Discrete Math for Computer Science

Syllabus

Calendar

The syllabus has a calendar of what is planned for each day; below we record what we actually cover each day.

  • …
  • 11/27 – For the quiz we discussed Hamilton Circuits and Adjacency Matrices. We then briefly discussed graph isomorphisms as a 1-1 and ont map between vertex sets which “preserves” edge relationships. In particular we emphasized properties of graphs which must be preserved by a graph isomorphism. We then started looking at Trees and their properties. We looked the first three section of these Slides on Trees, which we will finish next week.
  • 11/20 – We looked at more examples of types of walks in graphs, looked at proofs of theorems/algorithms for identifying Euler Circuits, Euler Trails, and Hamilton Circuits. Then we discussed adjacency matrices – how to build them, how to identify graph properties with them, how to add them and what that represents, and how to multiply them and what that represents. Here is a link to a page with two code cells where you can play with the NumPy we looked at in class: Adjacency Matrix Calculations
  • 11/13 – Exams were returned tonight, redos are do next week; recall that these need to be typed and in complete sentences. We also discussed some proofs related to graph theory and introduced a variety of terms for walks on a graph. The material we covered was from sections 1.4, 4.9, and 10.1.
  • 11/6 – Exam on Proof Techniques
  • 10/30 – We finished up our discussion of proof techniques
  • 10/23 – We looked at examples of direct proofs as well at proofs by contrapositive and contradiction. We then did three examples of proofs by induction. We will look at more examples of induction and discuss recursion next week.
  • 10/16 – Tonight we looked at a short and a long example of direct proof and then started discussing indirect proof methods. We looked at some examples of proof by contrapositive and discussed when we might use proof by contrapositive instead of proof by contradiction. Next week we will look at a couple classic examples of proof by contradiction before moving onto proof by induction.
  • 10/9 – Tonight I handed back the exams, redos are due next week, as with homework the redos must be typed up. We then discussed the structure of direct proofs, contrapositive proofs, and contradiction proofs. We looked at some examples of direct proofs, discussing along the way existential and universal proofs, and along the way we discussed ways to show a statement is false. Then we learned the definitions of divisibility (\(b|a\)) and modular equivalence (\(a\equiv b\pmod{n}\)) which we showed was an equivalence relation. Great emphasis was placed on using definitions whenever possible to help us construct proofs. We ended by stating the Division Algorithm/Quotient Remainder Theorem \[\forall a,b\in\mathbb{Z}: b\neq 0\rightarrow \exists q,r\in\mathbb{Z}: a=qb+r\ \wedge\ 0\leq r< |b|,\] we will pick things up there next class after the quiz.
  • 10/2 – Exam 1
  • 9/25 – We looked at material from chapter 3 ahead of the exam on 10/2
  • 9/18 – Today we went over all the material from Sections 2.1-2.4 for this class. Next week we will look at Sections 3.1-3.4.
  • 9/11 – We went over the syllabus and we discussed terminology, most of which should be familiar from MAT 141. Be sure to review the material in Chapter 1. We will be going over chapter 2 next class.

Assignments

All assignment submissions must be typed and in complete sentences. Proper submission formatting may count for up to 10% of the assignment grade.

  • Extra Credit: Writing Up Mathematics – It is recommended  that you finish this early, but may be turned in any time before 12/11/2023.  This must be typed.
  • Assignment 1 Due 10/9
    • Section 2.4 (p.91) – 28, 31
    • Section 3.4 (p.156) – 27, 32, 34
  • Assignment 2 Due 11/13
    • Section 4.4 (p. 197) – 28 & 29 (look at the solutions to the previous problems to get a hint how these might work)
    • Section 4.7 (p.225) – 18 (look in your notes at the similar proofs we did in class)
    • Section 5.3 (p,297) – 36
    • Section 5.9 (p,374) – 17, 20b
  • Assignment 3 Due 12/15 by 3pm
    • Section 4.9 (p,242) – 15
    • Section 10.1 (p.693) – 42
    • Section 10.2 (p.710) – 19
    • Section 10.4 (p.731) – 29
    • Section 10.5 (p.741) – 3
    • For Extra Credit: Section 10.6 (p.757) – 19 (use 18)
  • Due 12/15/2023 – Extra Credit Induction Assignment: Complete this Scaffolded Induction Exercise Extra Credit for upto +2% on your final grade.

Exams

  • Review Exam on 10/2/2023
    • All of chapter 1, sections 2.1-2.4 and 3.1-3.4
  • Proofs Exam on 11/6/ 2023
    • Sections 4.1, 4.4, 4.5, 4.7, 4.8, 5.2-5.4, 5.7, and 5.9
  • Graphs+ Exam on 12/11/2023
    • Sections 1.4, 4.9, 10.1-10.6 (75% of the exam)
    • Previous material from Units 1 and 2 (25% of the exam)

Links and Handouts