Messages
- July 27, 2019: webpage draft created.
- Oct. 2, 2019, Midterm 1, in class.
- Nov. 13, 2019, Midterm 2, in class.
- Dec. 16, 2019, Final, 12:30pm-2:30pm, Informatics West 107.
Description
This is an introductory graduate-level course on algorithm design and analysis, covering fundamental techniques in designing algorithms and proving bounds on their time and space complexity.
As the course focuses on the analysis (therefore mathematical aspect) of algorithms, students are expected to have a solid undergraduate mathematical background (e.g., elementary combinatorics, discrete probability, linear algebra and calculus). Students are also expected to have learned elementary algorithms, including basic data structures, basic sorting and searching, elementary graph terminology, and asymptotic analysis of time and space complexity for algorithms (i.e. big-O/Omega/Theta notation). There will be no programming requirement in this course. However, it will be very helpful to have past experience with implementation of basic algorithms and data structures.
Lecturer
Qin Zhang
Office hour: Wednesday 4pm-5pm, Luddy 3044
Email: qzhangcs@indiana.edu
Associate Instructors
Haoyu Zhang
Office hour: Tuesday 4pm-5pm, Venue: 2033JJ
Email: hz30@iu.edu
Helper: Yan Song
Office hour: Thursday 2pm-3pm; Venue: 2033KK
Email: songyan@iu.edu
Time and place
2:30pm-3:45pm, Monday/Wednesday, Informatics West 107
Texbooks
Required Textbook: [KT] Algorithm Design, J. Kleinberg, E. Tardos. Pearson Education.
Lecture notes will be posted in Canvas.
Course contents
Introduction [slides]
Greedy algorithms: interval scheduling, minimum spanning tree, shortest path
Divide and conquer: merge sort, counting inversions, closest pairs, fast fourier transform
Dynamic Programming: weighted interval scheduling, knapsack, sequence alignment, all-pair shortest path
NP-completeness
Selected topics: approximation and randomized algorithms
Grading
Assignments 30%
Five written assignments. Assignments are posted in Canvas. The answers should be typeset in LaTeX and submitted via Canvas; here is a template to start with. No extensions or late homeworks will be granted.
Exams 70%
(1) Midterm-1 20%
(2) Midterm-2 20%
(3) Final 30%
There will be NO make-up exams. If students have to miss the in-class midterm exam due to family/medical emergencies (and/or other reasons which will be granted on a case by case basis, but conference travels etc. cannot be the reason), they need to contact the instructor before the exams for permission, and their other exam grades will be re-weighted. Internship and job application interviews and paper deadlines are NOT proper reasons to miss an exam.
Course policies
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.
Prerequisites
CSCI-C241 "Discrete Structures for Computer Science", CSCI-C343 "Data Structures", and MATH-M 216 "Analytic Geometry and Calculus II" (or MATH-M 212 CALCULUS II). The prerequisites are enforced.