Get a head start on program admission

Preview this course in the non-credit experience today! 
Start working toward program admission and requirements right away. Work you complete in the non-credit experience will transfer to the for-credit experience when you upgrade and pay tuition. See How It Works for details.

Cross-listed with DTSA 5503

  • Course Type: Pathway | Breadth
  • Specialization: Foundations of Data Structures and Algorithms
  • Instructor: Dr. Sriram Sankaranarayanan, Professor of Computer Science
  • Prior knowledge needed: You must understand all concepts covered in Dr. Sankaranarayanan's non-credit Algorithms for Searching, Sorting, and Indexing and Trees and Graphs: Basics courses to succeed in this course. We highly recommend successfully completing those two courses in the non-credit experience before starting this course; they are a great option to refresh your skills and ensure you're ready. Note that you cannot apply credit from either of these courses toward MS-CS graduation requirements.

View on Coursera

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.

  • Page Updates: This page is periodically updated. Course information on the Coursera platform supersedes the information on this page. Click the View on Coursera button above for the most up-to-date information.