CS261: Mathematcial Foundations of Computer Science

Course Information

Instructor: Matthew Fricke
Website: http://www.cs.unm.edu/~mfricke
Room: Centennial Engineering Center 1032
Time: MTWTh 11:00am-12:15pm

Mailing List:

Course Description

Introduction to the formal mathematical concepts of computer science. Topics include proofs, first-order logic, set theory, functional relations, graphs, cryptography, state machines, and combinatorics.

Prerequisites: A minimum grade of C- in Computer Programming Fundamentals (CS151 or CS155 or CS152) and Calculus I (MATH162).


  1. Daily Class Exercises: 30% (1% each)
  2. Weekly Homeworks: 40% (5% each)
  3. Exams: 30% (Midterm 15% on July 1st; Final 15% on July 25th)

You may work together on the in-class exercises and homeworks. Use any resourse you find useful for the homeworks. No collaboration or resourses other than a pencil and paper are allowed during the exams. Exams will not be explictly comprehensive but, as with most math courses, comprehension of later topics depends on familiarity with earlier topics.

Makeups: There will be no makeups on the exercises or homeworks. If you miss an exam due to an unforeseeable emergency let me know as soon as possible and we will schedule a makeup. Makeup exams will be different from, but at least as hard as the regularly scheduled exam.

Academic Integrity: The University's policy on academic honesty can be found in the student handbook.

Disabilities: If you are a student who needs accessability services due to disability please let me know so that I can accomodate you. The Accessibility Resource Center website is at arc.unm.edu.


Discrete Title: Discrete Mathematics and its Applications 7th Ed.
Author: Ken Rosen
Publisher: McGraw-Hill Science

Hardcover (2011):
ISBN-10: 0073383090
ISBN-13: 978-0073383095

Course Topics and Assignments

  1. Introduction (slides)
  2. Mon Jun 3:

  3. Logic and Proofs (slides, slides)
  4. Reading: Rosen 1.1–1.8
    Tue Jun 4:
    Wed Jun 5:
    Thu Jun 6:

  5. Sets, Functions, Sequences, Sums and Cardinality (slides, slides)
  6. Reading: Rosen 2.1–2.4
    Mon Jun 10: Homework 1 Due.
    Tue Jun 11:

  7. Number Theory and Cryptography (slides)
  8. Reading: Rosen 4.1–4.5
    Wed Jun 12:
    Thu Jun 13:
    Reading: Rosen 4.6
    Mon Jun 17: Homework 2 Due

  9. Mathematical Induction and Recursion (slides)
  10. Reading: Rosen 5.1–5.5
    Tue Jun 18
    Wed Jun 19

  11. Counting (slides)
  12. Reading: Rosen 6.1–6.4, 6.6
    Thu Jun 20
    Mon Jun 24: Homework 3 Due

  13. Discrete Probability (slides)
  14. Reading: Rosen 7.1–7.4
    Tue Jun 25
    Wed Jun 26:

  15. Exam 1 (slides)
  16. Thu Jun 27 Exam Review
    Mon Jul 1: Exam 1. Homework 4 Due

  17. Recurrence Relations (slides)
  18. Reading: Rosen 8.1–1.8
    Tue Jul 2
    Wed Jul 3

  19. Relations (slides)
  20. Reading: Rosen 9.1-9.3, 9.5
    Mon Jul 8: Homework 5 Due
    Tue Jul 9

  21. Graphs and Trees (slides)
  22. Reading: Rosen 10.1–10.5
    Wed Jul 10
    Thu Jul 11
    Reading: Rosen 11.1–11.4
    Mon Jul 15: Homework 6 Due.
    Tue Jul 16

  23. Boolean Algebra (slides)
  24. Reading: Rosen 12.1–12.4
    Wed Jul 17

  25. Modelling Computation (slides)
  26. Reading: Rosen 13.1–13.5
    Thu Jul 18
    Mon Jul 22: Homework 7 Due
    Tue Jul 23

  27. Exam 2 (slides)
  28. Wed Jul 24: Exam Review
    Thu Jul 25: Exam 2. Homework 8 Due.


Homework 1 (solution)
Homework 2 (solution)
Homework 3 (solution)
Homework 4 (solution)
Homework 5 (solution)
Homework 6 (solution)
Homework 7 (solution)
Homework 8 (solution)