CS 275

Mathematical Foundations of Algorithms

The formal study of the mathematical foundations of algorithms. This course provides students with an algorithm-based introduction to discrete mathematical structures and their application to computer science. Topics include logic, sets, relations, functions, graphs, proof techniques, mathematical induction, recursive definitions, and recurrence relations. Applications include the correctness and complexity of algorithms.

• Textbook

  • Chapter 1 - Introduction
  • Chapter 2 - Logic
  • Chapter 3 - Proof
  • Chapter 4 - Sets
  • Chapter 5 - Relations
  • Chapter 6 - Recurrence Relations
  • Chapter 7 - Algorithm Complexity
  • Figures

• Homework

  • Homework #1 (due Sept. 1) Chapter 2 Problems 1-2
  • Homework #2 (due Sept. 10) Chapter 2 Problems 3-6
  • Homework #3 (due Sept. 15) Chapter 2 Problems 7-9, Chapter 3 Problems 1-3
  • Homework #4 (due Sept. 24) Chapter 3 Problems 4a, 5a, 7a
  • Homework #5 (due Sept. 29) Chapter 3 Problems 4c, 5c, 7c
  • Homework #6 (due Oct. 13) Chapter 4 Problems 1-5
  • Homework #7 (due Oct. 22) Chapter 5 Problems 1-11
  • Homework #8 (due Oct. 29) Chapter 5 Problems 12-14
  • Homework #9 (due Nov. 10) Chapter 6 Problems 1-2, 6-8
  • Homework #10 (due Dec. 1) Chapter 7 Problems 1-2

• Exams

  • Exam #1 (Chapters 1-3) - Thursday, October 1
  • Exam #2 (Chapters 4-6) - Tuesday, November 17
  • Final Exam (Chapters 1-8) - Tuesday, December 8 (1:00-3:00pm)

• Resources

  • ProVIDE
  • Constructing Contracts Notes