Spring 2023 - CS 401 Computer Algorithms I
Instructor:
Ajay Kshemkalyani
Email: first_name@uic.edu
Class meeting times: TR 12:30-1:45pm in classroom; (however, we may meet in Blackboard Collaborate if weather is bad)
Office Hours in Blackboard Collaborate:
T 4:00-4:45pm
Discussion Fourm: Piazza
Homework submissions: Gradescope
Teaching Assistant: Danyal Saeed
Email: dsaeed3@uic.edu
Office hours: T 10:30-12noon, R 2:00-3:30pm, in TBH 175
-
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 - (weighted) interval scheduling, bipartite matching, independent set, competitive facility location
- Basics of Algorithm Analysis
- Computational Tractability
- Asymptotic Order of Growth
- Common Running Times
- Graphs
- Basic Definitions and Applications
- Graph Traversal - BFS and DFS
- 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
- General recurrence relations and master theorem
- 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 (if time permits)
- Randomized algorithms (if time permits)
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-5 homeworks.
The following is a tentative breakup of the evaluation scheme
and is subject to changes as the course progresses.
- Midterm (20%)
- Final (30%)
- Homeworks (50%)
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: Chapter 1
- Week 2: Chapter 1
- Week 3: Chapter 2,3
Homework 1, due Fri Feb 3, 11:59pm in Gradescope
- Week 4: Chapter 3
- Week 5: Chapter 4
Homework 2, due Fri Feb 17, 11:59pm in Gradescope
- Week 6: Chapter 4
Homework 3, due Fri Mar 3, 11:59pm in Gradescope
- Week 7: Chapter 4, 5
- Week 8: Chapter 5
- Week 9: Chapter 5
- Week 10:
Chapter 5
Midterm on March 16. Syllabus: Chapters 1-4 (exclude 4.9)
- Week 11: Chapter 6
Homework 4, due Fri Apr 14, 11:59pm in Gradescope
- Week 12: Chapter 6
- Week 13: Chapter 6, 8
- Week 14: Chapter 8
Homework 5, due Thu Apr 27, 11:59pm in Gradescope
- Week 15: Chapter 8
- Week 16 Final exam: as per schedule, Fri May 5, 8:00-10:00am in regular classroom LC B1
Syllabus: Chapters 1 to Chapter 4, Chapter 5.1-5.5, Chapter 6, Chapter 8.1-8.5, 8.7, and including all the slides covered in class
Sections to EXCLUDE: 4.9, 5.6, 8.6, 8.8 onwards.
Face Masks: Masks covering both the mouth and the nose must be worn at all times by all students, faculty, and staff while inside any campus building regardless of vaccination status. If you do not wear a mask, you will be asked to leave the classroom and not allowed back in class unless or until you wear a mask.
If you have forgotten your mask, you may pick one up from one of the student information desks on campus during the first two weeks of campus. Students who do not comply with the mask-wearing policy will be reported to the Dean of Students. Eating and drinking are not allowed in classrooms.