You are here

Design and Analysis of Algorithms

CSCI 5454
CREDITS: 3

Design and Analysis of Algorithms

Spring 2015


Distance / Main Campus

John Black

MON WED 1:00 pm - 2:15 pm
Classroom: ECCS 1B12

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.

 

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-001 (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-740: Grades will be assigned based on the project (0.4) and problem sets (0.6).

Outline: 

Tentative Schedule:

  • Week 1: Overview, why algorithms? (Lecture 0)
  • Week 2: Divide and conquer
  • Week 3: Randomized data structures
  • Week 4: Greedy algorithms
  • Week 5: Graph algorithms
  • Week 6: Minimum spanning trees
  • Week 7: Network flow
  • Week 8: Phylogenetic trees
  • Week 9: Optimization
  • Week 10: Crowd-source lectures: (i) stable matchings and (ii) disjoint sets and union find
  • Week 11: Spring Break
  • Week 12: Crowd-source lectures: (i) knapsack problems and (ii) multiple sequence alignment
  • Week 13: Crowd-source lectures: (i) Byzantine agreement and (ii) fair division algorithms
  • Week 14: Crowd-source lectures: (i) primality tests and (ii) Sudoku and latin square solvers
  • Week 15: Crowd-source lectures: (i) approximation algorithms and (ii) linear regression
  • Week 16: Crowd-source lectures: (i) link prediction in social networks and (ii) PageRank algorithm

 

Problem Sets:

  • Problem set 1 (assigned January 18; due February 7)
  • Problem set 2 (assigned February 8; due February 28)
  • Problem set 3 (assigned February 29; due March 20)
  • Problem set 4 (assigned March 21; due April 10)
  • Problem set 5 (assigned April 11; due May 1)

Readings:

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.

Textbooks: 

Required:

Optional:

Resources:

Proctor: 

Required

Syllabus: 

Any syllabus provided above may not be the most recent version. Please refer to the course syllabus provided by the instructor of this course.

Previous Course Offerings

There are no previous offerings of this course.