CMPS 2200¶

Introduction to Algorithms¶

Final Exam Review¶

Module 1: Model of Computation and Asymptotic Notation¶

Lecture Topics:¶

  • Asymptotic Notation ($O, \Omega, o, \omega$)

  • Work, Span, Speedup, Amdahl's Law

  • Functional languages and SPARC

  • Computational costs, Parallelism, Work Efficiency, Scheduling

Homework 1¶

  • Asymptotic analysis
  • SPARC to Python
  • Longest run (a divide-and-conquer algorithm, actually)

Lab 1¶

  • Comparison of the empirical performance linear and binary search.

Lab 2¶

  • Calculating the values of recurrences

Skills¶

  • Knowledge of our model of computation (parallelism, speedup, work, span, work efficiency)

  • Know the difference between functional and imperative expressions

  • Translate from SPARC and Python

  • Given a function of $n$, derive asymptotic bounds

Module 2: Recurrences¶

Lecture Topics:¶

  • Why do we care about recurrences?

  • Tree Method

  • Brick Method

  • Example: Integer Multiplication

Homework 2¶

  • More recurrences using the brick method.

  • Comparing the asymptotic performance (work, actually) of 3 algorithms

  • Implement Karatsuba-Ofman

Lab 3¶

  • Practice the tree method and the brick method.

Skills¶

  • Write a recurrence that captures the behavior of a given algorithm

  • Understand the computation graph for an algorithm execution

  • Application of the tree and brick methods to analyze a given algorithm

Module 3: Sequences¶

Lecture Topics:¶

  • Abstract Data Types

  • Operations on sequences

  • Reduce and Iterate

  • scan (using contraction)

Homework 3¶

  • Finding an element in an unsorted list using Divide and Conquer

  • Parenthesis matching

Lab 4¶

  • map and reduce for word occurrences and sentiment analysis

Skills¶

  • Understand how sequence operations such as reduce and scan are parallelized

  • Applying sequence operations to solve problems efficiently

Module 4: Divide-and-Conquer¶

Lecture Topics:¶

  • Reductions, Search Spaces and Brute-Force

  • Divide and Conquer Framework

    • Correctness using induction
    • Running time using recurrences

  • Examples:

    • MergeSort
    • Karatsuba-Ofman
    • reduce
    • scan
    • eTSP
    • MCSS

Lab 5¶

  • Count Sort

Skills¶

  • Provide a brute force search algorithm along with its work/span for a given algorithm

  • Understand reductions and how they relate to problem complexity

  • Devise divide and conquer algorithms and prove their correctness and running time

Module 5: Randomization¶

Lecture Topics:¶

  • Basic Probability

  • Selection

  • Quicksort

Homework 4¶

  • Markov's Inequality

  • Las Vegas and Monte Carlo Algorithms

  • Quicksort performance

Skills¶

  • Formulate expected work/span

  • Compute probabilities and expectations

Module 6: Greedy Algorithms¶

Lecture Topics:¶

  • Greedy choice and optimal substructure properties

  • Unit Task Scheduling

  • Fractional Knapsack

  • Binary and Meldable Heaps

  • Huffman Coding

Lab 6¶

  • Heap Implemenation

Skills¶

  • Prove greedy choice and optimal substructure properties

Module 7: Dynamic Programming¶

Lecture Topics:¶

  • Dynamic Programming paradigm

  • 0-1 Knapsack

  • Edit Distance

  • Longest Increasing Subsequence=

Homework 5¶

  • Huffman Encoding

  • Proving that greedy algorithms are optimal (or not)

    • Greedy choice
    • Optimal Substructure

  • Edit Distance

Lab 7¶

  • Top-down and bottom-up memoization for dynamic programming

Skills¶

  • Formulate and prove optimal substructure property

  • Utilize top-down or bottom-up memoization

  • Analyze work/span

Module 8: Graph Search and Shortest Paths¶

Lecture Topics:¶

  • Graph representation and data structures

  • Breadth First Search, Depth First Search

  • Dijkstra's Algorithm

  • Bellman-Ford Algorithm

  • All-pairs Shortest Paths with Johnson's Algorithm

Homework¶

  • Shortest Paths (cost followed by number of edges)

  • Improving Dijkstra's

  • MSTs

Lab 8¶

  • Connectivity and reachability

Skills¶

  • Use graph search/shortest path algorithms

Module 9: Trees and Contraction¶

Lecture Topics:¶

  • Spanning Trees and Minimum Spanning Trees

  • Prim's Algorithm

  • Kruskal's Algorithm

  • Edge and Star contractions

  • Borůvka's Algorithm

Lab 9¶

  • Connected components using Prim's

Lab 10¶

  • Edge contraction

Skills¶

  • Be able to reason about MSTs and graph partitioning

Module 10: Computational Complexity and NP-Completeness¶

Lecture Topics:¶

  • $\mathcal{P} = \mathcal{NP}$ ?
  • Reductions and NP-completeness
  • $\mathcal{NC} = \mathcal{P}$ ?

Skills¶

  • Reductions