Data Structures and Algorithms: cram pack

Formula sheets, the key method steps for every topic and 6 practice problems, with full solutions at the back.

New problems Back to the course

In the print window, choose “Save as PDF” to keep a copy on your device.

1Formulas and methods

Graph theory

Handshake lemma: Σ deg(v) = 2|E|
Complete graphs: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Regular graph: |E| = n·k/2
Tree and forest: |E| = n − 1, |E| = n − c
Leaves of a tree: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: circuit: all degrees even; path: exactly 2 odd degrees
Hamilton circuits in K_n: (n − 1)!/2
Dijkstra update: d(v) = min(d(v), d(u) + w(u, v))
Walks of length L: (Mᴸ)_ij

Method

Write down the degree of every vertex; the degrees add up to twice the number of edges.
For Euler questions, check that the graph is connected and count the vertices with odd degree.
For trees, use n − 1 edges and the handshake lemma.
For Dijkstra, keep a table of tentative distances and settle the smallest unsettled vertex each round.
For a minimum spanning tree, sort the edges by weight and skip every edge that closes a cycle (Kruskal), or grow one tree from a start vertex (Prim).

2Practice problems

1.Algorithms & complexityMedium

About how many comparisons does binary search need in the worst case on a sorted array of 1,000,000 elements?

AAbout 100
BAbout 500,000
CAbout 20
DAbout 1,000

2.Algorithms & complexityHard

Is 2²ⁿ in O(2ⁿ)?

ANo, because 2²ⁿ grows more slowly than 2ⁿ
BNo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
CYes, because both are exponential
DYes, because constant factors in the exponent are always ignored in Big O

3.Data structuresMedium

An adjacency matrix for a graph with V vertices uses how much memory?

AO(log V)
BO(V + E)
CO(V²)
DO(E)

4.Data structuresHard

Under simple uniform hashing, what is the expected time of a search in a hash table with chaining, n keys and m buckets?

AO(1 + α), where α = n / m
BO(n)
CO(m)
DO(log n)

5.Graph theoryMedium

A connected graph has 17 vertices and 27 edges. How many edges k must be removed to leave a spanning tree?

|V| = 17|E| = 27

k =

6.Graph theoryHard

Use Dijkstra’s algorithm to find the length d(D) of the shortest path from A to D in the weighted graph.

start: Aend: D

d(D) =

3Solutions

1.Algorithms & complexity

Answer: C · About 20

Why this is the answer

2²⁰ ≈ 1,048,576, so after about 20 halvings only one element remains.

Answer

C · About 20

2.Algorithms & complexity

Answer: B · No, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound

Why this is the answer

A constant added to the exponent gives a constant factor, but a constant multiplying the exponent changes the base and the growth rate.

Answer

B · No, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound

3.Data structures

Answer: C · O(V²)

Why this is the answer

An adjacency matrix stores V × V entries, efficient for dense graphs; adjacency lists use O(V + E), better for sparse graphs.

Answer

C · O(V²)

4.Data structures

Answer: A · O(1 + α), where α = n / m

Why this is the answer

Computing the hash costs O(1) and the expected chain length is α, so keeping α bounded by resizing gives O(1) expected time.

Answer

A · O(1 + α), where α = n / m

5.Graph theory

Answer: k = 11

Euler, Hamilton and trees: a connected graph has an Euler circuit (every edge once, back to the start) when every vertex has even degree, and an Euler path that is not a circuit when exactly two vertices have odd degree; the path then runs from one odd vertex to the other. A Hamilton circuit visits every vertex once; K_n has (n − 1)!/2 of them. A tree on n vertices has n − 1 edges, and a connected graph with m edges keeps a spanning tree after removing m − n + 1 edges.

Edges of a spanning tree

17 − 1 = 16

Edges to remove

k = 27 − 16 = 11

Answer

k = 11

6.Graph theory

Answer: d(D) = 8

Shortest paths and spanning trees: Dijkstra’s algorithm settles one vertex per round: the unsettled vertex with the smallest tentative distance. Its distance is then final, and every neighbour v gets d(v) = min(d(v), d(u) + w(u, v)). Kruskal’s algorithm builds a minimum spanning tree by taking the edges from light to heavy and skipping any edge that would close a cycle; Prim’s algorithm grows one tree from a start vertex by always adding the lightest edge that leaves it. A spanning tree of n vertices has n − 1 edges.

Dijkstra round by round

Each line: the vertex settled, its final distance, and the neighbours whose distance improves.

A (0): B: 3, C: 8

B (3): D: 8, E: 4

E (4): F: 13

C (8)

D (8)

F (13)

Shortest path

A → B → D

d(D) = 8

Answer

d(D) = 8

ExamProblems · examproblems.com/courses/data-structures-and-algorithms