Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!
The final exam for Sections V04 and V06 has been scheduled for Wednesday, May 12, 5-7 PM. The exam will follow the same format as the midterm: Blackboard login for the duration of the exam, and Blackboard submission within 15 minutes after the two hour exam time.
The second extra homework for Sections V06 and V07 was assigned April 14 and is due April 28.
The lecture notes on shortest paths are available. We used Single-Source Shortest Paths visualization with the Example Graph DAG, Original Dijkstra's Algorithm and starting point 0. We also plan to use Floyd-Warshall All-Pairs Shortest Path visualization.
The sixth homework was assigned on April 21 and is due on May 5.
The project was assigned on April 8 and is due on May 7. It is available in PDF here. Here are instance01, instance02, instance03, instance04, instance05, instance06, and some solutions: greedy_solution01, greedy_solution02, greedy_solution04, greedy_solution06, and local_solution03, local_solution04, local_solution05, local_solution06. Recall that the outputs are not unique; your program can be correct and produce different answers.
The following lecture notes were used class: Graham's scan (two pages of the textbook). https://visualgo.net/en/convexhull We used 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.
One can download my pseudocode for the Knuth-Pratt-Morris algorithm. For visualization, we used Knuth-Morris-Pratt String Search, where there is a minor difference versus the textbook: the arrays start at 0 instead of 1.
The syllabus is available.
The insertion sort pseudocode, with part of the analysis, is available here .
Lecture notes on asymptotic notation are here . The first quiz is Monday Jan. 25, in class. It covers linked structures (including trees) and/or recursion, algorithmic topics from CS 331, listed as "preliminary" in the syllabus. See also Chapter 10 of the textbook.
The first homework was assigned Feb. 1 and is due Feb. 15.
The quiz of the week Feb. 1-5 is based on recursive algorithms (topic of CS 331).
The quiz of the week Feb. 8-12 is based on topics from CS 330: Big-Oh and/or graphs and both may need mathematical induction in the proof method. These topics are listed as "preliminary" in the syllabus. See Chapter 3 and Appendices A, B, C.1 of the textbook.
The academic honesty handout and the pledge you are asked to sign and return are here.
The lecture notes on sorting and heaps are here .
The lecture notes on binary search trees (corrected) , and on i binary search trees rotations and red-black trees are updated.
The second homework was assigned Feb. 15 and is due March 1 (March 5 noon is the latest for it to count, with penalty).
The web links binary tree visualization and max heap visualization were used in class. Also, for visualizing red-black trees, we used this site and for Merge: Mergesort Visualization.
The first extra homework for Sections V06 and V07 with clarifications was assigned Feb. 22 and is due March 15.
The pseudocode for the merge step of mergesort and for the partition procedure of quicksort is available here.
You can download lecture notes for recurrence relations, which include the Master Theorem.
The web link hashing visualization was used during the lecture for Hashing. However, in chaining, INSERT should take place at the start (and not the end) of the (doubly-) linked list. A variant of this programming contest problem was discussed in class after Counting Sort. The actual problem is more complicated but it can be solved with the same idea, see this online judge if you plan to submit your program (let me know if you succeded).
The web link
counting sort visualization was used in class for visualizing counting sort;
while the Java code is correct, the animation has a bug as the
display of the "Counts" array is not updated (as it should) in the last The web page
disjoint-sets data structure visualization
was used in class on March 15.
For March 17, we plan to use
this programming contest problem
as an example of problems that can be solved by a greedy algorithm.
The third homework version 1.1 was assigned
March 8, and is due March 22 (no penalty if turned in on March 24).
Lecture notes for dynamic programming are available in four parts:
part 1,
part 2,
part 3, typo corrected, and
part 4.
The web page
Matrix-Chain Multiplication
was used in class on March 22.
The fourth homework was assigned
March 24, and is due April 7.
Lecture notes for graphs are available in two parts:
part 1 and part 2.
The web page
Graph Traversal visualization
was used in class for Breadth-First Search, Depth-First Search, and Topological Sort.
Please download the lecture notes on
minimum spanning trees,
minimum spanning tree algorithms,
and
definitions for the blue rule .
We also have used
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 fifth homework was assigned
April 7 and is due April 21.
Contact the instructor at calinescu iit edu
Document last modified on April 28, 2021.