CS261: Mathematcial Foundations of Computer Science

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).

Grading

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.

Textbook

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

Introduction (slides)

Mon Jun 3:


Logic and Proofs (slides, slides)

Reading: Rosen 1.1–1.8
Tue Jun 4:
Wed Jun 5:
Thu Jun 6:


Sets, Functions, Sequences, Sums and Cardinality (slides, slides)

Reading: Rosen 2.1–2.4
Mon Jun 10: Homework 1 Due.
Tue Jun 11:


Number Theory and Cryptography (slides)

Reading: Rosen 4.1–4.5
Wed Jun 12:
Thu Jun 13:
Reading: Rosen 4.6
Mon Jun 17: Homework 2 Due


Mathematical Induction and Recursion (slides)

Reading: Rosen 5.1–5.5
Tue Jun 18
Wed Jun 19


Counting (slides)

Reading: Rosen 6.1–6.4, 6.6
Thu Jun 20
Mon Jun 24: Homework 3 Due


Discrete Probability (slides)

Reading: Rosen 7.1–7.4
Tue Jun 25
Wed Jun 26:


Exam 1 (slides)

Thu Jun 27 Exam Review
Mon Jul 1: Exam 1. Homework 4 Due


Recurrence Relations (slides)

Reading: Rosen 8.1–1.8
Tue Jul 2
Wed Jul 3


Relations (slides)

Reading: Rosen 9.1-9.3, 9.5
Mon Jul 8: Homework 5 Due
Tue Jul 9


Graphs and Trees (slides)

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


Boolean Algebra (slides)

Reading: Rosen 12.1–12.4
Wed Jul 17


Modelling Computation (slides)

Reading: Rosen 13.1–13.5
Thu Jul 18
Mon Jul 22: Homework 7 Due
Tue Jul 23


Exam 2 (slides)

Wed Jul 24: Exam Review
Thu Jul 25: Exam 2. Homework 8 Due.

Homework