## Welcome to CS321!

### Announcements

**Important Update.** In the email about the performance summary, I had incorrectly stated the marks in the first assignment to be out of 20. The marks in Assignment 1 are out of 15 - please recalculate your overall performance accordingly. I have emailed those whose final letter grades were affected because of this.

**[25 Apr, 2016]** The grading cutoffs are as follows:

The cutoff for A+ is 95. [2]

The cutoff for A is 85. [20]

The cutoff for A- is 70. [35]

The cutoff for B is 60. [8]

The cutoff for B- is 45. [6]

The cutoff for C is 35. [2]

The numbers in the brackets indicate the number of people who obtained that grade. This was a pretty good performance overall, so congratulations!

**[25 Apr, 2016]** The class averages have turned out as follows:

Assignments 1, 2, 3: 12, 16.68, 16.4 (out of 15, 20 and 20)

Quiz 1, 2: 9.29, 15.95 (out of 25)

Midsem, Endsem: 33.01, 34.43 (out of 50)

Programming Assignment: 92.87 (out of 100)

Overall: 75.81 (out of 100)

The breakup for computing the overall grade was: 25% each for the assignments and the programming exercise, 15% each for the exams, and 20% for the better of the two quizzes.

**[25 Apr, 2016]** The questions and answers for the final exam are now available. You will recieve your grades over email by 10AM today. If you do not recieve this email, or if you notice any serious discrepancy in your grades, please get in touch with me **before 6PM today**.

### Logistics

**Course Timings.** Monday, Wednesday and Friday, 01:05 PM to 02:00 PM.

**Venue.** Block 7, Room 208.

**Office Hours.** Monday, Wednesday and Friday, 02:00 PM to 03:00 PM.
Anytime over email, by appointment, or just anytime you find me free is fine too :)

**Teaching Assistants.** Shivdutt and Supratim.

### Grading Policy

1) Assignments: 25%

2) Quizzes (best of two): 20%

3) Programming Assignments: 25%

4) Exams (equally divided between the midsems and endsems): 30%

**Programming Assignments.** The default way to submit a programming assignment is through the HackerRank platform. For those who prefer not to code (!), please submit pseudocode with a formal proof of correctness and analysis of running time instead. Pseudocode guidelines, and a format for typesetting homework in LaTeX, will be posted on this website soon. Having said all that, I'm going to repeat that being proactive about impelmenting algorithms in your favorite coding environment will stand you in good stead.

**Non-graded work.** Class participation, solving starred problems, blogging about anything related to lecture material, conributing relevant content to Wikipedia, and answering questions on platforms like CSTheory/Quora, are all desirable activities are strongly encouraged. Having said that, they **do not** affect your grade in any way. The only reason to invest your time doing these things is to have fun while also enriching your overall learning experience. :) It doesn't hurt that some of this also looks good on a CV!

### Pre-Requisites

The course is open to students at all levels and from all disciplines. The course will be as self-contained as possible. Having said that, basic programming experience will make it easier to deal with some of the assignments. Also, some mathematical maturity will help in keeping up with formalisms that come up in proofs of correctness.

Feel free to drop me a line if you have any specific questions.

### Remarks on Course Topics

Basic notions of asymptotics, and data structures. We will cover various algorithm design paradigms, such as divide and conquer, greedy, and dynamic programming. We will also introduce the notion of NP-hardness, and design exact and approximate algorithms for NP-hard problems. Easy and hard problems will often be introduced simultaneously. Apart from searching, sorting, and order statistics, problems will frequently be of a graph-theoretic flavor (traversals, shortest path, spanning trees, and so on). We also expect to explore problems with a number-theoretic or geometric flavor. The course will have a definite focus on implementation. If time permits, we will also explore other models of algorithm design: a brief peek beyond the world of worst-case analysis.

### References

The first three books are available at our library, and are listed as official course reference material. The references (4) --- (7) are freely available online. The last references are to books that are less technical than the first three, but make for great additional reading.

1) Algorithm Design , Jon Kleinberg and Éva Tardos

2) Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani

3) Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (By the way, Thomas Cormen has a more introductory book called Algorithms Unlocked. Pro tip: he's also quite active at Quora!)

4) The lecture notes of Jeff Erickson are awesome.

5) The lecture notes on this website will have additional pointers for individual lectures.

6) Tim Roughgarden's lectures (see: the MOOCs on Coursera) are roughly based on the book by Klienberg and Tardos [1].

7) The lectures of Eric Demaine (along with with various co-instructors, see 6.046 or 18.410) are based on CLRS [3].

8) Algorithms Unplugged by by Berthold Vöcking (Author, Editor), Helmut Alt (Editor), Martin Dietzfelbinger (Editor), Rüdiger Reischuk (Editor), Christian Scheideler (Editor), Heribert Vollmer (Editor), Dorothea Wagner (Editor).

9) The Power of Algorithms by by Giorgio Ausiello (Editor), Rossella Petreschi (Editor)

10) The Golden Ticket: P, NP, and the Search for the Impossible Kindle Edition by Lance Fortnow, who also blogs here.