DS Lecture-1 about discrete structure .ppt

dicrete structure

1. MA -210
Discrete Structures
Introduction
Lecture-1

2. Overview of this Lecture
•Course Administration
•What is it about?
•Course Themes, Goals, and Syllabus
•Propositional logic

3. Course Administration

4. Timings
Lecture Hours:
Monday(α ): 12:00 PM –03:00 PM
Tuesday(Ω): 12:00 PM –03:00 PM
Location:
Class Room 5
Lecturer: Mona Waseem
Office: Faculty Office (Room-10), Ground Floor, CPED
Phone: [phone]
Email: [email protected]

5. Assessments
Homework (12%)
Quiz (13%)
Midterm (25%)
Final (50%)

6. Homework and Quiz
•Homeworkisveryimportant.Itisthebestwayforyouto
learnthematerial.
•Youcandiscusstheproblemswithyourclassmates,butall
workhandedinshouldbeoriginal,writtenbyyouin
yourownwords.
•Homeworkshouldbehandedininclass.
•20%penaltyforeachdaylate.
•MostProbablyQuizwillbeannouncedaweek
beforeBUTtherewillbeNORe-TakeforQuiz
inanyCase.

7. Textbook
Discrete Mathematics and Its Applications
by Kenneth H. Rosen, 7
th
Edition

8. Reference Book(1)
Discrete Mathematics
by Richard Johnsonbaugh
7
th
or 8
th
Edition

9. Reference Book(2)
Discrete Mathematics
by Edgar Goodaireand Michael Parmenter
3
rd
Edition.

10. Course Learning Outcome (CLO’s)
S.No. Course Learning Outcome (CLO’s)
Bloom’s
Learning
Level
1.
Recallthebasicconceptsoflogicandproofs,settheory,
relationsinfunctionsandcomplexityofalgorithms.
C1,PLO-1
2.
Demonstratethefundamentalconceptsofcounting,graphs,
trees,andMathematicalInduction.
C2,PLO-1
3.
Confidentlyapplytheknowledgelearnttosolve
mathematicalproblemsincomputerscienceandengineering
disciplines.
C3,PLO-2
Learning Levels (LL):Knowledge (LL1), Comprehension (LL2), Application
(LL3), Analysis (LL4), Synthesis (LL5), Evaluation (LL6)

11. Overview of this Lecture
Course Administration
What is MA-210about?
Course Themes, Goals, and Syllabus

12. Continuous vs. Discrete Math
Why is it computer science/engineering?
Mathematical techniques for DM
What is MA-210about?

13. What Are Discrete Structures?
Discrete math is mathematics that deals with discrete objects:
• Discrete Objects are those which are separated from (distinct from)
each other, such as integers, rational numbers, houses, people, etc.
Real numbers are not discrete.
• In this course, we’ll be concerned with objects such as integers,
propositions, sets, relations and functions, which are all discrete.
• We’ll learn concepts associated with them, their properties, and
relationships among them.
Discrete structures are:
–Theoreticalbasisofcomputerscience
–Amathematicalfoundationthatmakesyouthinklogically
–Aprerequisitecoursetounderstandthefundamentalsofprogramming

14. Discrete vs. Continuous Mathematics
ContinuousMathematics
Itconsidersobjectsthatvarycontinuously;
Example:analogwristwatch(separatehour,minute,andsecondhands).
Fromananalogwatchperspective,between1:25p.m.and1:26p.m.
thereareinfinitelymanypossibledifferenttimesasthesecondhandmoves
aroundthewatchface.
Real-numbersystem---coreofcontinuousmathematics;
Continuousmathematics---modelsandtoolsforanalyzingreal-world
phenomenathatchangesmoothlyovertime.(Differentialequationsetc.)

