Messages
 Oct. 26, 2017: webpage draft created.
 Jan. 14, 2018: assignment 1 posted, due date Jan. 29, 2018, in class.
 Jan. 28, 2018: assignment 2 posted, due date Feb. 12, 2018, in class.
 Feb. 11, 2018: assignment 3 posted, due date Feb. 28, 2018, in class.
 Mar. 7, 2018, midterm, in class.
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
 Divideandconquer
 Dynamic programming
 Greedy algorithms
 Graph algorithms
 NPcompleteness
Detailed list of topics is available in the course schedule below.
Lecturer
Qin Zhang
Office hour: Wednesday 3pm4pm, Luddy 3128
Email: qzhangcs@indiana.edu
Associate Instructors
Erfan Sadeqi Azer
Office hour: Tuesday 2pm3pm, Luddy 3118A
Email: esadeqia@indiana.edu
Adithya Vadapalli
Office hour: Friday 3pm4pm, Luddy 3033E
Email: vadit422@gmail.com
You can also talk to
Haoyu Zhang
Office hour: Thursday 4pm5pm, Luddy 3139C
Email: hz30@umail.iu.edu
Time and place
1:00pm2:15pm Monday/Wednesday, Ballantine Hall 305
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
Course schedule
(subject to adjustments as we go along; [KT] denotes the textbook by Kleinberg and Tardos).
1 
Jan. 8 
1. Introduction 
Overview 
intro 
1 
Jan. 10 

BigO notations 
[KT] Ch 2.2 
2 
Jan. 15 

No class 
MLK day 
2 
Jan. 17 

Common running times 
[KT] Ch 2.4 
3 
Jan. 22 
2. Graphs 
Introduction to HackerRank Graph basics 
[KT] Ch 3.1 
3 
Jan. 24 

BFS, implementation Graph representation 
[KT] Ch 3.2, 3.3 
4 
Jan. 29 

DFS, implementation Directed graph 
[KT] Ch 3.2, 3.3, 3.5 
4 
Jan. 31 

DAG, topological sorting 
[KT] Ch 3.6 
5 
Feb. 5 
3. Greedy 
Interval scheduling 
[KT] Ch 4.1 
5 
Feb. 7 

Interval scheduling (cont.) 
[KT] Ch 4.1 
6 
Feb. 12 

Shortest path (Dijkstra's algo) 
[KT] Ch 4.4 
6 
Feb. 14 
(By Adithya) 
Discussion of HW1&2 

7 
Feb. 19 

Dijkstra's algo (cont.) 
[KT] Ch 4.4 
7 
Feb. 21 

MST (cont.) 
[KT] Ch 4.5 
8 
Feb. 26 

MST (cont.) 
[KT] Ch 4.5 
8 
Feb. 28 
4. Divide & Conquer 
Mergesort 
[KT] Ch 5.1 
9 
Mar. 5 
Midterm Review 
Discussion of HW3 

9 
Mar. 7 
Midterm (in class) 


10 
Mar. 12 

No class 
Spring break 
10 
Mar. 14 

No class 
Spring break 
Grading
Assignments 15%
About 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.
Projects 15%
You will be asked to solve a question from HackerRank website. You will have the choice over which programming language to use. You will write a report for your experience. Details can be found in this instruction.
Exams 70%
(1) Midterm 30%
(2) Final 40%
There will be NO makeup exams. If students have to miss the inclass 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 reweighted. 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 writeups. 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
CSCIC241 "Discrete Structures for Computer Science", CSCIC343 "Data Structures", and MATHM 216 "Analytic Geometry and Calculus II" (or MATHM 212 CALCULUS II). The prerequisites are enforced.