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

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

AO(n² log n)
BO(n³)
CO(n²)
DO(n)

2.Algorithms & complexityHard

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

AΘ(n³)
BΘ(n log n)
CΘ(n²)
DΘ(n^{log₂ 3}), about n^1.585

3.Data structuresMedium

What is the value of the postfix expression 3 4 + 2 * ?

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(n)
BO(1 + α), where α = n / m
CO(log n)
DO(m)

5.Graph theoryMedium

How many different Hamilton circuits H does the complete graph K₅ have? Circuits that differ only in the starting vertex or the direction count as the same.

K₅

H =

6.Graph theoryHard

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

start: Aend: F

d(F) =

3Solutions

1.Algorithms & complexity

Answer: B · O(n³)

Why this is the answer

There are n² entries and each needs n multiplications, giving n³ operations.

Answer

B · O(n³)

2.Algorithms & complexity

Answer: D · Θ(n^{log₂ 3}), about n^1.585

Why this is the answer

Since log₂ 3 ≈ 1.585 > 1, the leaves dominate by the master theorem, beating the O(n²) schoolbook method.

Answer

D · Θ(n^{log₂ 3}), about n^1.585

3.Data structures

Answer: B · 14

Why this is the answer

Push 3 and 4, + gives 7; push 2, * gives 7 × 2 = 14.

Answer

B · 14

4.Data structures

Answer: B · 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

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

5.Graph theory

Answer: H = 12

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.

Count

H = (5 − 1)!/2 = 24/2 = 12

Answer

H = 12

6.Graph theory

Answer: d(F) = 23

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: 9, C: 13

B (9): D: 19, E: 21

C (13)

D (19): F: 31

E (21): F: 23

F (23)

Shortest path

A → B → E → F

d(F) = 23

Answer

d(F) = 23

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