CS 430 - FALL 2017
LECTURE MONDAY/WEDNESDAY 11:25am-12:40pm - 113 Stuart
RECITATION FRIDAY 11:25-12:15pm - 113 Stuart


Instructor: Matthew Bauer bauerm@iit.edu Office Hours Monday 10-11am, Tuesday 8:30-11am, Wednesday 8:30-9:30; Office:237B SB; 312-567-5148; (fax)312-567-5067; mailbox in CS dept(235-236 SB); 

TA: Xiaolang Wang xwang122@hawk.iit.edu Office Hours Monday 2-3pm, Friday 2-3:30pm in SB 004

Textbooks: (Required) Introduction to Algorithms, 3nd edition, by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, MIT Press, 2009.

Current Catalog Description: Introduction to the design, behavior, and analysis of computer algorithms. Searching, sorting, and combinatorial algorithms are emphasized. Worst case and average bounds on time and space usage. Prerequisites: ((CS330 or MATH230) and CS331) or CS401 or CS403.

Course Goals: Students should be able to:

  1. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.
  2. Determine the time complexity of simple algorithms, deduce the recurrence relations that describe the time complexity of recursively defined algorithms, and solve simple recurrence relations.
  3. Design algorithms using the greedy, dynamic programming, divide-and-conquer strategies.
  4. Design algorithms using at least one other algorithmic strategy from the list of topics for this unit.
  5. Use and implement the fundamental abstract data types -- specifically including heaps, balanced binary search trees, and graphs -- necessary to solve algorithmic problems efficiently.
  6. Solve problems using techniques learned in the design of sequential search, binary search, O(N log N) sorting algorithms, and fundamental graph algorithms, including depth-first and breadth-first search, single-source and all-pairs shortest paths, and at least one minimum spanning tree algorithm.
  7. Demonstrate the following abilities: to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in simple programming contexts.
  8. Communicate theoretical and experimental analyses of a set of algorithms (i.e. sorting) in a lab report format.
  9. Understand the notions of NP-completeness, NP-hardness.

Class Meetings: Meetings consist of lecture, discussion, problem solving, presentation of homework solutions and exams. Pre-reading the textbook, viewing the pre-lecture videos, preparing your notes on the lecture handouts, and regular class attendance is essential to success. Students are expected to be prepared and to actively participate in class activities. Ignore the references in the pre-lecture videos to what lecture number it is and the pre-lecture quizzes. The pre-lecture quizzes have been incorporated into the lecture handouts.

Assignments: Homework(7 total)-25% LectureParticipation-5% Exam#1-20% Exam#2-20% Exam#2-30%
A=90-100 B=80-89 C=70-79 D=60-69 E=0-59    NO LATE HOMEWORK ACCEPTED! NO EXTRA CREDIT!
Failure to attend class and participate in class discussions will result in a lowering your final grade by one letter grade. Also, the instructor reserves the right to fail any student that receives a failing score on any exam regardless of the scores on the other assignments.

Ethics: Any behavior on the homework, projects, or exams that could be considered copying or cheating will result in an immediate zero on the assignment for all parties involved, failure in the class, and notification of the Undergraduate or Graduate Dean's Office.

Communication is critical to the success and satisfaction of the learning experience. Please use e-mail to communicate any class issues with me.

