Messages
Learning outcomes and competences
After attending this course, participants should be able to
Given an algorithm, analyze its correctness and running time.
Given a problem, design a correct and efficient algorithm for it, express it in a form that a programmer can easily convert into code.
Have an idea about what problems are intractable, and basic algorithms for those that are tractable.
Know the mathematical techniques that you will need to analyze your algorithms.
Topics
In this course, we will discuss some basic techniques for algorithm design and analysis, including:
- Divide-and-conquer
- Dynamic programming
- Greedy algorithms
- Graph algorithms
Lecturer
Qin Zhang
In-person office hour: Wednesday 2-3pm, Luddy 3044
Email: qzhangcs@indiana.edu
Associate Instructors
Kaiwen Liu
Email: kaiwliu@iu.edu
Office hour: Tuesday 4:30-5:30pm, Luddy 2040 area
Time and place
9:45 AM–11:00 AM Monday/Wednesday, Myles Brand Hall (Informatics) I E130
Texbooks
Required Textbook: [KT] Algorithm Design, J. Kleinberg, E. Tardos. Pearson Education.
Tentative Schedule
- Preparation (overview, Big-O notations, some basic problems and running times, graph representation, graph traversal, topological sort)
- Greedy algorithms (interval scheduling, shortest path, MST)
- Mid-term
- Divide-and-conquer (mergesort, counting inversions, closest pair, integer multiplication)
- Dynamic programming (weighted interval scheduling, subset sum, sequence alignment)
- Final
Grading
Attendance 10%
Conducting five random attendance checks:
0 or 1 absence: 10 points
2 absences: 8 points
3 absences: 5 points
4 absences: 2 points
5 absences: 0 points
If you are sick (w/ Doctors Note), please inform the instructor in advance. If you have an extended absence due to a situation beyond your control (e.g. long-term hospitalization, concussion), please discuss with the instructors as soon as possible.
Assignments 30%
Five written assignments. Assignments are posted in Canvas. The answers should be submitted via Canvas . Please typeset in your favorite software (best in Latex).
No extensions will be granted (unless emergencies; medical emergencies need doctor's notes covering the deadline dates). For late assignments, we use the following rule: One day late, deduct 10% of the points; two days late, deduct 30% of the points; more than two days late, deduct 100% of the points.
Exams 60%
(1) Mid-term 25%
(2) Final 35%
There will be NO make-up exams. If students have to miss the in-class midterm exam due to medical emergencies (and/or other reasons which will be granted on a case by case basis; medical emergencies need doctor's notes covering the exam dates), 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/chatGPT/bard, 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.