Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!
The final exam is scheduled for Friday, Dec. 10, 10:30 am - 12:30 pm, in IT 1F6-1 (the IIT Tower, located at the NW intersection of State and 35th, the first floor auditorium).
The topics are: graph algorithms excluding minimum spanning trees, and including DFS/BFS/strongly connected components, shortest paths and network flows and applications, NP-completeness, and dynamic programming. One may also need to apply data structures as covered before midterm, or maybe selection, but will not be required to design data structures nor use amortized analysis.
Distributed in class, November: NP-completeness theory.
Distributed in class, Dec 1: the extra set of problems which might appear on the final exam .
The sixth homework version 1.1 was assigned and is due Dec. 3. It must be submitted by Dec. 8 to count (with a penalty starting Dec. 4).
The academic honesty handout and the pledge you are asked to sign and return are here.
The following lecture notes were distributed in class in August: the selection algorithm from the textbook, notes on lower bounds for sorting, Minimum Spanning Tree algorithms of Prim and Kruskal, and Minimum Spanning Tree definitions.
Here are some links: Minimum Spanning Tree visualization but keep in mind that our Prim's Algorithm differs from the one described on this web page, while Kruskal's algorithm is essentially the same. Essentialy the same with our Prim's Algorithm is the one at Prim Minimum Cost Spanning Treeh (sic), but compared to the pseudocode from the notes (and textbook), "Known" means not in Q, "Cost" is key[], and "Path" is π[].
The first homework was assigned and is due Sept. 15.
The following lecture notes were used class: Graham's scan (two pages of the textbook). https://visualgo.net/en/convexhull See also Convex Hull visualization, where there is a minor difference versus the textbook: the stack starts with Pm,P0,P1 instead of P0,P1,P2. Also ccw(P,P',P") checks if the angle P->P'->P" is counterclockwise or not.
The following lecture notes from the textbook were distributed in class in September. Regarding Fibonacci heaps, we have: Priority Queue Operations and Bounds (one page of the textbook), Pseoducode for CONSOLIDATE (from the textbook), and Pseoducode for DECREASE-KEY (from the textbook).
The second homework was assigned and is due Sept. 29.
The Splay Trees are described in detail here. We'll go through this handout in class; it comes from Dr. Dobbs (and it was once used in CS 331; note that that class does not do amortized analysis of data structures). Note however, that we, in this class, use for DELETE a different procedure: the one from binary search trees , followed by a SPLAY at the parent of the deleted node. See also binary search trees rotations . The web link binary tree visualization may help.
The third homework version 1.1 was assigned and is due Oct. 13. Also available: the extra set of problems which might appear on the midterm .
Regarding disjoint set maintance, we have union-find operations , union-find implementation, and union-find worst-case analysis version 2. Keep in mind that amortized analysis gives much better bounds. Also: pseudocode for Depth-First_Search, the edge classification for Depth-First_Search,
The midterm is scheduled for Oct. 18, during regular class hours.
The fourth homework was assigned and is due Nov. 3.
The following lecture notes from the textbook will be distributed in class in October: the Bellman-Ford algorithm and lecture notes on network flows.
The fifth homework was assigned and is due Nov. 17.
Document last modified on December 1, 2021.