CIS 1210 TA Review

Definition of matching GS alg

a subset S of ordered pairs in M × W such that each member of M and each member of W appears in at most one pair in S

Def of perfect matching GS alg

it is a matching and has the property that each member of M and each member of W appears in exactly one pair of S’

What does it mean for pair (m, w’) to be called an instability wrt matching S in GS alg?

(m, w’) does not belong to S, but each of m and w’ prefers the other to their partner in S

When is a matching stable GS alg?

1. it is perfect 2. there are no instabilities with respect to S

In GS, each man proposing is matched with his _________ valid partner and each woman is matched with her __________ valid partner.

best, words

What is a valid partner mean in GS alg?

A woman w is a valid partner of a man m if there is a stable matching that contains the pair (m, w)

What is POC method for insertion sort?

Initialization, maintenance, & termination

Definition. O-notation

Definition. Ω-notation

Definition. Θ-notation

Definition. o-notation

Definition. ω-notation

Definition of SMT

Θ(n log n)

Θ(n²)

Θ(n^lg3)

Θ(n²)

Let t be the iteration of the first call to Partition during which one of the elements from yi , yi+1, ..., yj is used as the pivot. Why must such a pivot exist?

Every element becomes a pivot exactly once.

What is the probability in quicksort that yi or yj is chosen as the pivot where i < j?

2/(j - i + 1)

What can the following be simplified to in qucksort?

What is a naive runtime for quicksort when you manually choose pivot?

O(n²)

What is naive runtime for counting inversions alg?

O(n²)

What is rough algorithm for counting inversions?

Similar to merge sort we divide array and half and count inversions + sort. Do same for combine step except when a > b, b must be smaller than all remaining elements in A so we add all remaining elements to count of inversions.

What is the runtime for optimized counting inversions?

O(nlgn)

What is the lower bound on the number of elements <= median of medians x? What about lower bound on the number of elements >= median of medians x? Based on lower bound, what is an upper bound on the worst case # of elements select is called on recursively?

at most 7n/10 + 6 elements = n - (3n/10 - 6)

What is alg for select?

What is the runtime for select?

O(n) proof by substitution

Prove runtime for select

Explain why sorting is important in closest pair.

Sorting is important in the closest‑pair algorithm because it makes the combine step run in linear time. After dividing the points into left and right halves, the algorithm needs to examine only the points that lie in the vertical strip of width 2δ. To do this efficiently, we maintain the points sorted by y‑coordinate. This ordering is crucial: it ensures that when scanning the strip, each point only needs to be compared with the next at most 7 points in y‑order.

This 7‑point bound comes from the geometric packing argument (sometimes explained using the pigeonhole principle): in a δ×2δ rectangle, you cannot fit more than 8 points that are all at least δ apart. Therefore, once the strip is sorted by y, the algorithm only checks a constant number of neighbors per point, making the combine step O(n).

What is the runtime for push, pop, peek, isEmpty operations for a stack?

When do you decrease size of the array capacity in stack pop?

When the stack is equal to ¼ of the array capacity

What is the runtime for enqueue, dequeue, peek, isEmpty operations for a queue?

What are the properties of a binary heap data structure?

It is a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.

What is the max-heap property? min-heap property?

Max-heap: A[Parent(i)] ≥ A[i], Min-heap: A[Parent(i)] ≤ A[i]

What is the height of a heap?

⌊lgn⌋

The root is stored at index 1, and if a node is at index i, then:
Parent(i): _________
Left(i): ____________
Right(i): __________

What two properties are stored to access heaps?

A.length, which is the number of elements in the array, and A.heapsize, which is the number of array elements that are actually part of the heap. Even though A is potentially filled with numbers, only the elements in A[1..A.heapsize] are actually part of the heap.

What is the runtime of Max-Heapify procedure?

O(lg n)

What is the runtime of Build-Max-Heap procedure?

O(n)

What is the runtime of Heapsort procedure?

O(n lg n)

Explain algorithm for Max-Heapify.

What is an upper bound on the number of children in the L/R subtrees in max-heapify?

L tree >= R tree. Worst case is when bottom level is half full so n/2 nodes belong to L tree. Remaining n/2 nodes are split evenly. Upper bound <= 2n/3

What is the time recurrence for max-heapify?

What is the algorithm for Build-Max-Heap?

How many nodes could there be in binary tree of height h?

2^h+1-1

What is the maximum number of nodes on the bottom level a heap?