15. Discrete vs. Continuous Mathematics
DiscreteMathematics
Itconsidersobjectsthatvaryinadiscreteway.
Example:digitalwristwatch.
Onadigitalwatch,thereareonlyfinitelymanypossibledifferenttimes
between1:25P.m.and1:27P.m.Adigitalwatchdoesnotshowsplit
seconds:notimebetween1:25:03and1:25:04.Thewatchmovesfromone
timetothenext.
Integers---coreofdiscretemathematics
Discretemathematics---modelsandtoolsforanalyzingreal-world
phenomenathatchangediscretelyovertimeandthereforeidealforstudying
computerscience–computersaredigital!(numbersasfinitebitstrings;data
structures,alldiscrete!Historicalaside:earliestcomputerswereanalogue.)

16. Discrete vs Continuous

17. Why is it computer science/engineering?
(examples)
What is MA-210 about?

18. •Computersusediscretestructurestorepresent
andmanipulatedata.
•isthebasicbuildingblockforbecominga
ComputerScientist
•ComputerScienceisnotProgramming
•ComputerScienceisnotSoftwareEngineering
•EdsgerDijkstra:“ComputerScienceisnomore
aboutcomputersthanAstronomyisabout
telescopes.”
•ComputerScienceisaboutproblemsolving.
Why Discrete Mathematics? (I)

19. •Mathematicsisattheheartofproblemsolving
•Definingaproblemrequiresmathematicalrigor
•Useandanalysisofmodels,datastructures,
algorithmsrequiresasolidfoundationof
mathematics
•Tojustifywhyaparticularwayofsolvinga
problemiscorrectorefficient(i.e.,betterthan
anotherway)requiresanalysiswithawell-
definedmathematicalmodel.
Why Discrete Mathematics? (II)

20. •Yourbossisnotgoingtoaskyoutosolve
–anMST(MinimalSpanningTree)or
–aTSP(TravellingSalespersonProblem)
•Rarelywillyouencounteraprobleminan
abstractsetting
•However,he/shemayaskyoutobuildarotation
ofthecompany’sdeliverytruckstominimize
fuelusage
•Itisuptoyoutodetermine
–apropermodelforrepresentingtheproblemand
–acorrectorefficientalgorithmforsolvingit
Problem Solving requires mathematical rigor
(Accuracy, Objectivity)

21. Discrete Mathematics in the Real
World
21

22. Computersrunsoftwareandstorefiles.
Thesoftware/filesbothstoredashugestringsof1sand0s.
Binarymathisdiscretemathematics.
22

23. 23

24. 24

25. Number Theory:
RSA and Public-key Cryptography
Alice and Bob have never met but they would like to
exchange a message. Eve would like to eavesdrop.
They could come up with a good
encryption algorithm and exchange the
encryption key–but how to do it without
Eve getting it? (If Eve gets it, all security
is lost.)
CS folks found the solution:
public key encryption. Quite remarkable that is feasible.
E.g. between you and the Bank of America.

26. Number Theory:
Public Key Encryption
RSA –Public Key Cryptosystem (why RSA?)
Uses modular arithmetic and large primes Its security comes from the computational difficulty
of factoring large numbers.

27. RSA Approach
•Encode:
•C = M
e
(mod n)
• M is the plaintext; C is ciphertext
• n = pq with p and q large primes (e.g. 200 digits long!)
• e is relative prime to (p-1)(q-1)
•Decode:
•C
d
= M (mod pq)
• d is inverse of e modulo (p-1)(q-1)
The process of encrypting and decrypting a message
correctly results in the original message (and it’s fast!)
Hmm??
What does this all mean??
How does this actually work?
Not to worry. We’ll find out.

28. Online Shopping
Encryptionanddecryptionarepartof
cryptography,whichispartofdiscrete
mathematics.Forexample,secureinternet
shoppingusespublic-keycryptography.
28

29. Analog Clock
AnAnalogClockhasgearsinside,andthesizes/teeth
neededforcorrecttimekeepingaredeterminedusing
discretemathofmodulararithmetic.
29

