In this course we will discuss some basic techniques for algorithm design and analysis, including:
1. Sorting and searching
2. Divide-and-conquer
3. Dynamic programming
4. Greedy algorithms
5. Graph algorithms
6. NP-completeness
Detailed list of topics is available in the course schedule below.
Qin Zhang
Office hour: Wednesday 3pm-4pm, LH430A
Email: qzhangcs@indiana.edu
Week | Date | Section | Content | Comments |
---|---|---|---|---|
1 | Jan. 9 | 1. Introduction | Overview, efficiency | intro |
1 | Jan. 11 | Big-O notations | [KT] Ch 2.2 | |
2 | Jan. 16 | No class | MLK day | |
2 | Jan. 18 | Common running times | [KT] Ch 2.4 | |
3 | Jan. 23 | 2. Graphs | Basics | [KT] Ch 3.1 |
3 | Jan. 25 | BFS, implementation Graph representation |
[KT] Ch 3.2, 3.3 | |
4 | Jan. 30 | Testing bipartiteness DFS, implementation |
[KT] Ch 3.2, 3.3 | |
4 | Feb. 1 | DAG, topological sorting | [KT] Ch 3.6 | |
5 | Feb. 6 | 3. Greedy | Interval scheduling | [KT] Ch 4.1 |
5 | Feb. 8 | Interval scheduling (cont.) | [KT] Ch 4.1 | |
6 | Feb. 13 | Shortest path (Dijkstra's algo) | [KT] Ch 4.4 | |
6 | Feb. 15 | Dijkstra's algo (cont.) | [KT] Ch 4.4 | |
7 | Feb. 20 | Minimum Spanning Tree (MST) | [KT] Ch 4.5 | |
7 | Feb. 22 | MST (cont.) | [KT] Ch 4.5 | |
8 | Feb. 27 | MST (cont.) | [KT] Ch 4.5 | |
8 | Mar. 1 | 4. Divide & Conquer | Mergesort | [KT] Ch 5.1 |
9 | Mar. 6 | Counting inversions | [KT] Ch 5.3 | |
9 | Mar. 8 | Closest pair | [KT] Ch 5.4 | |
10 | Mar. 13 | No class | Spring break | |
10 | Mar. 15 | No class | Spring break | |
11 | Mar. 20 | Mid-term Review | ||
11 | Mar. 22 | Mid-term | ||
12 | Mar. 27 | 5. Dynamic Programming | Weighted interval scheduling | [KT] Ch 6.1, 6.2 |
12 | Mar. 29 | Subset-sum | [KT] Ch 6.4 | |
13 | Apr. 3 | Sequence alignment | [KT] Ch 6.6 | |
13 | Apr. 5 | Sequence alignment (cont.) | [KT] Ch 6.7 | |
14 | Apr. 10 | 6. NP and Intractability | Polynomial reduction | [KT] Ch 8.1 |
14 | Apr. 12 | Polynomial reduction (cont.) | [KT] Ch 8.2 | |
15 | Apr. 17 | NP-completeness | [KT] Ch 8.3 | |
15 | Apr. 19 | NP-completeness | [KT] Ch 8.4 | |
16 | Apr. 24 | Final Review I | ||
16 | Apr. 26 | Final Review II | ||
17 | May 5 | 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.