Relevant course material will be made available on this webpage as the course progresses.

NOTICE: The midterm exam was on Thursday, May 24.

Assignments:

  • Assignment 1 is here. Due Tuesday May 15th, in class.
  • Assignment 2 is here. Due Tuesday May 22nd, in class.
  • Midterm Review sheet.
  • Midterm, without drawings, in postscript.
  • Midterm, without drawings, in pdf format.
  • Assignment 3 is here. Due Tuesday May 29nd, in class.

    NOTICE: Assignment 4 corrected on Fri June 1, 1pm.

  • Assignment 4 is here. Due Tuesday June 5th, in class.
  • Assignment 5 is here. Due Tuesday June 12th, in class.

    Course material that is not in the book but that you are responsible for:

  • The maximum bipartite matching problem and how to solve it using network flow and the Ford-Fulkerson algorithm.

  • Deterministic Finite Automata (DFAs) (what they are, how to "run them" on a string, how they accept words, the sets/languages of words they accept, how to construct a DFA given some language.)

  • Adjacency matrices of graphs (how to build one from a simple graph or a digraph, how to multiply the matrices, square-and-multiply method to obtain powers of matrices, how to interpret the kth power of an adjacency matrix, how to count edges/triangles/paths in graphs.)

  • Counting 01-strings by counting paths in a DFA.

    NOTE: The description of the Ford-Fulkerson algorithm given in the text (and as originally presented in class) is incorrect. On Thursday and Friday (June 7 and 8), I showed how the algorithm can be corrected by means of a Residual Graph.

    FINAL EXAM:

    the final exam will be on Tursday, June 14th, in ETLE 1-018 starting at 11:30am. It will be two hours long.

  • Final Exam Review sheet.
  • Final Exam, without drawings, in postscript.
  • Final Exam, without drawings, in pdf format.