Course Description

Math 182 is an introduction to the theory of algorithms. There is no programming pre-requisite. The goal of the course is to develop the basic design principles behind most modern efficient algorithms: greedy algorithms, divide-and-conquer, dynamic programming, and network flows. These powerful techniques will be illustrated on a variety of applications, from networking to computational biology.

Prerequisites: Some familiarity with calculus will be assumed (at the level of 3C or 32A). Math 182 is NOT a programming course. It is a discrete mathematics course with an emphasis on the mathematical analysis of efficient algorithms. (The Program in Computing (PIC) offers a series of programming courses in C++ and Java which are NOT required for Math 182, but that you may want to take separately or concurrently.)

General Information

• Instructor: Sebastien Roch (Office: MS 6228; Office hours: M 9:00-9:50am, W 1:00-2:50pm)
• TA: Pietro Carolino (Office: MS 2903; Office hours: R 10:00-10:50am)
• Class schedule: MWF 11:00-11:50am in 5127
• Section schedule: R 11:00-11:50am in 5127
• Midterm exam: Friday, April 29, 2011, 11:00am-11:50am in class
• Final exam: Wednesday, June 8, 2011, 3:00pm-6:00pm
• Required Text: The required textbook for the course is the excellent:
  • [KT] Kleinberg and Tardos, Algorithm Design.
  We will cover the first seven chapters. I will also occasionally refer to the following supplementary textbook (available online):
  • [DPV] Dasgupta, Papadimitriou, and Vazirani, Algorithms.
  Some may prefer the more concise style of the latter. The two books cover essentially the same material, at the same level.
• Grading: There will be regular homework assignments mostly taken from the textbook. The lowest homework score will be dropped. No late homework will be accepted. The final grade will be the maximum of:
  • Homework 20%, Midterm 30%, Final 50%
  • Homework 20%, Final 80%
  No make-up exam will be given. Requests for re-grading must be made no later than one week after the midterm is returned. The final exam must be taken in order to receive a passing grade. All exams are closed books. Grades will be recorded in the MyUCLA gradebook.
• Section: Attendance in section is expected. Solutions to homework assignments and midterm exam will not be posted online. Instead they will be discussed in section as needed.
• Handout: The handout is here.

News

• [Jun 5]: The final exam will take place Wednesday, June 8, 2011 from 3:00 PM to 6:00 PM in MS 5127. The exam is closed book and covers Chapters 2 to 7 except Sections 4.9, 5.6, 6.7, 6.9, 7.4 and 7.13. (Note that Chapter 1 is not covered in the exam.) Recall that, for algorithmic questions, a pseudocode in itself does not constitute a complete answer. I also expect an analysis of correctness and running time.
• [May 27]: Final homework posted.
• [May 20]: Eighth homework posted.
• [May 15]: Seventh homework posted.
• [May 9]: Sixth homework posted.
• [Apr 29]: Fifth homework posted.
• [Apr 21]: The midterm will take place on Friday, April 29 in class. The exam is closed-book and covers Chapters 1 through 4 except Sections 1.2 and 4.9.
• [Apr 18]: Fourth homework posted.
• [Apr 11]: Third homework posted.
• [Apr 5]: My office hours this Wednesday are cancelled.
• [Apr 1]: I will be holding office hours this afternoon from 1:00-2:50pm to replace the ones I missed on Wednesday.
• [Mar 27]: First homework posted.
• [Feb 2]: Website posted.

Lectures

The lectures will be partly based on slides available here.

