CS 161, Spring 2019:
Design and Analysis of Algorithms
General Course Information
The course will be taught by David
Eppstein, firstname.lastname@example.org (office hours MW 4-5).
The TAs are Arkadeep Adhikari, email@example.com, and Daokun Jiang, firstname.lastname@example.org.
The course meets for lectures Mondays, Wednesdays, and
Fridays, from 11:00 – 11:50, in Howard Schneiderman Lecture Hall, Room HSLH 100A. In addition there
are four discussion sections.
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.
There is an online forum at Piazza (search for CS161). 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, and sharing your materials with other students in the class 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). 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. Homeworks will be graded 50% for effort,
50% for correctness on one of the assigned problems (chosen arbitrarily
from each problem set).
Homeworks should be turned in through GradeScope. 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.
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.
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.
- Week 1: Introduction; data structures
- Intro/review [Goodrich & Tamassia, chapter 1]; Fibonacci numbers (Chapter 12)
- Priority queues and heapsort (Chapter 5)
- Hashing with linear probing (Chapter 6)
- Homework 1, due Friday, April 12: R-1.3, R-1.7, C-5.8, R-6.5.
- Week 2: Comparison sorting
- Merge sort, divide-and-conquer, and the master theorem
(Chapters 8 and 11)
- Comparison sorting lower bounds (Chapter 8)
- Quick sort (Chapter 8)
- Homework 2, due Friday, April 19: R-8.5, C-8.9, R-11.1, C-11.3.
- Week 3: Selection and integer sorting
- Quickselect (Chapter 9)
- Bucket sort and stability (Chapter 9)
- Radix sort (Chapter 9)
- Homework 3, due Friday, April 26: R-9.1, R-9.5, C-9.2, C-9.4. For
R-9.1, use the algorithms as presented in the text, without special
tie-breaking rules; answer separately for the three-way quicksort of
section 8.2 and the two-way in-place quicksort of section 8.2.2. For
C-9.2, use an integer sorting algorithm, not hashing, and note that when
comparing sets, duplicate elements don't change the comparison
- Week 4: Midterm; integer arithmetic
- Midterm Monday, April 22
- Karatsuba multiplication (Chapter 11)
- Modular exponentiation and RSA encryption (Chapter 24)
- Homework 4, due Friday, May 3: R-11.2, R-24.5, R-24.6, C-24.8.
- Week 5: Graph representation and traversal
- Graph representation (Chapter 13)
- Depth first search and strong connectivity (Chapter 13)
- Directed acyclic graphs and topological ordering (Chapter 13)
- Homework 5, due Friday, May 10: R-13.4, R-13.5, R-13.7, R-13.12.
- Week 6: Shortest paths and minimum spanning trees
- DAG and Bellman–Ford shortest paths (Chapter 14)
- Dijkstra's algorithm (Chapter 14)
- Minimum spanning trees (Chapter 15)
- Homework 6, due Friday, May 17: R-14.8, C-14.2, R-15.9, C-15.11.
- Week 7: Midterm; dynamic programming
- Midterm Monday, May 13
- Dynamic programming for computing solutions to recurrence relations (Chapter 12)
- Finding optimal game strategies (Chapter 12)
- Homework 7, due Friday, May 24: C-12.1, C-12.2, C-12.3, C-12.4
- Week 8: Dynamic programming applications
- Longest common subsequences (Chapter 12)
- The knapsack problem (Chapters 10 and 12)
- Homework 8, due Friday, May 31: R-10.1, R-12.5, C-12.11, A-12.3
- Week 9: Computational geometry
- Memorial day holiday, Monday, May 27.
- Convex hulls (Chapter 22)
- Closest pairs (Chapter 22)
- Homework 9, due Friday, June 7: R-22.8, C-22.1, C-22.5, C-22.15
(hint: you can solve this problem using any efficient closest pair
algorithm as a subroutine, without having to understand how it works).
- Week 10:
- Streaming algorithms (not in text;
Cormode's slides on finding frequent items and
article on reservoir sampling)
- NP-completeness (Chapter 17)
- Approximation algorithms (Chapter 18)
- Final exam:
- Tuesday, June 11, 1:30-3:30pm
Other Course-Related Information
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