Final Exam Information Information and list of topics (Finalized) - CompSci 161, Spring 2026 (Dillencourt)

Click here for general information about test rules and the test format.

This is the finalized version.

List of topics

The test will cover the material covered in the eight sets of lecture notes (numbered 1 through 8). It will not cover the notes on topological sorting.

The following is a list of topics that may be covered on the Final Exam. The test is cumulative.

Note: There may be questions about the mechanics of algorithms that were covered in the lectures and in the lecture notes. For these questions, you will need to know the algorithms as described in the lectures and in the lecture notes.

• Asymptotic notation (Big O,Theta, Omega, little o)
• Mathematical background:
  • Sums and summations
  • Logarithms and Exponents
  • Floors and Ceilings
  • Factorials and combinations
  • Harmonic numbers
  • Proofs / Proof by induction
  • Basic Probability
• Basic data structures: Arrays, Linked lists, stacks, queues, dictionaries, hash tables
• Binary trees
• Sequential Search
• Binary search: Correctness, analysis, proof of optimality using decision trees
• Sorting, basic terminology (permutations, inversions)
• Comparison-based sorting:
  • Insertion sort
  • Selection sort
  • Quicksort, including worst-case and average-case analysis
  • Merge sort, including two applications:
    • Counting inversions in O(n log n) time and listing inversions in O(n log n + k) time, by appropriately modifying the mergesort algorithm
    • Counting line intersections in O(n log n) time and listing line intersections in O(n log n + k) time, by reducing the problem to inversion counting.
  • Priority queues
  • Binary heaps: basic properties, sift-up, sift-down, insertion, deletion, extract-max, construction (heapify)
  • Heap sort
  • Summary/Comparison of comparison-based sorting methods
  • Stable sorting
  • Lower bounds on comparison-based sorting / decision tree argument
  • Optimally sorting 5 elements
• Address-calculation sorting:
  • Counting sort
  • Bucket sort
  • Radix sort
• External sorting
  • Polyphase Merge
  • Replacement selection (enhancement to polyphase merge)
• Greedy algorithms:
  • Fractional knapsack
  • Task scheduling to minimize the number of processors required
  • Task scheduling on a uniprocessor to maximize the number of tasks that can be performed
  • Huffman trees and Huffman coding
• Divide and conquer
  • Setting up a divide-and-conquer recurrence equation to describe the running time of an algorithm
  • Solving a divide-and-conquer recurrence equation
    • Simplified method
    • Master method
  • Binary search
  • Merge sort
  • Constructing a binary heap
  • Integer multiplication
  • Strassen's method:
    • You do not need to know the detailed equations for Strassen's method
    • You are expected to know that it is possible to multiply two 2-by-2 matrices with 7 scalar multiplications, and understand why this results in a more efficient algorithm for matrix multiplication
• Dynamic Programming
  • The basic approach:
    • Recursion vs. memorized recursion vs. dynamic programming
    • Expressing the solutions: subproblems, description of function, goal, initial conditions, recurrence equation
    • Modifying the program to obtain the optimum strategy in addition to the optimum value
  • Specific dynamic programming algorithms:
    • Optimal Weighted-interval scheduling
    • Truck-loading problem
    • 0/1 Knapsack problem
    • Optimal Matrix chain multiplication
    • Optimal Binary Tree
• Graph algorithms:
  • Graph basics:
    • Undirected/directed graphs
    • Definitions of basic terms associated with graphs and digraphs
    • Formulae for sums of degrees, indegrees, outdegrees
    • Paths, cycles, subgraphs
    • Connected graphs, connected components, trees
    • Representations of graphs: adjacency list, adjacency matrix
• Weighted graphs
  • Shortest paths
    • Definition, formulation of problem
    • Dijkstra's algorithm
  • Minimum spanning trees
    • Definition, formulation of problem
    • Prim-Jarnik algorithm
    • Kruskal's algorithm
      • Cluster management in Kruskal's algorithm. (Note: this is the material on slides 8-29 through 8-31.)