### Messages

• Feb. 19, Mid-term 1, in class.
• Apr. 8, Mid-term 2, in class.
• May 8, 8-10am, Final Due to COVID-19, the final exam will be a take-home exam, from 12:00am to 11:59pm on May 8. Exam paper will be posted on Canvas; answers should be typeset and submitted via Canvas.

### 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.

### Course summary

In this course we will discuss some basic techniques for algorithm design and analysis, including:
- Sorting and searching
- Divide-and-conquer
- Dynamic programming
- Greedy algorithms
- Graph algorithms
- NP-completeness
See an introduction

### Lecturer

Qin Zhang
Office hour: Wednesday 4-5pm, Luddy 3044
Email: qzhangcs@indiana.edu

Associate Instructors
Office hour: Monday 4-5pm, Info East 310A

Office hour: Thursday 4:30-5:30pm, Luddy 3040

• Jong Sung Park
Office hour: Tuesday 2-3pm, Luddy 3040
Email: jp109@iu.edu

• You can also talk to
• Yan Song
Office hour: Friday 10-11am, Luddy 2033KK
Email: songyan@iu.edu

• ### Time and place

9:30am-10:45am Monday/Wednesday, Myles Brand Hall (Informatics) E130

### Texbooks

Required Textbook: [KT] Algorithm Design, J. Kleinberg, E. Tardos. Pearson Education.
Supplementary Textbook: [CLRS] Introduction to algorithms, T. Cormen, C.Leiserson, R. Rivest, C. Stein. 3rd edition. MIT

• #### Assignments 30% 40%

Six written assignments. Assignments are posted in Canvas, and are due before class on the due date, in hard copy. If you can, typeset in your favorite software and bring printed hard copy to class. If you are handwriting, make sure it is legible.
No extensions or late homeworks will be granted.

• #### Exams 70%

(1) Mid-term 20%
(2) Mid-term 20%
(3) Final 30%
Final 40% 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), 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.