• Lec [Mar 28]: Cancelled.
• Lec 1 [Mar 30]: Syllabus. Stable matchings: definition, solution. Section 1.1.
• Lec 2 [Apr 1]: Stable matchings: Implementation. Section 2.3.
• Lec 3 [Apr 4]: Tractability. Sections 2.1, 2.2, 2.4.
• Lec 4 [Apr 6]: Graph algorithms: Definitions, connectivity, traversal. Sections 3.1, 3.2.
• Lec 5 [Apr 8]: Graph algorhtms: Bipartiteness, directed graphs, topological ordering. Sections 3.4-3.6.
• Lec 6 [Apr 11]: Greedy algorithms. Section 4.1.
• Lec 7 [Apr 13]: More greedy algorithms. Sections 4.2, 4.4.
• Lec 8 [Apr 15]: Heaps and implementation of greedy algorithms. Sections 2.5, 4.4.
• Lec 9 [Apr 18]: MST. Section 4.5.
• Lec 10 [Apr 20]: More MST. Clustering. Sections 4.6, 4.7.
• Lec 11 [Apr 22]: Optimal caching. Section 4.3.
• Lec 12 [Apr 25]: Huffman codes. Section 4.8.
• Lec [Apr 27]: Review for midterm.
• Lec [Apr 29]: MIDTERM.
• Lec 13 [May 2]: Divide-and-conquer. Sections 5.1, 5.2, 5.3.
• Lec 14 [May 4]: More divide-and-conquer. Sections 5.4, 5.5.
• Lec 15 [May 6]: Dynamic programming: basics. Sections 6.1, 6.2, 6.3.
• Lec 16 [May 9]: Dynamic programming: basics (continued). Sections 6.4, 6.5.
• Lec 17 [May 11]: Dynamic programming: alignment. Sections 6.6, 6.7.
• Lec 18 [May 13]: Dynamic programming: shortest paths. Sections 6.8, 6.10.
• Lec 19 [May 16]: Maximum-flow and minimum-cut problems. Sections 7.1, 7.2.
• Lec 20 [May 18]: Scaling algorithm. Application to bipartite matching. Sections 7.2, 7.3
• Lec 21 [May 20]: More on matchings. Disjoint paths. Sections 7.5, 7.6.
• Lec 22 [May 23]: Circulation with demands. Sections 7.7.
• Lec 23 [May 25]: Circulation with demands (ctd). Survey design. Sections 7.7, 7.8.
• Lec 24 [May 27]: Airline scheduling. Image segmentation. Project selection. Section 7.9, 7.10, 7.11.
• Lec [May 30]: NO LECTURE (Memorial Day Holiday).
• Lec 25 [Jun 1]: Review for final.
• Lec [Jun 3]: Review for final.

Assignments

Unless stated otherwise, the homework problems are taken from [KT]. The Python questions are entirely optional. If you wish to attempt them, you are expected to learn Python on your own. We will not discuss Python in class. The official Python tutorial should suffice.

• Hwk 1 [Due in class on Monday, Apr 4]: Exercises 1, 2, 3, 4, 6 from Chapter 1 in [KT]. Bonus question: Write a Python code for the algorithm in Exercise 4. Hint for Exercise 6: Encode the situation as a stable matching problem.
• Hwk 2 [Due in class on Monday, Apr 11]: Exercises 2, 4, 5, 6 from Chapter 2 and Exercises 2, 5 from Chapter 3 in [KT]. Bonus question: Write a Python code for the "simple" algorithm in Exercise 6 of Chapter 2. Remark for Exercise 5 of Chapter 2: Assume g(n) is at least 2.
• Hwk 3 [Due in class on Monday, Apr 18]: Exercises 1, 3, 9, 10 from Chapter 3 and Exercises 3, 4, 7, 29 from Chapter 4 in [KT]. Bonus question: Write a Python code for the algorithm in Exercise 9 of Chapter 3.
• Hwk 4 [Due in class on Monday, Apr 25]: Exercises 8, 10, 18, 20, 21, 26, 27 in Chapter 4. Bonus: Write a Python code for the algorithm in Exercise 21 of Chapter 4. Hint for Exercise 10 in Chapter 4: To simplify, you may assume that all edge costs are distinct.
• Hwk 5 [Due in class on Friday, May 6]: Exercises 1, 2, 3, 5, 6 in Chapter 5. Bonus: Write a Python code for the algorithm in Exercise 2 of Chapter 5.
• Hwk 6 [Due in class on Friday, May 13]: Exercises 1, 3, 4, 5, 16, 19, 20 in Chapter 6. Bonus: Write a Python code for the algorithm in Exercise 1(a) of Chapter 6.
• Hwk 7 [Due in class on Friday, May 20]: Exercises 11, 13, 14, 22, 23, 28 in Chapter 6. Bonus: Write a Python code for the algorithm in Exercise 11 of Chapter 6.
• Hwk 8 [Due in class on Friday, May 27]: Exercises 1, 3, 5, 7, 12, 16, 19, 26 in Chapter 7. Bonus: Write a Python code for the algorithm in Exercise 12 of Chapter 7.
• Hwk 9 [Due in class on Friday, June 3]: Exercises 2.1, 3.7, 4.2, 4.5, 5.7, 6.6, 6.10, 7.8, 7.9 in [KT].