Notes Discrete Mathematics Introduction Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics cse235 cse unl edu Computer Science Engineering 235 Notes Discrete Mathematics I Roll I Syllabus I Lectures M W F 1 30 2 20 Avery 109 I Recitations Tuesdays 5 30 6 20 Avery 108 Office hours I I I Instructor M W 2 30 3 30 Avery 123B TA Chris Bourke 1 00 2 00 Wed in Avery 123C and Thu in Avery 13A I Must have cse account I Must use webhandin I Bonus points report bugs Why Discrete Mathematics I You have to Computer Science is not programming It is not even Software Engineering Computer Science is no more about computers than astronomy is about telescopes Edsger Dijkstra Computer Science is problem solving Notes Why Discrete Mathematics II Notes Mathematics is at the heart of problem solving Often even defining a problem requires a level of mathematical rigor Competent use and analysis of models data structures algorithms requires a solid foundation in mathematics Justification for why a particular way of solving a problem is correct or efficient i e better than another way requires analysis within a well defined mathematical model Why Discrete Mathematics III Notes Abstract thinking is necessary to applying knowledge Rarely will you encounter a problem in an abstract setting your boss is not going to ask you to solve MST Rather it is up to you to determine the proper model of such a problem Scenario I A limo company has hired you or your company to write a computer program to automate the following tasks for a large event Task 1 In the first scenario businesses request limos and drivers for a fixed period of time specifying a start date time and end date time and charged a flat rate The program should be able to generate a schedule so that the maximum number of customers can be accommodated Notes Scenario II Notes Task 2 In the second scenario the limo service is considering allowing customers to bid on a driver so that the highest bidder gets a limo driver when there aren t enough available The program should thus make a schedule a feasible i e no limo can handle two customers at the same time while at the same time maximizing the profit by selecting the highest overall bids Scenario III Notes Task 3 In a third scenario a customer is allowed to specify a set of various times and bid an amount for the entire event A driver must choose to accept the entire set of times or reject it all The scheduler must still maximize the profit Scenario What s your solution How can you model such scenarios How can you develop algorithms for these scenarios How can you justify that that they work That they actually guarantee an optimal i e maximized profit solution Notes Scenario Notes The fundamentals that this course will teach you are the foundations that you will use to eventually solve these problems The first scenario is easily i e efficiently solved by a greedy algorithm The second scenario is also efficiently solvable but by a more involved technique dynamic programming The last scenario is not efficiently solvable it is NP hard by any known technique It is believed that to guarantee an optimal solution one needs to look at all exponentially many possibilities Fundamentals Notes Notation A set is a collection of similar objects We denote a set using brackets For example S s1 s2 s3 sn is a finite set and S s1 s2 s3 is an infinite set We denote that an object is an element of a set by the notation s1 S read s1 is in S or we can write s1 6 S for s1 is not in S Fundamentals Notes Notation You should at least be familiar with the sets of integers rationals and reals I We denote the set of natural numbers as N 0 1 2 3 I We denote the set of integers as Z 0 1 1 2 2 3 3 I We denote the set of rational numbers as na o Q a b Z b I We denote the set of reals as R x x is a decimal number Algebra I Notes Definition Let a b Z with b 6 0 we say that b divides a if and only if a qb for some integer q We will use the notation b a Algebra II Notes Example 2 divides 64 since 64 32 2 2 32 3 divides 27 since 27 9 3 3 27 However 2 does not divide 27 since there is no integer q such that 27 2q In this case we write 2 27 Topics Notes Topic Propositional Logic Predicate Logic Proofs Sets Functions Relations Algorithms Number Theory Induction Counting Combinatorics Recursion PIE Graphs Trees Sections 1 1 1 2 1 3 1 4 1 5 1 6 2 1 2 2 2 3 8 1 8 3 8 6 3 1 3 3 3 4 3 7 4 1 4 2 5 1 5 2 5 3 5 5 7 1 7 2 7 5 9 1 9 5 10 1 10 3
View Full Document
Unlocking...