Overview

The goal of this class is to introduce you to some topics in the design and analysis of algorithms. In the first part of the class, we will review some basic algorithm design paradigms, and show how one can use these paradigms to design efficient exact and approximation algorithms. In the second part, we will cover some more advanced topics, such as flows, randomized algorithms and streaming algorithms.

Prerequisites

A prerequisite for this course is CSE 101 or its equivalent. You should have undergraduate exposure to discrete mathematics and algorithms and their analysis. At the beginning of the class, I expect you to be very familiar with the material in Chapters 1-3 of the text book (which will not be covered in the class), and somewhat familiar with Chapters 4-5 (which will be covered very rapidly.) We will very briefly review topics from your undergraduate algorithms courses, and then look at some more advanced topics.

Textbook

Kleinberg and Tardos, Algorithm Design

Syllabus

Chapters 4-7 and Chapter 13 of the textbook will be covered. If time permits, we will also cover some more advanced topics such as streaming algorithms.