Discrete Mathematics: IntroductionSlides by: Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete [email protected] Science & Engineering 235Discrete MathematicsIRollISyllabusILectures: M/W/F 1:30 – 2:20 (Avery 109)IRecitations: Tuesdays 5:30 – 6:20 (Avery 108)IOffice hours:IInstructor: M/W 2:30 – 3:30 (Avery 123B)ITA: Chris Bourke: 1:00 – 2:00 (Wed in Avery 123C and Thu inAvery 13A)IMust have cse accountIMust use webhandinIBonus points: report bugsNotesWhy Discrete Mathematics? IYou have to.Computer Science is not programming.It is not even Software Engineering.“Computer Science is no more about computers thanastronomy is about telescopes.” –Edsger DijkstraComputer Science is problem solving.NotesWhy Discrete Mathematics? IIMathematics is at the heart of problem solving.Often, even defining a problem requires a level of mathematicalrigor.Competent use and analysis of models/data structures/algorithmsrequires a solid foundation in mathematics.Justification for why a particular way of solving a problem iscorrect or efficient (i.e., better than another way) requires analysiswithin a well defined mathematical model.NotesWhy Discrete Mathematics? IIIAbstract thinking is necessary to applying knowledge.Rarely will you encounter a problem in an abstract setting (yourboss is not going to ask you to solve MST). Rather, it is up to youto determine the proper model of such a problem.NotesScenario IA limo company has hired you (or your company) to write acomputer program to automate the following tasks for a largeevent.Task 1 – In the first scenario, businesses request limos and driversfor a fixed period of time (specifying a start-date/time andend-date/time) and charged a flat rate. The program should beable to generate a schedule so that the maximum number ofcustomers can be accommodated.NotesScenario IITask 2 – In the second scenario, the limo service is consideringallowing customers to bid on a driver (so that the highest biddergets a limo/driver when there aren’t enough available). Theprogram should thus make a schedule a feasible (i.e., no limo canhandle two customers at the same time) while at the same time,maximizing the profit by selecting the highest overall bids.NotesScenario IIITask 3 – In a third scenario, a customer is allowed to specify a setof various times and bid an amount for the entire event. A drivermust choose to accept the entire set of times or reject it all. Thescheduler must still maximize the profit.NotesScenarioWhat’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 actuallyguarantee an optimal (i.e., maximized profit) solution?NotesScenarioThe fundamentals that this course will teach you are thefoundations that you will use to eventually solve these problems.The first scenario is easily (i.e., efficiently) solved by a greedyalgorithm.The second scenario is also efficiently solvable, but by a moreinvolved technique, dynamic programming.The last scenario is not efficiently solvable (it is NP-hard) by anyknown technique. It is believed that to guarantee an optimalsolution, one needs to look at all (exponentially many) possibilities.NotesFundamentalsNotationA set is a collection of similar objects. We denote a set usingbrackets. For example,S = {s1, s2, s3, . . . , sn}is a finite set andS = {s1, s2, s3, . . .}is an infinite set.We denote that an object is an element of a set by the notation,s1∈ Sread “s1(is) in S” (or we can write s16∈ S for “s1(is) not in S”)NotesFundamentalsNotationYou should at least be familiar with the sets of integers, rationalsand reals.IWe denote the set of natural numbers asN = {0, 1, 2, 3, . . .}IWe denote the set of integers asZ = {0, 1, −1, 2, −2, 3, −3, . . .}IWe denote the set of rational numbers asQ =nab| a, b ∈ ZoIWe denote the set of reals asR = {x | x is a decimal number}NotesAlgebra IDefinitionLet a, b ∈ Z with b 6= 0. we say that b divides a if and only ifa = qbfor some integer q. We will use the notationb | aNotesAlgebra IIExample2 divides 64 since 64 = 32×22 | 323 divides 27 since 27 = 9×33 | 27However, 2 does not divide 27 since there is no integer q such that27 = 2qIn this case, we write 2 - 27NotesTopicsTopic SectionsPropositional Logic 1.1 – 1.2Predicate Logic 1.3 – 1.4Proofs 1.5 – 1.6Sets 2.1 – 2.2Functions 2.3Relations 8.1, 8.3 – 8.6Algorithms 3.1 – 3.3Number Theory 3.4 – 3.7Induction 4.1 – 4.2Counting 5.1 – 5.2Combinatorics 5.3 – 5.5Recursion 7.1 – 7.2PIE 7.5Graphs 9.1 – 9.5Trees 10.1 –
View Full Document
Unlocking...