Discrete Math for Computer Science

Syllabus

Fall 2025 Final’s Week Schedule:

Exam Times:

  • MAT 141 Monday 12/8 from 2 to 4:30pm
  • MAT 304 Monday 12/8 from 5:30 to 8pm
  • MAT 531 Tuesday 12/9 from 6 to 8:30pm
  • MAT 133 Friday 12/12 from 2 to 4:30pm

Final’s Week Office Hours:

  • Monday 12/8: 1-2pm
  • Tuesday 12/9: 3-6pm
  • Friday 12/12: 1-2pm

Calendar

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

  • …
  • 11/24 – We finished discussing graphs and adjacency matrices and started working through the slides on trees:
  • 11/17 – Tonight we covered adjacency matrices and matrix operations. One of the key takeaways was that raising adjacency matrices to higher powers allows us to count the number of paths between vertices of a given length. We also commented on the format of adjacency matrices for some particular graph types, specifically for disconnected graphs and bipartite graphs.
  • 11/10 – You got back the proofs exam, remember that redos are due on Monday the 17th. Tonight we covered, in detail, the proof that a graph has an Euler Circuit if and only if it is connected and all the vertices are of even degree. We also went over how to find the Euler Circuit and how to find an Euler Trail in the case when there are exactly two vertices of odd degree. We ended by looking at the conditions for having a Hamilton Circuit and looked at a couple of examples of how we can use that to decide if a graph has a Hamilton Circuit.
  • 11/3 – Exam 2 on Proofs
  • 10/27 – We did some additional proofs examples including some more proofs by induction. We then spent time reviewing vocabulary related to graph theory and looked at a couple of proofs. Next week is the proofs exam and the week after we will resume our discussion of graph theory. Prior to the exam we will spend 20-30 minutes answering questions if you have them.
  • 10/20 – We finished all the basic examples of proofs by mathematical induction, we did an example of a proof using strong induction and ended with an example of proof by structural induction. This concluded the work on Unit 2. We will start Unit 3 next week. The Unit 2 exam will be on November 3rd in line with the syllabus.
  • 10/13 – We finished our discussion of proofs by Contradiction and Proofs by Contrapositive. Then we introduced Proofs by Mathematical Induction
  • 10/6 – We discussed indirect proofs; proofs by contradiction where we assume \(P\wedge \sim Q\) and derive a contradiction and proofs by contrapositive where we assume \(\sim Q\) and try to derive \(\sim P\). Be sure to review all of this material for the quiz next week.
  • 9/29 – Exam 1
  • 9/22 – Having finished the Unit 1 material on 9/15, we started on Unit 2. We covered examples of direct proof with an emphasis on the general structure of the proofs, the importance of using precise definitions, and the benefits of working a problem from both ends. Next week is the Unit 1 exam and we will return to discussing proofs the week after.
  • 9/15 – We did additional examples of valid arguments, this was material from Section 2.3. We then went on to discuss predicates and truth sets in some detail including distinguishing between predicates like \[G(a,b):a>b\] and statements like \[\forall n,m \in \mathbb{Z}: G(a,b)\rightarrow G(a^3,b^3).\] We also discussed showing counter examples and negating false statement. Finally we talked briefly about the general structure of Direct Proofs, Proofs by Contrapositive and Contradiction, and Proofs by Induction. Over the next several weeks we will develop these ideas and look at examples. Finally, I forgot to give you a quiz so I will give those present 100% so there is a grade for tonight in the gradebook. There will be a quiz next week so be sure to study your notes.
  • 9/8 – Went over the syllabus and started reviewing logical concepts. We went through the most basic material and will pick up next Monday looking at logical arguments.

Assignments

All assignment submissions must be typed in \(\LaTeX\) and in complete sentences. Proper submission formatting counts for 10% of the assignment grade.

  • Assignment 1 Due 10/6
    • Section 2.4 (p.91) – 28, 31
    • Section 3.4 (p.156) – 20,22,27
  • Assignment 2 Due 11/17
    • 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
    • Section 5.3 (p,297) – 36
    • Section 5.9 (p,374) – 17, 20b
  • Assignment 3 Due 12/12 by 3pm
    • Section 4.9 (p,242) – 15
    • Section 10.2 (p.710) – 19, 21, (23 for extra credit)
    • Section 10.4 (p.731) – 29
    • Section 10.5 (p.741) – 3
    • For Extra Credit: Section 10.6 (p.757) – 19 (use 18)
  • Extra Credit Writing Assignment: Due 9/29
  • Extra Credit Induction Assignment: Due 12/12

Exams

  • Review Exam on 9/29/2024
    • All of chapter 1, sections 2.1-2.4 and sections 3.1-3.4
  • Proofs Exam on 11/3/ 2024
    • Sections 4.1, 4.4, 4.5, 4.7, 4.8, 5.2-5.4, 5.7, and 5.9
  • Graphs+ Exam on 12/8/2024
    • 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