Instructor Fall 2018: Sriram Sankaranarayanan

Topics Covered

This is a graduate course on algorithms. We will focus on studying basic algorithms at a finer level of detail and more advanced algorithms and data structures

  • “Concrete” Mathematics:
    • Solving Recurrences,
    • Basic Combinatorics (review) and
    • Probability Theory.
  • Algorithm Design Approaches
    • Divide and Conquer
    • Dynamic Programming
    • Greedy Algorithms
    • Randomized Algorithms
    • Approximation Algorithms
  • Data Structures
    • Balanced Trees
    • Hashtables
    • Amortized Analysis
    • Union-Find Data Structures
    • Fibonacci Heaps
  • Graph Algorithms
    • Shortest Path (Review)
    • Flow Problems.
  • Complexity Theory: P vs NP
  • Advanced Topics (Subject to Change)
    • Combinatorial Optimization: Randomization and Approximation.
    • Geometric Algorithms
    • String Algorithms
    • Quantum Algorithms

Prerequisites

Undergraduate algorithms (CSCI 3104), data structures (CSCI 2270), discrete mathematics (CSCI 2824) and two semesters of calculus, or equivalents. We will assume that the student has already taken an undergraduate level course on algorithms, and is therefore familiar with the following topics from day one. Students lacking these pre-requisites are strongly encouraged to take CSCI 3104 first.
Stuff you should already have learned and reviewed for this course:

  • Big-O, Big-Omega, Big-Theta notations, and their meanings.
  • Basic data structures: Heaps, and Binary Search Trees.
  • Algorithm Design Approaches:
    • Divide and Conquer including analysis using recurrences
    • Greedy Algorithms
    • Dynamic Programming Algorithms
  • Algorithms for the following primitives:
    • Sorting: bubblesort, mergesort, heapsort, quicksort.
    • Searching
    • Graph Algorithms: Depth/Breadth First Search, Shortest Paths, Spanning Trees.
  • P vs NP: definitions and familiarity NP complete problems.

Programming

We will set programming assignments in Python3. These assignments will require basic
knowledge of writing programs in Python3.

  • Python3 functions, and control loops.
  • Data structures: lists, dictionaries and sets.
  • Classes and Inheritence.
  • Ability to write small projecs in Python3, test and debug.

Textbook

We will use the textbook by Cormen, Leiserson, Rivest and Stein (CLRS). https://mitpress.mit.edu/books/introduction-algorithms.

Course Work/Grades

The course work will consist of (a) weekly problem sets that will involve solving algorithmic problems and some coding; (b) spot exams; (c) final project; and (d) participation.