In this course we will discuss some basic techniques for algorithm design and analysis, including:
- Sorting and searching
- Divide-and-conquer
- Dynamic programming
- Greedy algorithms
- Graph algorithms
- NP-completeness
Detailed list of topics is available in the course schedule below.
Qin Zhang
Office hour: Wednesday 3pm-4pm, Luddy 3128
Email: qzhangcs@indiana.edu
Week | Date | Section | Content | Comments |
---|---|---|---|---|
1 | Jan. 8 | 1. Introduction | Overview | intro |
1 | Jan. 10 | Big-O notations | [KT] Ch 2.2 | |
2 | Jan. 15 | No class | MLK day | |
2 | Jan. 17 | Common running times | [KT] Ch 2.4 | |
3 | Jan. 22 | 2. Graphs | Introduction to HackerRank Graph basics |
[KT] Ch 3.1 |
3 | Jan. 24 | BFS, implementation Graph representation |
[KT] Ch 3.2, 3.3 | |
4 | Jan. 29 | DFS, implementation Directed graph |
[KT] Ch 3.2, 3.3, 3.5 | |
4 | Jan. 31 | DAG, topological sorting | [KT] Ch 3.6 | |
5 | Feb. 5 | 3. Greedy | Interval scheduling | [KT] Ch 4.1 |
5 | Feb. 7 | Interval scheduling (cont.) | [KT] Ch 4.1 | |
6 | Feb. 12 | Shortest path (Dijkstra's algo) | [KT] Ch 4.4 | |
6 | Feb. 14 | Discussion of HW1&2 | ||
7 | Feb. 19 | Dijkstra's algo (cont.) | [KT] Ch 4.4 | |
7 | Feb. 21 | MST | [KT] Ch 4.5 | |
8 | Feb. 26 | MST (cont.) | [KT] Ch 4.5 | |
8 | Feb. 28 | MST (cont.) | [KT] Ch 4.6 | |
9 | Mar. 5 | Mid-term Review | Discussion of HW3 & others | |
9 | Mar. 7 | Mid-term (in class) | ||
10 | Mar. 12 | No class | Spring break | |
10 | Mar. 14 | No class | Spring break | |
11 | Mar. 19 | 4. Divide & Conquer | Mergesort | [KT] Ch 5.1 |
11 | Mar. 21 | Counting inversions | [KT] Ch 5.3 | |
12 | Mar. 26 | Closest pair | [KT] Ch 5.4 | |
12 | Mar. 28 | 5. Dynamic Programming | Weighted interval scheduling | [KT] Ch 6.1, 6.2 |
13 | Apr. 2 | Subset-sum | [KT] Ch 6.4 | |
13 | Apr. 4 | Sequence alignment | [KT] Ch 6.6 | |
14 | Apr. 9 | Sequence alignment (cont.) | [KT] Ch 6.7 | |
14 | Apr. 11 | 6. NP and Intractability | Polynomial reduction | [KT] Ch 8.1 |
15 | Apr. 16 | Polynomial reduction (cont.) | [KT] Ch 8.2 | |
15 | Apr. 18 | NP-completeness | [KT] Ch 8.3 | |
16 | Apr. 23 | NP-completeness (cont.) | [KT] Ch 8.4 | |
16 | Apr. 25 | Final Review | ||
17 | Final |
For assignments, students may discuss answers with anyone, including problem approaches and proofs. But all students must write their own proofs, and write-ups. The names of all people that you have talked to should be listed at the beginning of the first page. If a solution comes from existing papers/web/books, they must be properly cited, and you must write the solution in a way that demonstrates your understanding (simply copying the solution will be considered as plagiarism, and will result an "F" for the entire course). All deadlines are firm. No late assignments will be accepted unless there are legitimate circumstances.
For more details, see Indiana University Code of Student Rights, Responsibilities, and Conduct.