Spring 2013 - CS 401 Computer Algorithms I (Call no. 17455/20667)
Instructor:
Ajay Kshemkalyani
Email:
ajayk@cs.uic.edu
Class meeting times: T,R 12:30-1:45pm in BH 317
We may need to set up a few extra class meetings to make up for any
of the regular meetings we miss due to my travel.
Office Hours in 915 SEO:
T,R 3:30-4:30pm and by appointment
Teaching Assistant: Lakshmi Kaligounder
Email: lkalig2@uic.edu
Office hours: M: 12:30am-2:00pm, R: 10:30am-12noon in SEO 932
-
Text book: Algorithm Design, by J. Kleinberg, and E. Tardos, Pearson/Addison-Wesley, 2006
-
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
- Approximation algorithms
- Randomized algorithms
CS 202; 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 5 homeworks.
The following is a tentative breakup of the evaluation scheme
and is subject to changes as the course progresses.
- 2 Midterms (40%)
- 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.
Final grades
TENTATIVE course progress chart:
Will be updated as we progress.
- Week 1: (1/14-) Chapter 1
- Week 2: (1/21-) Chapter 1
- Week 3: (1/2-) Chapter 2, 3, Homework 1 assigned, due Feb 7
- Week 4: (2/4-) Chapter 3, 4
- Week 5: (2/11-) Chapter 4, Homework 2 assigned, due Feb 21
- Week 6: (2/18-) Chapter 4
- Week 7: (2/25-) Chapter 4, 5
- Week 8: (3/4-) Midterm 1 on March 5, (Syllabus: Chapters 1.1 to 4.8 + slides from class). Chapter 5
- Week 9: (3/11-) Chapter 5, Chapter 6
- Week 10: (3/18-) Chapter 6, Homework 3 assigned, due Apr 2
- SPRING BREAK: (3/25-)
- Week 11: (4/1-) Chapter 6, 7.1-7.3
- Week 12: (4/08-) Midterm 2: April 9, (Syllabus: Chaps 1-6). Chapter 7.1-7.3
- Week 13: (4/15-) Chapter 8, Homework 4 assigned, due Apr 30
- Week 14: (4/22-) Chapter 8
- Week 15: (4/29-) Chapter 8
- Final exam: on Friday May 10, 8:00-10:00am in BH 317
Syllabus: Chapters 1 to Chapter 4, Chapter 5.1-5.5, Chapter 6, Chapter 7.1-7.3, Chapter 8 - 8.5, 8.7 including the slides, (syllabus updated May 2)
cs 401 Old Grades in the past and
some other cs 401 Old Grades in the past.