30. Dijkstra’s Algorithm and Google Maps
GoogleMapsusesdiscretemathematicsto
determinefastestdrivingroutesandtimes.
30

31. Railway Planning
Railwayplanningusesdiscretemath:decidinghowto
expandtrainraillines,traintimetablescheduling,and
schedulingcrewsandequipmentfortraintripsuse
bothgraphtheoryandlinearalgebra.
31

32. 32

33. Computer Graphics
Computergraphics(suchasinvideogames)uselinear
algebrainordertotransform(move,scale,change
perspective)objects.That'strueforbothapplications
likegamedevelopment,andforoperatingsystems.
33

34. Smarter Phones for All
CellPhoneCommunications:Makingefficientuseofthe
broadcastspectrumformobilephonesuseslinear
algebraandinformationtheory.Assigningfrequencies
sothatthereisnointerferencewithnearbyphonescan
usegraphtheoryorcanusediscreteoptimization.
34

35. Graphs and Networks
Many problems can be
represented by a graphical network
representation.
•Examples:
–Distribution problems
–Routing problems
–Maximum flow problems
–Designing computer / phone / road networks
–Equipment replacement
–And of course the Internet
Aside: finding the right
problem representation
is one of the key issues
in this course.

36. Sub-Category Graph
No Threshold New Science of Networks
NYS Electric
Power Grid
(Thorp,Strogatz,Watts)
Cyber communities
(Automatically discovered)
Kleinberg et al
Network of computer scientists
ReferralWeb System
(Kautz and Selman)
Neural network of the
nematode worm C-elegans
(Strogatz, Watts)
Networks are
pervasive
Utility Patent network
1972-1999
(3 Million patents)
Gomes,Hopcroft,Lesser,Selman

37. Applications of Networks
Applications
Physical analog
of nodes
Physical analog
of arcs
Flow
Communication
systems
phone exchanges,
computers,
transmission
facilities, satellites
Cables, fiber optic
links, microwave
relay links
Voice messages,
Data,
Video transmissions
Hydraulic systems
Pumping stations
Reservoirs, Lakes
Pipelines
Water, Gas, Oil,
Hydraulic fluids
Integrated
computer circuits
Gates, registers,
processors
Wires Electrical current
Mechanical systems Joints
Rods, Beams,
Springs
Heat, Energy
Transportation
systems
Intersections,
Airports,
Rail yards
Highways,
Airline routes
Railbeds
Passengers,
freight,
vehicles,
operators

38. Finding Friends on Facebook
GraphtheorycanbeusedinspeedingupFacebook
performance.
39

39. DNA Fragment Assembly
Graph theory is used in DNA sequencing.
40

40. Applications Of Discrete Structures
Algorithms can be used in searching for a letter or number in the list.
The study of these sorting algorithms often involves analyzing their time
complexity, space complexity,and other performance characteristics
using discrete mathematics concepts.

41. Applications Of Discrete Structures
Set theory can be used to determine number of students enrolled in
discrete structures and number of students enrolled in applied
physics in this semester.

42. Learning Discrete Mathematics make you
a better Programmer?
Oneofthemostimportantcompetences–thatonemust
have;asaprogramdeveloperistobeabletochoosetheright
algorithmsanddatastructuresfortheproblemthatthe
programissupposedtosolve.
Theimportanceofdiscretemathematicsliesinitscentralrole
intheanalysisofalgorithmsandinthefactthatmany
commondatastructures–andinparticulargraphs,trees,sets
andorderedsets–andtheirassociatedalgorithmscomefrom
thedomainofdiscretemathematics.43

43. Logic and Proofs
Programmersuselogic.Allthetime.Whileeveryone
hastothinkaboutthesolution,aformalstudyof
logicalthinkinghelpsyouorganizeyourthought
processmoreefficiently.
44

