P2
CSC2420 Home Page
CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Spring 2015)
This page will provide WWW access to various documents concerning CSC2420.
Announcements will also be made on
this page.
The class will be held Thursdays 2-4 in BA 1200.
%Please consult
% the
%CSC 2420 Fall 2012 web page for lecture notes from that term.
Please send any comments or questions to the instructor:
Announcements
I accidently uploaded the wrong L10 file. It has now been properly posted.
The graded assignment 2 can be picked up from Lalla in her office SF4301D
starting Monday. Lalla is usually in 9-6.
The third and final problem set is
due April 7(instead of the initial April 2). Please note that question 2 refers to the deterministic polynomial time algorithm.
It is preferable if you send a pdf file. Otherwise please arrange to contact
Lalla.
If you are intending to graduate this term, please let me know so that I
can be sure to submit your grades on time.
This course is the fourth time offering of our graduate level
introduction to the design and analysis
of algorithms. The course serves as a foundational course,
appropriate for students in computer science, computer engineering,
and mathematics. However, the course should also be of
interest to ``theory students'' looking for research topics.
We will begin with topics normally discussed in
undergraduate courses such as our CSC373/CSC375 using some less standard
examples and also discussing some precise models for
standard algorithmic paradigms such as greedy, local search and
dynamic programming algorithms. Other possible topics include:
online algorithms, the random order model,
randomized algorithms and Markov chains, linear and submodular
maximization subject to independence constraints,
LP and SDP relaxations,
primal dual algorithms, online primal dual algorithms,
sublinear time algorithms, embedding techniques,
data stream algorithms, MapReduce algorithms,
multiplicative weights algorithms,
spectral methods,
algorithmic aspects of mechanism design, social networks
and information retrieval.
We will not use any one text book for this course. There are a number of
excellent undergraduate texts (e.g. "Algorithm Design" by
Jon Kleinberg and Eva Tardos;
"Introduction to Algorithms"
by Corman, Leiserson, Rivest and Stein;
``Algorithmics: Theory and Practice" by Brassard and Bratley; and
"Algorithms" by DsGupta, Papadimitriou and U. Vazirani) that
cover the standard topics
and include advanced material. There are also a number of texts
on somewhat specialized topics (e.g. "Approximation Algorithms" by V. Vazirani;
"A First Course in Combinatorial Optimization", by James Lee;
and "Randomized Algorithms" by Motwani and Raghaven).
There are also many web accessible courses that indicate the diversity
of topics taught in graduate algorithms courses. For example, you
may want to consider the following sources:
University of Washington CSE 521
University of Washington CSE 522
Cornell University CSC6820
CMU 451/651
Nikhil Devanur Online Course
Avner Magen LP and SDP Course
Lecture slides will be posted here
Lecture 1
Lecture 2
Lecture 3
Lecture 4
. Note argument for Makespan PTAS has been``cleaned up''.
Lecture 5
Lecture 6
The following three slides relate to Derek Corneil's guest lecture (Lecture 7).
General
introduction to graph search
Part 1 of more
detailed seminar regarding graph search.
Part 2 of more
detailed seminar.
Lecture 8
Lecture 9
Lecture 10
Lecture 11
Lecture 12
Assignments will be posted here. Note questions for P2 will be incrememntally
added as the relevant material is presented.
Given my delay in not posting new problems, the due date is now March 5.
Assignment 1
Assignment 2
Assignment 3
Here is the article by Buchbinder et al that provides the deterministic 1/3
and randomized 1/2 approximation for the
unconstrained maximization of a submodular set function .