MATH 3330: Notes

LINKS

• The Final exam of this course will be held on Wednesday, April 18, at 9am in the Dal arena. The exam will be 3 hours long. It will cover all the material covered in class as outlined below. If you did poorly on the midterm but do well on the final exam, then I will replace your midterm mark with the mark of the final exam. Like the midterm, the final exam will be closed book, but you will be allowed one letter size sheet of handwritten notes (both sides).

  I recommend that you study the solutions to the assignments, and the topics and sections listed below. For the Floyd-Warshall algorithm, study the notes handed out in class, and the example posted on the notes page. For minimum cost flow, study the hand-out from class, and the solutions to the assignment.

  I will have office hours on Thursday, April 11, 11am-1pm, Monday, April 16, 1-2pm, and Tuesday, April 17, 2-3.30pm. I am around, so you can also ask for an appointment by email.

• Thursday, March 29: Travelling Salesman problem. Three heuristics. Hamiltonian cycles. Sections 6.3 and 6.4.
• Tuesday, March 27: Graph colouring. Section 9.1. Perfect graphs. Interval graphs. Bipartite graphs. Clique number, chromatic number.
• Thursday, March 22: Minimum cost flow. See handout.
• Step-by-step example of Floyd-Warshall algorithm
• Tuesday, March 20: Bipartite matchings and relation with max flow. Vertex covers. Section 13.4. Floyd-Warshall algorithm for shortest (cheapest) path when negative edge weights are allowed. ( Not in book; handout will be given, see also the links)
• Thursday, March 15: Matchings. Bipartite matchings and relation with max flow. Vertex covers. Section 13.4
• Tuesday, March 13: Applications of max flow/min cut. Connectivity. Capacities on the vertices. Sections 13.3, see also 5.3. Introduction to bipartite matchings.
• Thursday, March 8: Solving the maximum-flow problem. Ford Fulkerson algorithm. Section 13.2.
• Tuesday, March 6: Introduction to network flows. Definition of flow, and its value. Definition of cut, and its capacity. Proof that the maximum value of an s-t-flow is less than or equal to the minimum capacity of an s-t cut. Section 13.1.

• There will be a Midterm in class on Thursday, March 1. The midterm will be 70 minutes long. It will cover all the material covered in class sofar, see below. It will be closed book, but you will be allowed one letter size sheet of handwritten notes. I recommend that you study the solutions to the assignments, and the topics and sections listed below. The class on Tuesday, February 27 will be a review.

• Thursday, February 15: Applications of Eulerian tours. Postman problem, RNA sequencing. Section 6.2.
• Tuesday, February 13: Eulerian tours. Applications: deBruijn sequences, two-person conferences. Section 6.1.
• Thursday, February 8: Vertex- and edge connectivity. Sections 5.1, 5.2. Presentations: bipartite graphs have no odd cycles, p.41, sequencing two-person conferences, p.258.
• Tuesday, February 6: Dijkstra's shortest path algorithm, section 4.3. Presentation: Tree-graphic sequences, p.121.
• Thursday, February 1: repeat of DFS and BFS. Section 4.4: using DFS to find cut vertices. Presentation: center of a tree. p.119-120.
• Tuesday, January 30: Growing trees. Depth-First-Search (DFS) and Breadth- First-Search (BFS). Sections 4.1 and 4.2. Tarry's maze: page 189. Presentation: every tree has at least two leaves. p.116.
• Thursday, January 25: More about trees and connectivity. Rooted trees (Section 3.2, first part)
• Tuesday, January 23: Connectivity and trees (Section 3.1) Minimum spanning tree (Section 4.3, first part). Cut vertex/edge (Section 2.4, first part.) Presentation: Rigidity in rectangular frame structures: Page 33--34.
• Thursday, January 19: Subgraphs. Cartesian products of graphs. Sections 2.3, 2.7 first part. Hypercubes (page 18).
• Tuesday, January 17: Isomorphisms. Sections 2.1 and 2.5.
• List of topics for presentation 1
• Thursday, January 11: Graphical sequences (Theorem 1.1.6 and its proof). Degree distribution (article from Scientific American handed out in class). Walks, diameter, eccentricity, connectedness. Section 1.4.
• Tuesday, January 9: Degree. Degree sequence. Degree-sum theorem. Introduction to Graphical sequences. Section 1.1.
• Thursday, January 4: Introduction. Some applications of graphs, and initial definitions. Sections 1.1, 1.3.
• Syllabus

HOME