Design and Analysis of Algorithms

The course will be taught by David Eppstein, eppstein@uci.edu (office hours Tues 2:30 – 3:30 and Weds 4:30 – 5:30 in Bren 4082). The teaching assistants are Sid Gupta (office hours Thu 3:30 – 4:30 and Fri 12:00 – 1:00 in Bren 4032) and Nil Mamano (office hours Mon 12:30 – 1:30 and Weds 1:30 – 2:30 in Bren 4061). We also have four readers, Nitin Agarwal, Disi Ji, Jordan Jorgensen, and Pedro Matias.

The course meets for lectures Mondays, Wednesdays, and Fridays, from 3:00 – 3:50, in Social Science Lecture Hall, Room 100. In addition there are four discussion sections, Tuesdays and Thursdays at 5, 6, 7, and 8pm in ICS 174. Students are expected to be enrolled in one of the discussion sections and to attend discussions regularly. We will not be taking attendance, and it is ok to attend a different discussion than the one you are enrolled in as long as space permits. At the discussion sections, the teaching assistant will go over homework and midterm solutions, give additional examples of topics covered in the lecture, and be available to answer questions.

Additionally, the course has a Piazza page for online discussions and answers to questions. You can sign up to this at http://piazza.com/uci/fall2016/cs161cse161.

Lecture materials will not be distributed to the class; instead, you are encouraged to attend the lecture yourself and take your own notes. Recording the lectures for your own personal use is allowed, but other uses of recorded lectures (including making them available online) is forbidden.

The course text will be "Algorithm Design and Applications" by Goodrich and Tamassia (Wiley, 2015). Students are expected to own a copy and to read the relevant chapters and sections. The official version of the textbook is the one sold in the bookstore. Most homework problems will be assigned from this text. If you are using a different version (e.g., an international version, or the older text by the same authors), then it is your responsibility to make sure you are doing the correct homework problems.

Coursework will consist of weekly homeworks (typically due on Fridays and posted on this page before the start of class on Monday of the week it is due) as well as two midterms and a comprehensive final exam. The overall grade will be determined 10% from homework, 25% from each midterm, and 40% from the final.

Group work on homeworks is permitted; however, each student should turn in his or her own copy of the homeworks. Some of the homework problems will ask you to perform calculations or trace the steps of an algorithm; you are welcome to use computer programs to solve these problems rather than doing everything by hand. Each week's homework assignment will be given on this web page. Homework is due by 9:00pm on Fridays and must be turned in through dropbox on eee. No late homework will be accepted. Handwritten homework or homeworks in other formats risk graded. Students who add the class after the start of quarter will be responsible for turning in all earlier homeworks by the following Friday. The lowest homework score of the quarter will be dropped from the course average.

Homework must be formatted as a pdf file. We strongly recommend that homeworks be typed; we will also accept homeworks in pdf format generated by scanning a handwritten answer sheet, but if your handwriting is not legible to the course readers you will be penalized for it. If you need to include equations or formulas in your answers, you might find it helpful to use a LaTeX-based document formatting system. Exam answers may be written either by pencil or pen, but regrade requests will only be accepted for answers that were written in non-erasable ink.

For the UCI academic integrity policy, please see aisc.uci.edu. Students who are caught cheating in this class (for instance by copying exam solutions or allowing other students to copy from them) risk getting an F in the class or other disciplinary action as allowed by this policy.

**Week 0:**- Sep. 23: Intro/review [Goodrich & Tamassia, chapter 1]; Fibonacci numbers (Chapter 12)
**Week 1: Data structures**- Homework 1, due 9:00pm on Friday, Sep. 30: R-1.3, R-1.4, R-1.7, R-1.10
- Sep. 26: Priority queues and heapsort (Chapter 5)
- Sep. 28: Hashing with linear probing (Chapter 6)
- Sep. 30: Nearest neighbor searching with balanced WAVL trees (Chapter 4)
**Week 2: Comparison sorting**- Homework 2, due 9:00pm on Friday, Oct. 7: R-4.17, R-5.11, C-6.1, A-6.8
- Oct. 3: Merge sort, divide-and-conquer, and the master theorem (Chapters 8 and 11)
- Oct. 5: Comparison sorting lower bounds (Chapter 8)
- Oct. 7: Quick sort (Chapter 8)
**Week 3: Selection and integer sorting**- Homework 3, due 9:00pm on Friday, Oct. 14: R-8.5, C-8.10, R-9.5, C-9.1
- Oct. 10: Quickselect (Chapter 9)
- Oct. 12: Bucket sort and stability (Chapter 9)
- Oct. 14: Radix sort (Chapter 9)
**Week 4: Midterm; integer arithmetic**- Oct. 17: MIDTERM ONE
- Oct. 19: Karatsuba multiplication (Chapter 11)
- Oct. 21: Modular exponentiation and RSA encryption (Chapter 24)
**Week 5: Graph representation and traversal**- Homework 4, due 9:00pm on Friday, Oct. 28: R-11.4, R-24.5, R-24.10, C-24.8
- Oct. 24: Graph representation (Chapter 13)
- Oct. 26: Depth first search and strong connectivity (Chapter 13)
- Oct. 28: Directed acyclic graphs and topological ordering (Chapter 13)
**Week 6: Shortest paths and minimum spanning trees**- Homework 5, due 9:00pm on Friday, Nov. 4: R-13.4, R-13.12, C-14.2, C-14.4
- Oct. 31: DAG and Bellman–Ford shortest paths (Chapter 14)
- Nov: 2: Dijkstra's algorithm (Chapter 14)
- Nov. 4: Minimum spanning trees (Chapter 15)
**Week 7: Midterm; dynamic programming**- Nov. 7: MIDTERM TWO
- Nov. 9: Dynamic programming for computing solutions to recurrence relations (Chapter 12)
- Nov. 11: VETERANS DAY HOLIDAY
**Week 8: Dynamic programming applications**- Homework 6, due 9:00pm on Friday, Nov. 18: R-12.4, R-12.8, C-12.3, A-12.9
- Nov. 14: Finding optimal game strategies (Chapter 12)
- Nov. 16: Longest common subsequences (Chapter 12)
- Nov. 18: The knapsack problem (Chapters 10 and 12)
**Week 9: Computational geometry**- Nov. 21: Convex hulls (Chapter 22)
- Nov. 23: Closest pairs (Chapter 22)
- Nov. 25: THANKSGIVING HOLIDAY
**Week 10:**- Homework 7, due 9:00pm on Friday, Dec. 2: R-22.8, C-22.1, C-22.5, C-22.6
- Nov. 28: Streaming algorithms (not in text; see Graham Cormode's slides on finding frequent items and the Wikipedia article on reservoir sampling)
- Nov. 30: NP-completeness (Chapter 17)
- Dec. 2: Approximation algorithms (Chapter 18)
**Final exam:**- Dec. 5 (Monday), 4:00 - 6:00 (per schedule)

The following material is from previous years' offerings of ICS 161. Some of these offerings were based on different texts (Baase and Cormen-Leiserson-Rivest), and covered a somewhat different range of topics. You may find this material useful, but it is not required reading.