Spring 2018 - CS 401 Computer Algorithms I (Call no. 41266/ 41267)
Instructor:
Ajay Kshemkalyani
Email:
ajay@uic.edu
Class meeting times: MWF 12:00-12:50pm in BH 208
Office Hours in 915 SEO:
MW 1:00-1:50pm and by appointment
Teaching Assistant: Sanket Gaurav
Email: sgaura2@uic.edu
Office hours: R 10am - 12 noon, in SEO 1330
-
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/15-) Chapter 1
- Week 2: (1/22-) Chapter 1,2,3
- Week 3: (1/29-) Chapter 3, 4; Homework 1, due Feb 12
- Week 4: (2/5-) Chapter 4
- Week 5: (2/12-) Chapter 4
- Week 6: (2/19-) Chapter 4; Homework 2, due March 5 (extended from March 2)
- Week 7: (2/26-) Chapter 5
- Week 8: (3/5-) Chapter 5; Midterm 1 on March 7, (Syllabus: Chapters 1.1 to 4.8 + slides from class)
- Week 9: (3/12-) Chapter 6
- Week 10: (3/19-) Chapter 6; Homework 3, due April 4
- Week 11: (4/2-) Chapter 7
- Week 12: (4/9-) Chapter 7; Midterm 2: April 11, (Syllabus: Chaps 1-6).
- Week 13: (4/16-) Chapter 8; Homework 4, due April 30
- Week 14: (4/23-) Chapter 8
- Week 15: (4/30-) Chapter 9
- Final exam: (as per university timetable), Tuesday (May 8), 8:00-10:00am
Syllabus: Chapters 1 to Chapter 4, Chapter 5.1-5.5, Chapter 6, Chapter 7, Chapter 8 - 8.5, 8.7 including the slides, Chapter 9
Sections to EXCLUDE: 4.9, 5.6, 7.4, 7.13, 8.6, 8.8