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

Course goals
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.

Homework (6 x 3%). There will be six assignments each worth 3 points. The assignments will be released on a Monday and all but the last will be due at 6PM the following Monday; the last assignment will be due on 6PM the Friday of the same week (so that you have time to review the solutions for the final).

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.

Quizzes (10 x 1%). There will be a short weekly online quiz that will go live on CCLE every Wednesday at 6PM. The quiz should take you about 5 minutes to answer and will be open till Friday 6PM.

Exams. There will be three non-cumulative exams (22%, 25%, 25%). The first two will be held in class, the last one will be as per university schedule. The exams will be closed-book and closed-notes.

Exam 1, April 25th: Lectures 1 - 5.
Exam 2, May 16th: Lectures 6 - 11.
Exam 3, June 11 (3-5): Lectures 12-17.

Course policies: No exceptions with the following easy to follow policies.
  • 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.
Homework submission We will use Gradescope for homework and they have to be submitted by 6PM on their due date. This is extremely helpful both for me as well as for you - you'll get better feedback and will have a digital record of all your homework that you can refer to later. Things to keep in mind: 1) Within a week of the course, you should receive a registration link from Gradescope. If you don't receive it before the first homework, contact the TAs immediately; this will give you access to the website. 2) Watch this one-minute video with complete instructions. Follow them to the letter! The simple guidelines make the process considerably smoother. 3) Make sure you start each problem of a homework on a new page. 4) To generate a PDF scan of the assignments, you can follow the instructions here; you can also use the scanners in the library.

Homework writing It is strongly recommended to use LaTeX or other word processing software for submitting the homework. Grades will take into account both the correctness and the quality of the solutions. Correctness is a prerequisite but clarity is also important: you are responsible for communicating your solution in a legible and understandable way.
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.

Syllabus and lecture plan
The syllabus will be broken up as follows. A tentative lecture plan including homework dates is in the calendar above.
  • Introduction: 1 lecture
    • Logistics. What is an algorithm? Multiplication, Asymptotic analysis.
  • Divide and Conquer: 2 lectures
    • Merge-sort, master theorem, Karatsuba multiplication, fast exponentiation.
  • 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.
Academic honesty: While collaboration with other students on assignments is fine, each student must write their solutions independently and should clearly mention the collaborators. Keep in mind that it is emphatically in your best interest to attempt the problems honestly: not spending time on the homework problems will put you at a significant disandvantage in the exams (as you would not have had much practice) that 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.

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.