CS 430-01 Introduction to Algorithms - Fall 2018.

Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!


The sixth quiz is Friday, Nov. 16. It is based on (unweighted) graphs and dynamic programming.

The sixth homework was assigned Nov. 15, and is due Nov. 29. This homework must be turned in before the final exam!

The lecture notes on shortest paths are available.

The Registrar has scheduled the final exam for Monday Dec 3, 2018 2-4 p.m. in PS 111.

Topics for the final exam include: Greedy Algorithms, Dynamic Programming, Graph Algorithms, Minimum Spanning Trees and Shortest Paths in graphs. Data structures and sorting may be needed (but only for using these structures, not for designing and implementing them). Relevant notes from the class will be provided.

The project (version 1.01) was assigned Nov. 6 and is due Nov. 26. It is available in PDF here. Here are instance01, instance02, instance03, instance04, instance05, instance06, instance07, instance08, instance09, and later we will post some solutions: greedy_solution01, greedy_solution02, greedy_solution03, greedy_solution04, greedy_solution05, greedy_solution06, greedy_solution07, greedy_solution08, greedy_solution09, and local_solution01, local_solution02, local_solution03, local_solution04, local_solution05, local_solution06, local_solution07, local_solution08, local_solution09. Recall that the outputs are not unique; your program can be correct and produce different answers. For the project, the late policy is as follows: 5% penalty Wednesday, 10% Friday, and 15% Monday before the exam starts. Once the final exam starts, the project will not be accepted.

Please download and print lecture notes on minimum spanning trees, minimum spanning tree algorithms, and definitions for the blue rule .

The fifth homework was assigned Nov. 1 and is due Nov. 15.


Archive

The first quiz is Friday, August 24. 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 second quiz is Friday, August 31. It covers 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 syllabus version 1.1 is available.

The insertion sort pseudocode, with part of the analysis, is available here .

Lecture notes on asymptotic notation are here .

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 third quiz is Friday, September 21. It is based on the data structures covered in lectures.

The lecture notes on binary search trees , and on binary search trees rotations are posted.

I found on the web the following lecture notes in 2-3 trees from U.Southern California, part 1 and lecture notes in 2-3 trees from U.Southern California, part 2.

The first homework was assigned Aug. 30 and is due Sept. 13.

The second homework was assigned Sept. 13 and is due Sept. 27.

The fourth quiz is Friday, 5. It is based on the solving recurrence relations.

The third homework was assigned Sept. 27 and is due Oct. 9.

The pseudocode for the merge step of mergesort and for the partition procedure of quicksort is available here.

Here is the queens collision problem discussed in class.

You can download lecture notes for recurrence relations, which include the Master Theorem.

You can download the high-level pseudocode for the greedy multiple-machines scheduling algorithm..

Lecture notes for dynamic programming are available in four parts: part 1, part 2, part 3, part 4.

The fifth quiz is Friday, Nov. 2. It is based on dynamic programming.

The fourth homework was assigned Oct. 18 and is due Nov. 1.

Lecture notes for graphs are available in two parts: part 1 and part 2.

Contact the instructor at calinescu iit edu

Document last modified on Nov. 14, 2018.