TAs: Sam Haney, Nat Kell

UTAs: Ang Li, Wenshun Liu, Yilun Zhou, Roger Zou

Times & Locations

Lectures: | Tue, Thu 3:05-4:20 pm in Physics 128 |

Recitations: | Fri 11:45 am-1:00 pm in Social Sciences 139 |

Office Hours

Panigrahi: | Tue 4:45-5:30 pm, Thu 11-11:45 am in LSRC D203 |

Haney: | Mon 4:00-5:00 pm in North 306 |

Kell: | Wed 4:00-5:00 pm in North 306 |

We will use Piazza for all correspondence and discussions related to the course. If you have a question about the course material or want to initiate a discussion, post it on Piazza allowing the entire class to view and participate in it. If you want to contact the course staff only, send a message via Piazza that is visible only to the relevant course staff.

Algorithms are a cornerstone of computational sciences and the need for efficient algorithms is ubiquitous in modern technology. However, the primary goals of algorithm design, the resources that need to be optimized, and even the model of computation varies widely between application areas. In this course, we will study some of the fundamental principles of algorithm design that appear in multiple areas and have had broad impact. In addition, we will focus on the mathematical tools that are frequently used in the theoretical analysis of algorithms, and study how such analysis, in turn, influences algorithm design. The course will be at an undergraduate level and will aim to serve the following objectives:

- provide basic training in algorithm design for a future computer scientist and/or programmer, and
- expose future professionals in other disciplines to fundamental algorithmic paradigms.

- Basics: history of algorithms, asymptotic and worst-case analysis, time and space as resources, recurrences
- Design techniques: divide and conquer, dynamic programming and memoization, greedy algorithms
- Graph algorithms: graph representations, graph traversal and applications, shortest path, minimum spanning tree, network flows and cuts
- Computational geometry: convex hull
- Data structures: binary search trees, height and weight balanced trees, amortization and potential functions, union-find
- Randomized algorithms: Monte Carlo and Las Vegas algorithms, hashing, primality testing
- Linear programming:simplex algorithms, duality
- Intractability: lower bounds, easy and hard problems, NP-completeness, polynomial time reductions
- Approximation algorithms: greedy algorithms, LP rounding, approximation schemes
- Online algorithms: rent or buy, paging

There are two hard prerequisites: COMPSCI 201 Data Structures and Algorithms and COMPSCI 230 Discrete Math for Computer Science, or equivalent courses. If you do not satisfy these prerequisites, please contact the instructor.

Lecture notes will be uploaded on the course website after every lecture. In addition, the following books cover most of the syllabus:

[DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.

[KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.

[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2009.

[AHU] A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.

[Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.

[Er] J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC.

[Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.

- Assignments (five): 30%
- Midterm exams (two): 40%
- Final exam: 30%
- Both the midterms and the final exam will be in-class closed-book exams.

- Review the detailed guidelines on
collaboration.
**Any violation of these guidelines will be reported without exception to the relevant authority.** - You are allowed one late homework submission, which may be turned in up
to one week after the original deadline. All other late submissions will
receive
**no credit**. - We will use
**Sakai**for homework submission. - The answer to each homework problem has to be typed. It is strongly encouraged that you prepare your homework submissions in LaTeX.
- Answers to all problems on an assignment must be submitted by 11:59 pm EST on the due date.
- Solutions will be available on Sakai after the late submission deadline.