15-351/15-650/02-613
Algorithms & Advanced Data Structures
Fall 2023

Instructor: Yun William Yu, Assistant Professor of Computational Biology

Course Description

The objective of this course is to study general computational problems, with a focus on the principles used to design those algorithms. Efficient data structures will be discussed to support these algorithmic concepts. Topics include: run-time analysis, divide-and-conquer algorithms, dynamic programming algorithms, network flow algorithms, linear and integer programming, large-scale search algorithms and heuristics, efficient data storage and query, and NP-completeness. Although this course may have a few programming assignments, it is primarily not a programming course. Instead, it will focus on the desing and analysis of algorithms for general classes of problems. This course is not open to Computer Science graduate students, who should consider taking 15-651 instead.

Cross-listed numbers

All the courses have the same structure, lectures, TAs, etc. There may be additional assignments and exam questions for students signed up under one of the graduate numbers. The grading curve will be computed separately in each of the three courses.

Schedule

Mondays, Wednesdays, and Fridays 9-9:50am.
Doberty Hall 2315
The first lecture will be on Monday, August 28.

A non-exhaustive set of topics we tentatively plan on covering are as follows:

  1. Minimum spanning trees
  2. Asymptotic analysis
  3. Graph traversals
  4. Topological sort
  5. Shortest paths
  6. Suffix trees/arrays
  7. Dynamic programming
  8. String alignment (genomics)
  9. Network flow
  10. Amortized analysis
  11. Splay trees
  12. Linear programming
  13. NP-hardness
  14. Approximation algorithms
  15. Hashing
  16. Probabilistic sketching
  17. Minimum cut
  18. Closest pair of points

Here is the rough schedule and prelecture notes (gratefully based off Carl Kingsford's excellent materials; all errors are mine):

Office Hours and Contact Info

TA office hours to-be-determined

Piazza: https://piazza.com/cmu/fall2023/026131535115650/home

We strongly encourage contacting course staff via Piazza (you may post to instructors only); we cannot guarantee a timely response for any other medium.

If you have an issue that you wish to raise to just the professor (for example, a complaint about a TA), you may email directly to ywyu@cmu or yuny@andrew. However, any other general course-related correspondence should be via Piazza.

 

Syllabus

 

Reference texts

The primary reference text is Algorithm Design by Jon Kleinberg and Eva Tardos (2005).

Homework

Homework will be approximately weekly. Every homework can be submitted up to 24 hours late for a 20% penalty. No other late homeworks will be accepted. Homework must be handwritten and submitted online (either scanned or written on a tablet).

Solutions should be as short, clear, and concise as possible. We will be taking marks off for long, meandering solutions to otherwise short problems, even if all of the reasoning is technically correct. Brevity is the soul of wit.

More details about submitting homework to come.

Midterms and Exam


There will be two midterms and a final exam.

Icons made by xnimrodx from www.flaticon.com.