New version page

UNL CSCE 235 - Discrete Mathematics: Introduction

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Upgrade to remove ads

This preview shows page 1-2 out of 5 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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
Download Discrete Mathematics: Introduction
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Discrete Mathematics: Introduction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Discrete Mathematics: Introduction 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?