44. Logic:
Hardware and software specifications
One-bit Full Adder with
Carry-In and Carry-Out
4-bit full adder
Example 2: System Specification:
–The router can send packets to the edge system only if it supports the new address space.
–For the router to support the new address space it’s necessary that the latest software release be installed.
–The router can send packets to the edge system if the latest software release is installed.
–The router does not support the new address space.
Example 1: Adder
How to write these specifications in a formal way? Use Logic.
Formal: Input_wire_A
value in {0, 1}

45. Propositional Logic
System specificationsdemonstrate the requirements of
a system. These requirements are stated in English
sentences which can be ambiguous. Therefore,
translating these English requirements into logical
expressions removes the ambiguity and check for the
consistency of specifications.
Compound propositions and quantifiers can be used to
express the specifications and then find an assignment
of truth values that make all the specifications true.

46. Why Proofs?
Whyproofs?Theanalysisofanalgorithmrequires
onetocarryout(orattheveryleastbeableto
sketch)aproofofthecorrectnessofthealgorithm
and a proof of itscomplexity
47

47. Moral of the Story???
DiscreteMathisneededtoseemathematical
structuresintheobjectyouworkwith,and
understandtheirproperties.Thisabilityisimportant
forcomputer/softwareengineers,datascientists,
securityandfinancialanalysts.
itisnotacoincidencethatmathpuzzlesareoften
usedforinterviews.
48

48. Discrete Mathematics is a Gateway
Course
Topicsindiscretemathematicswillbeimportantin
manycoursesthatyouwilltakeinthefuture:
ComputerScience:ComputerArchitecture,Data
Structures,Algorithms,Programming Languages,
Compilers,ComputerSecurity,Databases,Artificial
Intelligence,Networking,Graphics,GameDesign,Theory
ofComputation,GameTheory,NetworkOptimization……
OtherDisciplines:Youmayfindconceptslearnedhere
usefulincoursesinphilosophy,economics,linguistics,
andotherdepartments.
52

49. Course Themes, Goals, and Course Outline

50. Goals of MA-210
Introduce students to a range of mathematical tools from discrete
mathematics that are key in computer science
Mathematical Sophistication
How to write statements rigorously
How to read and write theorems, lemmas, etc.
How to write rigorous proofs
Areas we will cover:
Logic and proofs
Set Theory
Number Theory
Counting and combinatorics
Practice works!
Actually, only practice works!
Note: Learning to do proofs from
watching the slides is like trying to
learn to play tennis from watching
it on TV! So, do exercises!

51. Tentative Topics MA-210
Logic and Methods of Proof
Propositional Logic ---SAT as an encoding language!
Predicates and Quantifiers
Methods of Proofs
Number Theory
Modular arithmetic
RSA cryptosystems
Sets
Sets and Set operations
Functions
Counting
Basics of counting
Pigeonhole principle
Permutations and Combinations

52. Topics MA-210
Graphs and Trees
Graph terminology
Example of graph problems and algorithms:
graph coloring
TSP
shortest path
Min. spanning tree

53. Bart Selman
CS2800
What’s your job?
•Buildamathematicalmodelforeachscenario
•Developanalgorithmforsolvingeachtask
•Provethatyoursolutionswork
–Termination:Provethatyouralgorithmsterminate
–Completeness:Provethatyouralgorithmsfinda
solutionwhenthereisone.
–Soundness:Provethatthesolutionofyouralgorithmsis
alwayscorrect
–Optimality(ofthesolution):Provethatyouralgorithms
findthebestsolution(i.e.,maximizeprofit)
–Efficiency,time&spacecomplexity:Provethatyour
algorithmsfinishbeforetheendoflifeonearth

54. Bart Selman
CS2800
Discrete Structures
Logic

55. Bart Selman
CS2800
Logic
•Logic, is the study of reasoning and making
sense of things in a systematic and clear way.
•It helps us figure out if our ideas and
arguments make sense, and it provides a
way to think through problems and come to
reliable conclusions.
•Logic is like having a set of steps to follow to
make good decisions and understand things
better.

56. Bart Selman
CS2800

57. Bart Selman
CS2800

