WIXLIB

Discrete Mathematics & Mathematical ReasoningCourse OverviewColin StirlingInformaticsColin Stirling (Informatics)Discrete MathematicsToday1 / 23

Teaching staffLecturers:Colin Stirling, first half of courseKousha Etessami, second half of courseCourse Secretary (ITO):Kendall Reid (kreid5@staffmail.ed.ac.uk)Colin Stirling (Informatics)Discrete MathematicsToday2 / 23

LecturesMonday 16.10-17.00 HereTuesday 10.00-10.50 Weeks 1& 7 LT C DHT; other weeks LT 4 ATThursday 16.10-17.00 HereColin Stirling (Informatics)Discrete MathematicsToday3 / 23

Course web page (not on r/Colin Stirling (Informatics)Discrete MathematicsToday4 / 23

Course web page (not on r/Contains important informationLecture slidesTutorial sheet exercisesLink to tutorial groupsCourse organization.Colin Stirling (Informatics)Discrete MathematicsToday4 / 23

TutorialsYou should receive email from the ITO informing you ofpreliminary allocation of tutorial groupsColin Stirling (Informatics)Discrete MathematicsToday5 / 23

TutorialsYou should receive email from the ITO informing you ofpreliminary allocation of tutorial groupsSee link on course web page for current assignment of tutorialgroupsColin Stirling (Informatics)Discrete MathematicsToday5 / 23

TutorialsYou should receive email from the ITO informing you ofpreliminary allocation of tutorial groupsSee link on course web page for current assignment of tutorialgroupsIf you can’t make the time of your allocated group, please emailKendall suggesting some groups you can manageColin Stirling (Informatics)Discrete MathematicsToday5 / 23

TutorialsYou should receive email from the ITO informing you ofpreliminary allocation of tutorial groupsSee link on course web page for current assignment of tutorialgroupsIf you can’t make the time of your allocated group, please emailKendall suggesting some groups you can manageIf you change tutor groups for any reason, you must let Kendalland the ITO know (because your marked coursework is returnedat the tutorial groups)Colin Stirling (Informatics)Discrete MathematicsToday5 / 23

TutorialsYou should receive email from the ITO informing you ofpreliminary allocation of tutorial groupsSee link on course web page for current assignment of tutorialgroupsIf you can’t make the time of your allocated group, please emailKendall suggesting some groups you can manageIf you change tutor groups for any reason, you must let Kendalland the ITO know (because your marked coursework is returnedat the tutorial groups)Tutorial attendance is mandatory. If you miss two tutorials in a row,your PT will be notifiedColin Stirling (Informatics)Discrete MathematicsToday5 / 23

Tutorials and (marked) exercisesWeekly exercise sheets, available previous Wednesday (except forthe first) on the course web pageColin Stirling (Informatics)Discrete MathematicsToday6 / 23

Tutorials and (marked) exercisesWeekly exercise sheets, available previous Wednesday (except forthe first) on the course web pageThe last question on every sheet will be graded. The courseworkgrade contributes 15% to the total course grade, and every one ofthe 9 exercise sheets counts 1/9th of the coursework gradeColin Stirling (Informatics)Discrete MathematicsToday6 / 23

Tutorials and (marked) exercisesWeekly exercise sheets, available previous Wednesday (except forthe first) on the course web pageThe last question on every sheet will be graded. The courseworkgrade contributes 15% to the total course grade, and every one ofthe 9 exercise sheets counts 1/9th of the coursework gradeStarting in week 2, deadline for submission of each tutorial sheetis Wednesday at 4:00pm. To do this you will use the online dicesubmit command (where your file is a pdf)Colin Stirling (Informatics)Discrete MathematicsToday6 / 23

Tutorials and (marked) exercisesWeekly exercise sheets, available previous Wednesday (except forthe first) on the course web pageThe last question on every sheet will be graded. The courseworkgrade contributes 15% to the total course grade, and every one ofthe 9 exercise sheets counts 1/9th of the coursework gradeStarting in week 2, deadline for submission of each tutorial sheetis Wednesday at 4:00pm. To do this you will use the online dicesubmit command (where your file is a pdf)Solutions will be discussed in tutorials the following week. Gradedsheets are returned in tutorials (or collected later from the ITO)Colin Stirling (Informatics)Discrete MathematicsToday6 / 23

Tutorials and (marked) exercisesWeekly exercise sheets, available previous Wednesday (except forthe first) on the course web pageThe last question on every sheet will be graded. The courseworkgrade contributes 15% to the total course grade, and every one ofthe 9 exercise sheets counts 1/9th of the coursework gradeStarting in week 2, deadline for submission of each tutorial sheetis Wednesday at 4:00pm. To do this you will use the online dicesubmit command (where your file is a pdf)Solutions will be discussed in tutorials the following week. Gradedsheets are returned in tutorials (or collected later from the ITO)Exception: no tutorial in week 1Colin Stirling (Informatics)Discrete MathematicsToday6 / 23

TextbookKenneth Rosen, Discrete Mathematics and its Applications,7th Edition, (Global Edition) McGraw-Hill, 2012Available at BlackwellsFor additional material see the course webpageColin Stirling (Informatics)Discrete MathematicsToday7 / 23

GradingWritten Examination: 85% IMPORTANT CHANGE THIS YEAR:OPEN BOOK EXAMAssessed Assignments: 15%. Each one of the 9 exercise sheetscounts equally. (Actually, first 8 sheets are each out of 11, and thelast is out of 12). IMPORTANT CHANGE THIS YEAR:SUBMISSIONS ARE DONE ON DICE MACHINESColin Stirling (Informatics)Discrete MathematicsToday8 / 23

GradingWritten Examination: 85% IMPORTANT CHANGE THIS YEAR:OPEN BOOK EXAMAssessed Assignments: 15%. Each one of the 9 exercise sheetscounts equally. (Actually, first 8 sheets are each out of 11, and thelast is out of 12). IMPORTANT CHANGE THIS YEAR:SUBMISSIONS ARE DONE ON DICE MACHINESTo pass course need 40% or more overall (No separateexam/coursework hurdle)Colin Stirling (Informatics)Discrete MathematicsToday8 / 23

GradingWritten Examination: 85% IMPORTANT CHANGE THIS YEAR:OPEN BOOK EXAMAssessed Assignments: 15%. Each one of the 9 exercise sheetscounts equally. (Actually, first 8 sheets are each out of 11, and thelast is out of 12). IMPORTANT CHANGE THIS YEAR:SUBMISSIONS ARE DONE ON DICE MACHINESTo pass course need 40% or more overall (No separateexam/coursework hurdle)Questions about course administration?Colin Stirling (Informatics)Discrete MathematicsToday8 / 23

Important themesmathematical reasoningcombinatorial analysisdiscrete structuresalgorithmic thinkingapplications and modellingColin Stirling (Informatics)Discrete MathematicsToday9 / 23

Foundations: proofRudimentary predicate (first-order) logic: existential and universalquantification, basic algebraic laws of quantified logic (duality ofexistential and universal quantification)The structure of a well-reasoned mathematical proof; proofstrategies: proofs by contradiction, proof by cases; examples ofincorrect proofs (to build intuition about correct mathematicalreasoning)Colin Stirling (Informatics)Discrete MathematicsToday10 / 23

Foundations: sets, functions and relationsSets (naive): operations on sets: union, intersection, setdifference, the powerset operation, examples of finite and infinitesets (the natural numbers). Ordered pairs, n-tuples, and Cartesianproducts of setsRelations: (unary, binary, and n-ary) properties of binary relations(symmetry, reflexivity, transitivity).Functions: injective, surjective, and bijective functions, inversefunctions, composition of functionsRudimentary counting: size of the Cartesian product of two finitesets, number of subsets of a finite set, (number of n-bitsequences), number of functions from one finite set to anotherColin Stirling (Informatics)Discrete MathematicsToday11 / 23

Induction and recursionPrinciple of mathematical induction (for positive integers)Examples of proofs by (weak and strong) inductionColin Stirling (Informatics)Discrete MathematicsToday12 / 23

Basic number theory and some cryptographyIntegers and elementary number theory (divisibility, GCDs and theEuclidean algorithm, prime decomposition and the fundamentaltheorem of arithmetic)Modular arithmetic (congruences, Fermat’s little theorem, theChinese remainder theorem)Applications: public-key cryptographyColin Stirling (Informatics)Discrete MathematicsToday13 / 23

Basic algorithmsConcept and basic properties of an algorithmSome examples of algorithmsBasics of growth of function, and complexity of algorithms:comparison of growth rate of some common functionsColin Stirling (Informatics)Discrete MathematicsToday14 / 23

CountingBasics of countingPigeon-hole principlePermutations and combinationsBinomial coefficients, binomial theorem, and basic identities onbinomial coefficientsGeneralizations of permutations and combinations (e.g.,combinations with repetition/replacement)Stirling’s approximation of the factorial functionColin Stirling (Informatics)Discrete MathematicsToday15 / 23

GraphsDirected and undirected graph: definitions and examples inInformaticsAdjacency matrix representationTerminology: degree (indegree, outdegree), and special graphs:bipartite, complete, acyclic, .Isomorphism of graphs; subgraphsPaths, cycles, and (strong) connectivityEuler paths/circuits, Hamiltonian paths (brief)Weighted graphs, and shortest paths (Dijkstra’s algorithm)Bipartite matching: Hall’s marriage theoremColin Stirling (Informatics)Discrete MathematicsToday16 / 23

TreesRooted and unrooted treesOrdered and unordered trees(Complete) binary (k-ary) treeSubtreesExamples in InformaticsSpanning trees (Kruskal’s algorithm, Prim’s algorithm.)Colin Stirling (Informatics)Discrete MathematicsToday17 / 23

Discrete probabilityDiscrete (finite or countable) probability spacesEventsBasic axioms of discrete probabilityIndependence and conditional probabilityBayes’ theoremRandom variablesExpectation; linearity of expectationBasic examples of discrete probability distributions, the birthdayparadox and other subtle examples in probabilityThe probabilistic method: a proof techniqueColin Stirling (Informatics)Discrete MathematicsToday18 / 23

My proofColin Stirling (Informatics)Discrete MathematicsToday19 / 23

My markColin Stirling (Informatics)Discrete MathematicsToday20 / 23

Reasoning 1Given the following two premisesAll students in this class understand logicColin is a student in this classColin Stirling (Informatics)Discrete MathematicsToday21 / 23

Reasoning 1Given the following two premisesAll students in this class understand logicColin is a student in this classDoes it follow thatColin understands logicColin Stirling (Informatics)Discrete MathematicsToday21 / 23

Reasoning 2Given the following two premisesEvery computer science student takes discrete mathematicsHelen is taking discrete mathematicsColin Stirling (Informatics)Discrete MathematicsToday22 / 23

Reasoning 2Given the following two premisesEvery computer science student takes discrete mathematicsHelen is taking discrete mathematicsDoes it follow thatHelen is a computer science studentColin Stirling (Informatics)Discrete MathematicsToday22 / 23

Reasoning 3Given the following three premisesAll hummingbirds are richly colouredNo large birds live on honeyBirds that do not live on honey are dull in colourColin Stirling (Informatics)Discrete MathematicsToday23 / 23

Reasoning 3Given the following three premisesAll hummingbirds are richly colouredNo large birds live on honeyBirds that do not live on honey are dull in colourDoes it follow thatHummingbirds are smallColin Stirling (Informatics)Discrete MathematicsToday23 / 23

Starting in week 2, deadline for submission of each tutorial sheet isWednesday at 4:00pm. To do this you will use the online dice submitcommand (where your file is a pdf) Solutions will be discussed in tutorials the following week. Graded sheets are returned in tutorials (or collected later from the ITO) Exception: no tutorial in week 1 Colin Stirling (Informatics) Discrete Mathematics Today .