Date Topics Chapters Assignment
Monday, August 21, 2017
Wednesday, August 23, 2017
Pre-Lecture 01 Video (9:25)
1.Introduction to Algorithm Design, Complexity Analysis (CS430Lecture01Activities)
1.Introduction to Algorithm Design, Complexity Analysis (CS430Lecture02Activities)
Monday, August 28, 2017
Wednesday, August 30, 2017
Pre-Lecture 02 Video (7:41)
1.Introduction to Algorithm Design, Complexity Analysis (CS430Lecture03Activities)
2.Recurrence Relations (CS430Lecture04Activities)
Monday, September 04, 2017
Wednesday, September 06, 2017
Pre-Lecture 03 Video (9:19)
Labor Day - no lecture
3.Divide & Conquer Sorting Methods - Quicksort, Heaps and Heapsort (CS430Lecture05Activities)
6,7 HW #1 (topics 1-2)
Fri Sept 8, 11:25am
Monday, September 11, 2017
Wednesday, September 13, 2017
Pre-Lecture 04 Video (5:45)
3.Divide & Conquer Sorting Methods - Quicksort, Heaps and Heapsort (CS430Lecture06Activities)
4.Lower bound on sorting (CS430Lecture07Activities)
HW #2 (topics 3-4)
Fri Sept 15, 11:25am
Monday, September 18, 2017
Wednesday, September 20, 2017
5.Medians and Order Statistics (CS430Lecture08Activities)
6.Binary Search Trees (CS430Lecture09Activities)
EXAM #1 (topics 1-4)
Fri Sept 22, 11:25am-12:40pm
Monday, September 25, 2017
Wednesday, September 27, 2017
Pre-Lecture 05 Video (7:07)
7.Balanced Binary Search Trees (Red-Black trees, AVL trees) (CS430Lecture10Activities)
7.Balanced Binary Search Trees (Red-Black trees, AVL trees) (CS430Lecture11Activities)
Monday, October 02, 2017
Wednesday, October 04, 2017
Pre-Lecture 06 Video (8:25)
8.Augmenting Data Structures (CS430Lecture12Activities)
9.Introduction to Dynamic Programming (CS430Lecture13Activities)
HW #3 (topics 5-6)
Fri Oct 6, 11:25am
Monday, October 09, 2017
Wednesday, October 11, 2017
Pre-Lecture 07 Video (7:25)
Fall Break - no lecture
9.Introduction to Dynamic Programming (CS430Lecture14Activities)
15.2-15.5 HW #4 (topics 7-8)
Fri Oct 13, 11:25am
Monday, October 16, 2017
Wednesday, October 18, 2017
Pre-Lecture 08 Video (9:17)
9.Introduction to Dynamic Programming 1 (CS430Lecture15Activities)
10.Introduction to Greedy Methods (CS430Lecture16Activities)
Monday, October 23, 2017
Wednesday, October 25, 2017
10.Introduction to Greedy Methods (CS430Lecture17Activities)
11.Amortized Analysis (CS430Lecture18Activities)
HW #5 (topics 9-10)
Fri Oct 27, 11:25am
Monday, October 30, 2017
Wednesday, November 01, 2017
12.Fibonacci Heaps (CS430Lecture19Activities)
13.Data Structures for Disjoint Sets (CS430Lecture20Activities)
EXAM #2 (topics 5-10)
Fri Nov 3 11:25am-12:40pm
Monday, November 06, 2017
Wednesday, November 08, 2017
Pre-Lecture 09 Video (9:19)
14.Graphs, Depth First Search, Breadth First Search (CS430Lecture21Activities)
14.Graphs, Depth First Search, Breadth First Search (CS430Lecture22Activities)
appendix B.4, 22
Monday, November 13, 2017
Wednesday, November 15, 2017
Pre-Lecture 10 Video (6:21)
15.Minimum Spanning Trees, Shortest Paths (CS430Lecture23Activities)
15.Minimum Spanning Trees, Shortest Paths (CS430Lecture24Activities)
23,24.1-24.3,25.1-25.2 HW #6 (topics 11-13)
Fri Nov 17, 11:25am
Monday, November 20, 2017
Wednesday, November 22, 2017
15.Minimum Spanning Trees, Shortest Paths (CS430Lecture25Activities)
Thanksgiving - no lecture
Monday, November 27, 2017
Wednesday, November 29, 2017
15.Minimum Spanning Trees, Shortest Paths (CS430Lecture26Activities)
Review for Final
23,24.1-24.3,25.1-25.2 HW #7 (topics 14-15)
Fri Dec 1, 11:25am
Final's Week     EXAM #3 (topics 11-15)
Thurs Dec 7, 8-10am
104 Stuart

Copyright Matthew Bauer, CS, Illinois Institute of Technology