Jia Liu

COM S 311: Design and Analysis of Algorithms
_{^{(Spring 2020, Section B)}}
_{^{[Link
to Canvas]}}

Personnel

Instructor: Jia (Kevin) Liu, Assistant Professor, Dept. of Computer Science
Contact: 209 Atanasoff Hall, jialiu@iastate.edu
Time & Location: Tue/Thu 3:40pm -- 5:00pm, 0124 Ross Hall
Office Hours: Thu 11am -- 12pm

Course Objectives

- Know a set of standard algorithms (and data structures) and be able to model a problem to use them.
- Gain a strong foundation in designing algorithms based on common techniques, including greedy, divide and conquer, dynamic programming, etc.
- Be able to reason about correctness of algorithms, either by proof or providing a counterexample.
- Be able to recognize intractable problems and have an idea on how to develop approximation algorithms.
- Be able to implement algorithms given their description.

Course Materials

- There is no required textbook.
- Recommended Book 1: [KT] J. Kleinberg and E. Tardos, "Algorithm Design," Pearson, 2005.
- Recommended Book 2: [CLRS] T. Corman, C. Leiserson, R.L. Rivest, and C.E. Stein, "Introduction to Algorithms," MIT Press, 2009.

Homework and Programming Assignments

- Home works and programming assignments will be assigned over the semester.
- There will be around 5-8 home works and 2 programming assignments. A programming assignment and a homework might be assigned at the same time.
- All programming assignment must be written in Java and submitted electronically to the Canvas system. Homework can be written or typed.
- Homeworks should be submitted via Canvas. Homework discussions should go to Piazza (sign-up link here).

Exams

There are two midterms and a final exam. Dates for midterms are Feb. 27 and Apr. 7. The date for final exam is TBD.

Grading Policy

- Homework: 15%; Programing Assignments: 20%; Midterm Exam 1: 20%; Midterm Exam 2: 20%; Final Exam: 25%

Late Policy

Without the consent of the instructor, 1-day late homework submission will incur 25% penalty, and late submission beyond 1 day will result in a grade of zero. In the case of an emergency (sudden sickness, family problems, etc.), an after-the-fact notice is acceptable. But we emphasize that this is reserved for true emergencies.

Schedule

Here is an estimated class schedule, which is subject to change depending on lecture progress and/or class interests. Please check for latest adjustments.

Class	Date	Topics	Lecture Topics	Lecture Notes	Assignments
1	Jan. 14	Basic Algorithms Analysis	Big-O Analysis Basic Proof Techniques for Correctness	Lecture 1
2	Jan. 16
3	Jan. 21
4	Jan. 23
5	Jan. 28	Common Data Structures	BST: Add/Delete, Search, Max/Min Balancing BST: Red-Black Tree, Treaps Hashing Functions and Applications Heaps: Max/Min Heaps, Maintain&Construct	Lecture 2
6	Jan. 30
7	Feb. 4
8	Feb. 6
9	Feb. 11
10	Feb. 13
11	Feb. 18	Searching & Sorting (feat. Divide-and-Conquer)	Merge Sort and Quick Sort	Lecture 3
12	Feb. 20
13	Feb. 25
Midterm Exam 1: Feb. 27, 8:15-9:45pm
14	Mar. 3		Selection
15	Mar. 5	Graph Algorithms	Data Structures for Graphs BFS, DFS, and Topological Sort Strongly Connected Components	Lectures 4
16	Mar. 10
17	Mar. 12
Spring Break
18	Mar. 24
19	Mar. 26	Greedy Algorithms	Interval Scheduling, Minimum Spanning Trees Shortest Path Problems	Lecture 5
20	Mar. 31
21	Apr. 2
Midterm Exam 2: Apr. 7, 8:15-9:45pm
22	Apr. 9
23	Apr. 14	Dynamic Programming	Weighted Interval Scheduling Segmented Least Squares, Knapsack, Longest Common Subsequence, Edit Distance Bellman-Ford Shortest Path Problem	Lecture 6
24	Apr. 16
25	Apr. 21
26	Apr. 23
27	Apr. 28	NP	Basics of NP-Completeness, Reduction	Lecture 7
28	Apr. 30	Final Review	Topics since Exam 2	Final Review
Final Exam: TBD

Academic Integrity

This course will follow ISU's Code of Academic Conduct. Discussions of homework assignments and final projects are encouraged. However, what you turn in must be your own. You should not directly copy solutions from others. Any reference (including online resources) used in your solution must be clearly cited.