Messages
- September 15, 2020: webpage draft created.
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 11am-12pm, Via this Link (Zoom).
Email: qzhangcs@indiana.edu
Associate Instructors
Harshad Badiyani
Office hour: Friday 4-5pm via this Link (Zoom).
Email: hbadiyan@iu.edu
Yan Song （helper, office hour only）
Office hour: Tuesday 2-3pm via this Link (Zoom).
Email: songyan@iu.edu
Time and place
9:25am-10:40am, Monday/Wednesday. (Synchronized) lectures via Zoom (see the Canvas page for the link).
Texbooks
Required Textbook: [KT] Algorithm Design, J. Kleinberg, E. Tardos. Pearson Education.
Lecture notes will be posted on 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
Class participation 10%
Assignments 40%
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 50%
(1) Midterm 20%
(2) Final 30%
There will be NO make-up exams. If students have to miss the 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.