Learning Outcomes | Review ICS 311

Perform simple algorithm analysis, including:

Best, worst, and average case analysis for algorithms.
Use of Big O notation to characterize runtime of algorithms.
Use of recurrence relations to understand properties of algorithms.

Referencing modules: Analysis examples

Characterize algorithms with respect to asymptotic growth, including:

Growth rates in terms of O, o, Ω, ω or Θ.

Referencing modules: Growth of functions

Define, implement, and characterize behavior of common abstract data types, including

Performance analysis in nanoseconds.
Determination of asymptotic worst-case running time.

Referencing modules: Abstract data types

Carry out probabilistic analysis, including:

Use of indicator random variables to characterize expected values.

Referencing modules: Probabilistic Analysis

Design, implement, and characterize the behavior of the hash table data structure, including:.

Use of open addressing.
Characterizing run-time complexity.
Use of skip lists and chaining.

Referencing modules: Hash Tables

Design and characterize behavior of divide and conquer algorithms, including:

Use of divide-and-conquer in recurrence relations.
Use of Master Method and Substitution methods to bound runtime behavior of algorithms.

Referencing modules: Divide and conquer

Define and characterize behavior of binary search trees, including:

Using Big O notation to characterize runtime behaviors of BST operations.
Implementation of BST variants, including balanced binary trees.

Referencing modules: Binary Search Trees

Characterize behavior of heaps, heapsort, and priority queues, including:

Characterize the asymptotic running time of heap algorithms.
Define and implement various operations on heaps.

Referencing modules: Heapsort

Define and characterize behavior of the quicksort algorithm, including:

Writing applications using quicksort.
Graphically representing the behavior of quicksort on various data sets.

Referencing modules: Quicksort

Characterize the behavior of the balanced tree algorithm, including:

Show insertion and deletion procedures for red-black trees.

Referencing modules: Balanced Trees

Apply the greedy algorithm to problem solving, including:

Solve simple optimization problems using greedy programming techniques.

Referencing modules: Greedy Algorithms

Apply dynamic programming to problem solving, including

Solve simple optimization problems using dynamic programming techniques.

Referencing modules: Dynamic Programming

Define, implement, and characterize behavior of graphs, including:

Use of breadth-first and depth-first search.
Characterize a graph in terms of strongly connected components.
Computing the transpose of a directed graph.

Referencing modules: Graphs

Understand amortized analysis, including:

Use of the accounting method to determine the amortized cost per operation for an algorithm.

Referencing modules: Amortized analysis

Manipulate disjoint sets, including:

Performing union, iterative find-set, and applying the connected-components algorithm.

Referencing modules: Disjoint sets

Characterize behavior of minimum spanning tree data structures, including:

Algorithms to detect minimum spanning trees.
Use of Kruskal’s algorithm.

Referencing modules: Minimum spanning tree

Apply single source shortest path algorithms, including:

Application of the Bellman-Ford algorithm.
Application to directed acyclic graphs.

Referencing modules: Single source shortest paths

Apply all pairs shortest paths algorithms, including:

Use of Floyd-Warshall and Johnson’s algorithsm.

Referencing modules: All pairs shortest paths

Apply the maximum flow algorithm, including:

Detection of conservation property and capacity constraints.
Use of Edmunds-Karp algorithm.

Referencing modules: Maximum flow

Apply linear programming techniques, including:

Modeling Single-Source, Single-Destination.
Modeling Single-Source, All-Destinations.
Rewriting equations and inequalities to be in slack form.

Referencing modules: Linear programming