Instructor | Raghu Meka |

Lecture | MW 12 - 1:50 PM; Rolfe Hall 1200 |

Discussion | TBD |

Website | Here. |

Piazza | Class page. |

Syllabus | See syllabus below. |

Office hours | Instructor: M 3:30 - 4:30; W 2:30 - 3:30. EVI, 464. |

TAs: Check the Piazza webpage | |

Prerequisites | CS32, Math 61, Math 180 |

Textbook | Algorithm Design, Kleinberg and Tardos, 2005. |

(A direct link to the calendar is here.)

Transcript of lectures 1-7. Transcript of lectures 8 to 12. Transcript of lectures 13 onward. The lectures are being recorded and are available via CCLE.

Homework 1. Due April 16th, 6PM.

Homework 2. Due April 23rd, 6PM.

Homework 3. Due May 7, 6PM.

Homework 4. Due May 14, 6PM.

Homework 5. Due May 29, 6PM.

Homework 6. Due June 8, 10PM.

We will use piazza for the course (to ask/answer questions, to post announcements, homework etc.,). You can signup here. The class page is here.

The course will cover the basics of design and analysis of algorithms. The primary goal of the course is to develop ''algorithmic thinking''. Along the way we will learn some of the core algorithmic techniques and concrete algorithms that underlie much of computer science; we will cover some very important and blazingly fast algorithms. The course will be both challenging (as evidenced by the incomplete list of topics below) and exciting! For an idea, you can check the 'transcript' of the course from Winter 2017.

Tentative scopes of the assignments: 1 - Lectures 1-3; 2 - Lectures 4-5; 3 - Lectures 6-8; 4 - Lectures 9-11; 5 - Lectures 12-14; 6 - Lectures 15-17.

Exam 1, April 25th: Lectures 1 - 5.

Exam 2, May 16th: Lectures 6 - 11.

Exam 3, June 11 (3-5): Lectures 12-17.

- There will be no makeup exams for the course. If the above dates do not work for you, you need to talk to me within the first week of classes.
- Students who arrive more than
**15 minutes**late for an exam will not be allowed into the exam and will automatically receive 0 credit. - Regrade requests need to be submitted electronically on Gradescope within a week of receiving the graded work. Requests later than a week will not be handled (mainly to keep things flowing).
- If you are unsatisfied with the online response for your regrade request, bring it up during a TA office hours next. If that also does not resolve it, and only then, you can bring it up during instructor office hours (so that we have time to discuss course material during the limited office hours).
- We will use piazza for questions and discussions. Questions related to assignments will not be answered via email. Use Piazza so that others can also benefit from your questions; if you want to communicate a private question, you can also do that on Piazza.
- Collaboration on homeworks is encouraged, but each student must write their solutions independently and should clearly mention the collaborators. Keep in mind that just attempting the homeworks itself will get you reasonable partial credit and will go a long way towards better performance in the exams (which carry significantly more weight). You should never share your written solutions with someone else or copy from someone else's written solutions. Under no circumstances may you use solution sets to problems from previous year courses or from similar courses elsewhere or other resoruces on the web.

Some helpful guidelines: (1) Start early to use office hours. (2) Serious/honest attempts count - there will be reasonable partial credit for attempts that show understanding of the problem/concepts involved.

The syllabus will be broken up as follows. A tentative lecture plan including homework dates is in the calendar above.

- Introduction: 1 lecture
- Divide and Conquer: 2 lectures
- Graph algorithms: 2 lectures Graphs and connectivity. Breadth-first search. Depth-first search. Finding cycles in graphs.
- Greedy algorithms: 3 lectures Interval scheduling. Minimum spanning trees.
- Dynamic programming: 3 lectures General framework. Sequence alignment, knapsack, LCS.
- Randomization to gain speed: 3 lectures Randomized divide & conquer: quick-sort, quick-select. Dictionary data structure.
- Intractability: 3 lectures P, NP, Reductions.

The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating will have significant and irrevocable consequences for your academic record and professional future. Please don't cheat.