Spring 2020 - CS 401 Computer Algorithms I (Call no. 20667/ 17455)
Instructor:
Ajay Kshemkalyani
Email:
ajay@uic.edu
Class meeting times: TR 3:30-4:45pm in TBH 180F
Office Hours in 915 SEO:
T 5:00-5:50pm and by appointment
Teaching Assistant: Neshat Mohammadi
Email: nmoham24@uic.edu
Office hours: W 10:00 - 12:00 noon in TBH 175
Undergrad TA: Shin Imai
Email: simai2@uic.edu
Office hours: T 1-3pm, Thurs 12-2pm, F 3-5pm in CS Student Lounge
-
Text book: Algorithm Design, by J. Kleinberg, and E. Tardos, Pearson/Addison-Wesley, 2006
- Lecture slides in PDF
-
Auxiliary notes and web links:
Topics
- Some representative problems
- Stable matching type problems
- Five representative problems
- Basics of Algorithm Analysis
- Computational Tractability
- Asymptotic Order of Growth
- Common Running Times
- Graphs
- Basic Definitions and Applications
- Graph Traversal
- Testing Bipartiteness
- Connectivity in Directed Graphs
- DAGs and Topological Ordering
- Greedy Algorithms
- Interval Scheduling
- Interval Partitioning
- Scheduling to Minimize Lateness
- Optimal Caching
- Shortest Paths in a Graph
- Huffman Codes
- Coin Changing Problems
- Selecting Breakpoints
- Minimum Spanning Tree
- Clustering
- Divide and Conquer
- Mergesort
- Counting Inversions
- Closest Pair of Points
- Integer Multiplication
- Matrix Multiplication
- Convolution and FFT (if time permits)
- Dynamic programming
- Weighted Interval Scheduling
- Segmented Least Squares
- Knapsack Problem
- RNA Secondary Structure
- Sequence Alignment
- Shortest Paths: Bellman-Ford algorithm, Distance Vector Protocols
- Detecting Negative Cycles in a Graph
- Network Flow
- Maximum Flow and Minimum Cut
- Ford-Fulkerson Algorithm
- Bipartite Matching Problem
- Disjoint Paths in Graphs
- Survey Design
- Airline Scheduling
- Image Segmentation
- Project Selection
- Baseball Elimination
- Computational intractability
- Polynomial-Time Reductions
- Definition of complexity classes P,NP,EXP
- NP completeness
- NP-Complete Problems
- co-NP and the Asymmetry of NP
- NP-completeness reductions
- The class PSPACE
- Approximation algorithms
- Randomized algorithms
CS 251; or C or better in Stat 381 and MCS 360
This course focuses on theoretical principles. There will be no programming. We expect to have about 4 homeworks.
The following is a tentative breakup of the evaluation scheme
and is subject to changes as the course progresses.
- 2 Midterms (20% each)
- Final (40%)
- Homeworks (20%)
The final grade is on the curve, i.e., this is relative grading - how you
perform with respect to the others in the class.
TENTATIVE course progress chart:
Will be updated as we progress.
- Week 1: (1/13-) Chapter 1
- Week 2: (1/20-) Chapter 1,2,3
- Week 3: (1/27-) Chapter 3, 4,
Homework 1, due Thurs Feb 6, 10am in Gradescope
- Week 4: (2/3-) Chapter 4
- Week 5: (2/10-) Chapter 4
- Week 6: (2/17-) Chapter 4,
Homework 2, due Thurs Feb 27, 10am in Gradescope
- Week 7: (2/24-) Chapter 5
- Week 8: (3/2-) Chapter 5; Midterm 1 on March 5, (Syllabus: Chapters 1.1 to 4.8 + slides from class) in class during class time
- Week 9: (3/9-) Chapter 5
- Week 10: (3/16-) Classes cancelled, this is extended spring break
- Week 11: (3/30-) Chapter 6; Homework 3, due Wednesday April 15, 10am in Gradescope
- Week 12: (4/6-) Chapter 6; Midterm 2: April 9, (Syllabus: Chapters 1.1 to 4.8 + Chapters 5.1 to 5.5 + slides from class)
Midterm 2 (April 9), released 3:15pm, due 5:00pm in Gradescope
- Week 13: (4/13-) Chapter 6, Chapter 8
Homework 4, due Thursday April 30, 11pm in Gradescope
- Week 14: (4/20-) Chapter 8
- Week 15: (4/27-) Chapter 8
- Final exam: (as per university timetable), Friday (May 8), 12:30-3:00pm
Final exam, released 12:30pm, due 3:15pm in Gradescope
We will hold it on-line, submit solutions thu Gradescope, like a Homework. Will be released at 12:30pm, Gradescope upload deadline 3:15pm
Syllabus: Chapters 1 to Chapter 4, Chapter 5.1-5.5, Chapter 6, Chapter 8 - 8.5, including the slides
Sections to EXCLUDE: 4.9, 5.6, 8.6 and onwards.