CMPS201 - Analysis of Algorithms

UC Santa Cruz, Fall 2013

About Announcements Schedule /
Lecture Notes
FAQ Contact Misc Readings

Latest CMPS201 Announcements

Course Information

Lecture: MW 17:00-18:45, Kresge Clrm 327
Instructor: Dimitris Achlioptas
Office Hours:
TA: Dimitrios Skourtis
Sections: Monday 12:30 - 1:30, Thursday 16:00 - 17:00; Oakes Acad 106

Syllabus

A Sort of Introduction


Course Materials

Text: Tardos and Kleinberg
The core of the course will be based on a subset of the book by Kleinberg and Tardos titled Algorithm Design (required text -- available for sale at the university bookstore).

Supplements:
MIT OCW Introduction to Algorithm Analysis

Course Description

Methods for the systematic construction and mathematical analysis of algorithms. The algorithm design techniques covered include divide-and-conquer, greedy algorithms, dynamic programming, and network flows. Potentially also linear programming and techniques for designing approximation algorithms. Applications to combinatorial, graph, string, and geometric algorithms.

Lecture Schedule

Week 1MonOct 1st Stable matching problem
WedOct 3rd Master theorem, Divide and conquer
Week 2MonOct 7th Median [1, 2], Closer set of points
WedOct 9th Matrix multiplication, Interval scheduling

Frequently Asked Questions

I keep getting mediocre scores on my proofs. What should I do?
Practice. Debug your proofs as if they were code! Name the objects that you talk about in your proof (ie "...therefore there exists a point, P, that..."). Practice.
I'm confused. What should I do?
Go to section and office hours, and ask questions. Email the Google Group or the TA. Don't wait until you fall way behind. The TA is there to help you, but don't expect him to solve all of your problems in the last three hours before an assignment is due.

Professor Dimitris Achlioptas

<last five letters of last name> @ cs.ucsc.edu
Homepage

Dimitrios Skourtis (TA)

<last name> @ cs.ucsc.edu

Miscellaneous Readings

Regarding the economy of developers
Some thoughts on the P vs. NP problem
The mental effects of multitasking
A puddle as a Music Visualizer
Benoit Mandelbrot, Fractals, and the Mathematics of Roughness
A teacher asks: Why do I teach?