2h nodes on the bottom level
2h=2h+1/2= (n + 1)/2 <= n/2

What is the loop invariant for build max heap?

Explain linear time for Build-Max-Heap.

What is the algorithm for heapsort?

What is the algorithm for looking at heap maximum? Runtime?

Return the value at the top of the heap. Θ(1)

What is the algorithm for extracting heap maximum? Runtime?

O(lg n)

What is the algorithm for extracting heap increase key? Runtime?

O(lg n)

What is the algorithm for max heap insert key? Runtime?

O(lg n)

What is the definition of a prefix code for S?

Def of ABL (Average bits per letter) in Huffman’s encoding

Suppose we take a rooted tree T in which each node that is not a leaf has exactly two children; i.e. T is a binary tree. Further, suppose that the number of leaves is equal to the size of the alphabet S, and we label each leaf with a distinct letter in S. Such a labeled binary tree T naturally describes a prefix code. For each letter x ∈ S, we follow the path from the root to the leaf labeled x. Each time the path goes from a node to its left child, we write down a 0, and each time the path goes from a node to its right child, we write down a 1. We take the resulting string of bits as the encoding for x.

Lemma 1. The encoding of S constructed from T as described above is a prefix code

One thing to note immediately about the optimal binary tree T is that it is full. That is, each node that is not a leaf has exactly two children. To see why, suppose the optimal tree weren’t full. Then we could take any node with only one child, remove it from the tree, and replace it by its lone child. This would create a new tree T 0 such that ABL(T 0 ) < ABL(T), contradicting the optimality of T.

Specifically, let v be a leaf in T ∗ whose depth is a large as possible. Leaf v has a parent u, and since T ∗ must be full, u has another child, w, which is a sibling of v. Note that w is also a leaf in T ∗ , otherwise, v would not be the deepest possible leaf. Now, since v and w are siblings at the greatest depth, our level-by-level labelling process will reach them last. The leaves at this deepest level will receive the lowest frequency letters, and since we argued above that the order in which we assign these letters to the leaves within this level doesn’t matter.

Describe Huffman’s Algorithm

Formal definition of layers in BFS

Describe BFS algorithm

Describe DFS algorithm

Definition of tree edges, back edges, forward edges, cross edges.

What does white, gray and black mean in classifying edges (tree, back, forward, cross)?

We’d like to characterize bipartite graphs. In order to do so, let’s consider some examples of bipartite graphs. Clearly, a triangle graph is not bipartite. More generally, any cycle of odd length cannot be bipartite. If C = (v1 v2 ... v2k v2k+1) is an odd cycle which we try to two-color, note that the even-indexed nodes and odd-indexed nodes must have different colors. Since there is an edge between v1 and v2k+1, both of which are the same color, it is impossible to two-color an odd cycle. Moreover, if a graph G simply contains an odd cycle, it cannot be two-colorable.

Describe Kahn’s Algorithm for Topological Ordering

Describe Tarjan’s Algorithm for Topological Ordering

Prove Tarjan’s Algorithm for Topological Ordering

Describe Kosaraju’s Algorithm

What is the Dijkstra’s invariant for dist(s, t)?

At any point in time, dist[t] ≥ d(s, t), and when t is finished, dist[t] = d(s, t)

Describe Dijkstra's algorithm

What is the runtime of Dijkstra’s?

O((V + E) lgV)

Describe Shortest Path in DAG Algorithm

What is the runtime for Shortest Path in DAG Algorithm?

O(n + m)

What is the POC for Shortest Path in DAG Algorithm?

Definition of spanning subgraph

A spanning subgraph of G is a subgraph of G that contains all the vertices in G.

Definition of a minimum weight spanning subgraph

A minimum weight spanning subgraph or minimum spanning subgraph is a spanning subgraph whose total cost is the minimum over all other spanning subgraphs.

Proposition 1. Let T be a minimum cost set of edges as described above. Then (V, T) is a tree

Describe Prim’s Algorithm

Another way to phrase Prim’s algorithm is that it starts with T = {s} and at each step, chooses the lightest weight edge crossing the cut (T, V − T) (here we use T as a set of vertices) and adds it to the growing tree.

What is the runtime of Prim’s algorithm?

O(mlgn)

Describe Kruskal’s algorithm

What data structure is needed in Kruskal’s algorithm?

Union find

What is the runtime of Kruskal’s?

O(m log m) = O(m log n), dominates all union find operations

Describe the algorithm for reverse-delete