CSCI 429: Advanced Algorithms and Data Structures Fall 2025
Test 1 Studying
ATD Array: Write pseudocode for the functions init, set, get. Analyze their running time. Argue for
the correctness.
Dynamic Programming: You will be given a problem and asked to develop an algorithm to solve it.
You may or may not be told that DP is the method to apply, so it might be necessary to recognize
when DP can be usefully applied.
You may be asked to give the recurrance relation that determines the relationship between the values
that are memoized, and you may by asked to argue the correctness. You may be asked
to trace the execution of one of the DP solutions we studied, such as minimum contiguous sum, which is
a streaming algorithm (a single pass over the data which computes some statistics of the data).
Greedy Algorithms. Give an example of when plain greed does not yield the optimal solution. Jeff Erickson's text has
good coverage of the Interval Scheduling problem and some greedy strategies. For each strategy,
either show it doesn't work (come up with a counter example for the optimality of that strategy's
solution) or prove it does. Coin denomination and change-making -- given coin denominations, find
an amount of change to make where the greedy algorithm fails to be optimal.
Gale-Shapley Algorithm: Given a set of Doctors and Hospitals and their rankings (1 is top choice),
use the Gale-Shapley Algorithm to determine a stable matching. Given a matching, determine if it is stable.
Given an alternative algorithm, come up with a counter-example to its optimality (or prove it is optimal)
Huffman Coding. Trace an execution of the algorithm by showing the contents of the priority queue at various points in the execution. Show the resulting codes.
Amortized Analysis. Given a data structure and algorithm, analyze the algorithms using one of the
amortization techniques to show that the running time for the operations is within a given amortized
bound. E.g., multipop stack, binary counter, and the BinRep Priority Queue.