CSE 203A: Advanced algorithms, Winter 2003

Instructor: Daniele Micciancio

Time & Place: Tu,Th 9:30-10:50am, Solis 111

Section ID: 456341

Textbooks

The following two textbooks will be used:

Most of the material presented in class can be found in the textbooks. They will be the main reference for the course, and lecture notes will be distributed only occasionally for topics not in the textbooks. Although we will be able to cover only part of each book, they are both excellent references, and their use is strongly recommanded. Homework assignments will typically be a selection of excercises and problems from the textbooks..

Course Description

This course will cover advanced algorithmic concepts and techniques. In particular, we will study the use of randomness as a tool to design improved or simpler algorithms for various problems, and approximation techniques to devise solutions for problems whose exact solution is intractable. The course will try to emphasize general techniques that can be applied to many different problems, and it is expected to be of interest to most researchers in computer science, not just theoreticians. The course will try to be self-contained, beyond a basic understanding of algorithms (CSE202) and probability theory.

A detailed list of topics will be posted as the course goes on. Here is a start:

  1. Background: basic probability theory, randomized models of computation and probabilityic complexity classes
    Reading: [MR] App. C and Chapter 1.5
  2. Introduction to approximation and randomized algorithms. Examples of Monte Carlo (Min Cut) and Las Vegas (Quicksort) Algorithms.
    Tools: linearity of expectation, conditional probability.
    Reading: [MR] Chapter 1, 1.1, 1.2
  3. Game tree evaluation, proving lower bounds for randomized algorithms
    Tools: game theory, minimax principle
    Reading: [MR] Chapter 2
  4. The probabilistic method, randomized approximation algorithm for MAX-SAT, derandomization using conditional expectations
    Reading: [MR] Chapter 5.1, 5.2, 5.6, [V] Chapter 6
  5. Markov chains and random walks
    Reading: [MR] Chapter 6
  6. Approximation algorithms and min-max relations
    Reading: [V] Chapter 1
  7. Approximation algorithm for Set Cover
    Reading: [V] Chapter 2
  8. Linear Programming, designing approximation algorithms using LP duality (dual fitting, randomized rounding, primal-dual schema)
    Reading: [V] Chapters 12, 13, 14, 15
  9. Approximate coNP algorithm for Shortest Vector Problem

    Reading: [V] Chapter 27

Prerequisites

Introductory graduate level knowledge of algorithms (CSE 202 or equivalent), and implied prerequisites (e.g., discrete math and basic probability) is assumed.

Assignments

If you are not taking this course for letter grade, it is enough for you to do the homework assignments.

If you are taking the course for letter grade you are required to either give a presentation, or do a project. You can do that either individually, or in pairs. If you work on the presentation or project in pairs, then you are also required to do the homeworks individually.

As a starting point for your project/presentation you can select a paper reltated to this course from a recent theoretical computer science or algorithms conference, e.g. FOCS 2000, FOCS 2001, STOC 2001, STOC 2002, SODA 2001, SODA 2002.

The homework assignment will be distributed in class.

SCHEDULE

.