Skip to main content

Theory

Timeline: 64 - 128 hours

Covers everything typically found on the theoretical side of a Data Structures & Algorithms course. Introduction to DSA was covered throughout Program Design.

The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

Extra Resources​

  • Algorithms Illuminated: The textbook authored by the instructor of this set of courses. The textbook covers roughly the same material and can be used as either an alternative or as a supplement to the courses.
  • Discussion forums: Tim Roughgarden actually reads these from time to time.
  • Test cases and test runners: Contains test cases for all assignments in the courses. You can use this to validate the correctness of your implementations. Keep in mind that the input files in the repository may have a slightly different format than the ones you download from Coursera (such as spaces instead of tabs).