Relevant course material will be made available on this webpage
as the course progresses.
NOTICE: The midterm exam was on Thursday, May 24.
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
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
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
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.