**Design and Analysis of AlgorithmsCSCI 5454, Spring 2013**

Time: Monday and Wednesday, 1:00pm - 2:15pm

Room: ECCS 1B12

Instructor: Aaron Clauset

Office: ECOT 743

Office hours: Wednesdays, 10:00-11:30am

Email: look it up

Syllabus

**Description**

**Course work and grading**

**Schedule and lecture notes**

**Problem sets**

**Description**

Algorithms are the heart of computer science, and their essential nature is
to automate some aspect of the collecting, organizing and processing of
information. Today, information of all kinds is increasingly available
in enormous quantities. However, our ability to make sense of all this
information, to manage, organize and search it, and to use it for practical
purposes, e.g., self-driving cars, adaptive computation, search algorithms
for the Internet or for social networks, artificial intelligence, and many
scientific applications, relies on the design of efficient algorithms, that
is, algorithms that are fast, use little memory and provide guarantees on
their performance.

This graduate-level course will cover topics related to
algorithm design and analysis. Topics will include divide and conquer
algorithms, greedy algorithms, graph algorithms, algorithms for social
networks, computational biology, optimization algorithms, randomization
and algorithm analysis. We will not cover any of these topics
exhaustively. Rather, the focus will be on algorithmic thinking, performance
guarantees and boundary cases, efficient solutions to practical problems and
understanding how to analyze algorithms.
Advanced topics will cover a selection of modern algorithms, many of which
come from real-world applications.

**Prerequisites**

Undergraduate algorithms (CSCI 3104), data structures (CSCI 2270), discrete
mathematics (CSCI 2824) and two semesters of calculus, or equivalents. This
class assumes familiarity with asymptotic analysis (Big-*O*, etc.),
recurrence relations and the correct implementation of basic algorithms.
Students without the required background may struggle to keep up with the
lectures and assignments. There will be a brief survey at the beginning of
the semester to help me get an idea of the class's preparation.

**Text**

Required:

Introduction to Algorithms (3rd ed.), by Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest and Clifford Stein ("CLRS"; available
at the CU Bookstore).

Optional:

Algorithm Design, by J. Kleinberg and E. Tardos, and

Algorithms, by S. Dasgupta, C. Papadimitriou and U. Vazirani

**Course work and grading**

See the syllabus for description of the required coursework, including
descriptions of the problem sets, crowd-source lecture and independent
project assignments.

**5454-002** (or by permission): Grades will be assigned based on
attendance (0.2), crowd-source lecture or independent project (0.3), and
problem sets (0.5).

**5454-5454**: Grades will be assigned based on the project (0.4) and
problem sets (0.6).

**Tentative Schedule**

Week 1: Overview, why algorithms? (Lecture 0)

Week 2: Divide and conquer (Lecture 1 and Lecture 2)

Week 3: Randomized data structures (Lecture 3 and Lecture 4)

Week 4: Greedy algorithms (Lecture 5)

Week 5: Graph algorithms (Lecture 6 and Lecture 7)

Week 6: Minimum spanning trees (Lecture 8)

Week 7: Network flow (Lectures 9 and 10)

Week 8: Phylogenetic trees (Lectures 11 and 12)

Week 9: Optimization (Lecture 13) and Graph Clustering (Lectures 14 and 15)

Week 10: Stable matchings (Lecture 16) and

Crowd-source lecture
(i) disjoint sets and union find (Lecture 17)

Week 11: Spring Break

Week 12: Crowd-source lectures:

(i) knapsack problems (Lecture 18) and
(ii) sequence alignment (Lecture 19)

Week 13: Crowd-source lectures:

(i) randomized min-cut (Lecture 20) and
(ii) Sudoku and latin square solvers (Lecure 21)

Week 14: Crowd-source lectures:

(i) Byzantine agreement (Lecture 22) and
(ii) fair division algorithms (Lecture 23)

Week 15: Crowd-source lectures:

(i) NP-hard problems (Lecture 23) and
(ii) approximation algorithms (Lecture 24)

Week 16: Crowd-source lectures:

(i) link prediction in social networks (Lecture 24)
and (ii) PageRank algorithm (Lecture 25)

**Problem Sets**

**Problem set 1** (assigned January 14; due February 4)

**Problem set 2** (assigned February 5; due February 25)

**Problem set 3** (assigned February 26; due March 18)

**Problem set 4** (assigned March 19; due April 8)

**Problem set 5** (assigned April 9; due April 29)

**Readings**

Week 3: William Pugh, Skip Lists: A Probabilistic Alternative To Balanced Trees

**Resources**

Advice on writing proofs, by Cathy O'Neil.

Mathematics for Computer Scientists; advice by Eric Lehman (Google), F. Thomson Leighton (MIT) and Albert R Meyer (MIT)

TeXShop (LaTeX installation for Mac OS X)

LaTeX resources and guides
(here,
here,
here and
here).

Algorithms Course Materials by Jeff Erickson (UIUC)