58. Bart Selman
CS2800
Activity
Which of these sentences are propositions? What are the
truth values of those that are propositions?
•Boston is the capital of Massachusetts.
•Miami is the capital of Florida.
•2+3=5
•x+7=10
Answer this question

59. Bart Selman
CS2800
Answers
1.Boston is the capital of Massachusetts.
1.Proposition: Yes
2.Truth Value: True
2.Miami is the capital of Florida.
1.Proposition: Yes
2.Truth Value: False (Miami is not the capital of Florida; it is
Tallahassee)
3.2 + 3 = 5.
1.Proposition: Yes
2.Truth Value: True (mathematically correct)
4.x + 7 = 10.
1.Not a Proposition (contains a variable; its truth depends on the
value of x)

60. Bart Selman
CS2800

61. Bart Selman
CS2800

62. Bart Selman
CS2800

63. Bart Selman
CS2800

64. Bart Selman
CS2800

65. Bart Selman
CS2800
Activity
What is the negation of these propositions
•Mei has an MP3 player.
•There is no pollution.
•2+1=3
•The summer in Maine is hot and sunny.

66. Bart Selman
CS2800
Answers
1.Mei has an MP3 player:
1.Negation: Mei does not have an MP3 player.
2.Symbolically: ¬p
2.There is no pollution:
1.Negation: There is pollution.
2.Symbolically: ¬q
3.2+1=3:
1.Negation: 2+1is not equal to 3.
2.Symbolically: ¬(2+1=3)
4.The summer in Maine is hot and sunny:
1.Negation: The summer in Maine is not hot and sunny (it could be
cold or not sunny).
2.Symbolically: ¬(p∧q)

67. Bart Selman
CS2800

68. Bart Selman
CS2800

69. Bart Selman
CS2800

70. Bart Selman
CS2800

71. Bart Selman
CS2800

72. Bart Selman
CS2800
Activity
Let p and be the propositions
p: It is below freezing
q: It is snowing
Write these propositions using p and q and logical
connectives
a)It is below freezing and snowing
b)It is below freezing but not snowing
c)It is not below freezing and it is not snowing
d)It is either snowing or below freezing(or both)

73. Bart Selman
CS2800
Answers
a. It is below freezing and snowing:
p∧q
b. It is below freezing but not snowing:
p∧¬q
c. It is not below freezing and it is not
snowing:
¬p∧¬q
d. It is either snowing or below freezing (or
both):
p∨q

74. Bart Selman
CS2800

75. Bart Selman
CS2800

76. Bart Selman
CS2800

77. Bart Selman
CS2800

78. Bart Selman
CS2800

79. Bart Selman
CS2800

80. Bart Selman
CS2800

81. Bart Selman
CS2800

82. Bart Selman
CS2800

83. Bart Selman
CS2800
Activity
Let p and be the propositions
p: It is below freezing
q: It is snowing
Write these propositions using p and q and logical
connectives
a)If it is below freezing, then it is snowing.
b) It is snowing whenever it is below freezing.
c) That it is below freezing is necessary and sufficient for it to be
snowing

84. Bart Selman
CS2800
Activity
Let p and be the propositions
p: It is below freezing
q: It is snowing
Write these propositions using p and q and logical
connectives
a) If it is below freezing, then it is snowing.
p→q
b) It is snowing whenever it is below freezing.
p→q
c) That it is below freezing is necessary and sufficient for it to be
snowing
p↔q

85. Bart Selman
CS2800

86. Bart Selman
CS2800

87. Bart Selman
CS2800

88. Bart Selman
CS2800

89. Bart Selman
CS2800

90. Bart Selman
CS2800

91. Bart Selman
CS2800

92. Bart Selman
CS2800
Construct a truth table for each of these compound
propositions
•p ∧¬p
•p v ¬p
•p ⊕(p v q)
•(p v q) → (p ∧q)
•p ⊕¬ q
Activity

93. Bart Selman
CS2800
The end