CS 430  FALL 2017
INTRODUCTION TO ALGORITHMS
LECTURE MONDAY/WEDNESDAY 11:25am12:40pm  113 Stuart
RECITATION FRIDAY 11:2512:15pm  113 Stuart
COURSE INFORMATION & SYLLABUS
http://www.cs.iit.edu/~cs430
Instructor: Matthew Bauer bauerm@iit.edu Office Hours Monday 1011am, Tuesday 8:3011am, Wednesday 8:309:30; Office:237B SB; 3125675148; (fax)3125675067; mailbox in CS dept(235236 SB);
TA: Xiaolang Wang xwang122@hawk.iit.edu Office Hours Monday 23pm, Friday 23: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:
Class Meetings: Meetings consist of lecture, discussion, problem solving, presentation of homework solutions and exams. Prereading the textbook, viewing the prelecture 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 prelecture videos to what lecture number it is and the prelecture quizzes. The prelecture quizzes have been incorporated into the lecture handouts.
Assignments: Homework(7 total)25%
LectureParticipation5% Exam#120% Exam#220% Exam#230%
A=90100 B=8089 C=7079 D=6069 E=059 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 email to communicate any class issues with me.
Date  Topics  Chapters  Assignment 
Monday, August 21, 2017 Wednesday, August 23, 2017 
PreLecture 01 Video (9:25) 1.Introduction to Algorithm Design, Complexity Analysis (CS430Lecture01Activities) 1.Introduction to Algorithm Design, Complexity Analysis (CS430Lecture02Activities) 
1,2,3  
Monday, August 28, 2017 Wednesday, August 30, 2017 
PreLecture 02 Video (7:41) 1.Introduction to Algorithm Design, Complexity Analysis (CS430Lecture03Activities) 2.Recurrence Relations (CS430Lecture04Activities) 
1,2,3 4.34,5 

Monday, September 04, 2017 Wednesday, September 06, 2017 
PreLecture 03 Video (9:19) Labor Day  no lecture 3.Divide & Conquer Sorting Methods  Quicksort, Heaps and Heapsort (CS430Lecture05Activities) 
6,7  HW #1 (topics 12) Fri Sept 8, 11:25am 
Monday, September 11, 2017 Wednesday, September 13, 2017 
PreLecture 04 Video (5:45) 3.Divide & Conquer Sorting Methods  Quicksort, Heaps and Heapsort (CS430Lecture06Activities) 4.Lower bound on sorting (CS430Lecture07Activities) 
6,7 8.18.3 
HW #2 (topics 34) Fri Sept 15, 11:25am 
Monday, September 18, 2017 Wednesday, September 20, 2017 
5.Medians and Order Statistics
(CS430Lecture08Activities) 6.Binary Search Trees (CS430Lecture09Activities) 
9 12.112.3 
EXAM #1 (topics 14) Fri Sept 22, 11:25am12:40pm 
Monday, September 25, 2017 Wednesday, September 27, 2017 
PreLecture 05 Video (7:07) 7.Balanced Binary Search Trees (RedBlack trees, AVL trees) (CS430Lecture10Activities) 7.Balanced Binary Search Trees (RedBlack trees, AVL trees) (CS430Lecture11Activities) 
13  
Monday, October 02, 2017 Wednesday, October 04, 2017 
PreLecture 06 Video (8:25) 8.Augmenting Data Structures (CS430Lecture12Activities) 9.Introduction to Dynamic Programming (CS430Lecture13Activities) 
14.114.2 15.215.5 
HW #3 (topics 56) Fri Oct 6, 11:25am 
Monday, October 09, 2017 Wednesday, October 11, 2017 
PreLecture 07 Video (7:25) Fall Break  no lecture 9.Introduction to Dynamic Programming (CS430Lecture14Activities) 
15.215.5  HW #4 (topics 78) Fri Oct 13, 11:25am 
Monday, October 16, 2017 Wednesday, October 18, 2017 
PreLecture 08 Video (9:17) 9.Introduction to Dynamic Programming 1 (CS430Lecture15Activities) 10.Introduction to Greedy Methods (CS430Lecture16Activities) 
15.215.5 16.116.3 

Monday, October 23, 2017 Wednesday, October 25, 2017 
10.Introduction to Greedy Methods
(CS430Lecture17Activities) 11.Amortized Analysis (CS430Lecture18Activities) 
16.116.3 17.117.2 
HW #5 (topics 910) Fri Oct 27, 11:25am 
Monday, October 30, 2017 Wednesday, November 01, 2017 
12.Fibonacci Heaps (CS430Lecture19Activities) 13.Data Structures for Disjoint Sets (CS430Lecture20Activities) 
19 21.121.2 
EXAM #2 (topics 510) Fri Nov 3 11:25am12:40pm 
Monday, November 06, 2017 Wednesday, November 08, 2017 
PreLecture 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 
PreLecture 10 Video (6:21) 15.Minimum Spanning Trees, Shortest Paths (CS430Lecture23Activities) 15.Minimum Spanning Trees, Shortest Paths (CS430Lecture24Activities) 
23,24.124.3,25.125.2  HW #6 (topics 1113) Fri Nov 17, 11:25am 
Monday, November 20, 2017 Wednesday, November 22, 2017 
15.Minimum Spanning Trees, Shortest Paths (CS430Lecture25Activities) Thanksgiving  no lecture 
23,24.124.3,25.125.2  
Monday, November 27, 2017 Wednesday, November 29, 2017 
15.Minimum Spanning Trees, Shortest Paths (CS430Lecture26Activities) Review for Final 
23,24.124.3,25.125.2  HW #7 (topics 1415) Fri Dec 1, 11:25am 
Final's Week  EXAM #3 (topics 1115) Thurs Dec 7, 810am 104 Stuart 
Copyright Matthew Bauer, CS, Illinois Institute of Technology