Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Prelims Mathematics and Computer Science > CS1: Design & Analysis of Algorithms > Flashcards

CS1: Design & Analysis of Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Algorithm

Insertion Sort

A 
for j = 1 to A.length - 1
  key = A[j+1]
  i = j
  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1
  A[i+1] = key
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Knowledge

Insertion Sort Running Time

A

O(n²)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Knowledge

Divide and Conquer

4 points

A
  • Divide a problem into a problems whose size is original size divided by b > 1
  • Recursion stops when problems small enough to be solved by brute force
  • Solutions combined to build a solution of original solution
  • Work done in three places: dividing the problem, solving subproblems and combining their solutions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Theorem

The Master Theorem

A

Suppose T(n) ≤ aT(⌈n/b⌉) + O(nᵈ) for some constants a > 0, b > 1 and d ≥ 0
Then T(n) = O(nᵈ) if d > log_(b)a, T(n) = O(n^(log_(b)a)) if d < log_(b)a or T(n) = O(nᵈlog n) if d = log_(b)a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Proof

(The Master Theorem)
Suppose T(n) ≤ aT(⌈n/b⌉) + O(nᵈ) for some constants a > 0, b > 1 and d ≥ 0
Then T(n) = O(nᵈ) if d > log_(b)a, T(n) = O(n^(log_(b)a)) if d < log_(b)a or T(n) = O(nᵈlog n) if d = log_(b)a

3 points

A
  • Recursion tree has branching factor a and depth log_b n
  • Formulate expression for upper bound of T(n) containing a geometric series
  • Consider different cases and the sum of the geometric series
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Algorithm

Merge Sort

A 
MERGE-SORT(A, p, r)
 if r > p + 1
  q = ⌊(p + r)/2⌋
  MERGE-SORT(A, p, q)
  MERGE-SORT(A, q, r)
  MERGE(A, p, q, r)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Proof

The running time of every comparison-based sorting algorithm is Ω(n log n)

6 points

A
  • Every leaf of the decision tree is a permutation of {a₁, a₂, …, aₙ}
  • The decision tree has n! leaves
  • Every binary tree of depth d has at most 2ᵈ leaves
  • In the worst case, the algorithm explores d nodes
  • n! ≤ 2ᵈ
  • Hence running time is Ω(log n!) = Ω(n log n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Knowledge

The Selection Problem

2 points

A
  • Input: A set of n (distinct) numbers and a number i, with 1 ≤ i ≤ n
  • Output: The iᵗʰ-order statistic of the set
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Knowledge

Selection Algorithm Running Time

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Algorithm

Integer Multiplication

3 points

A
  • Split x = 2^(n/2) x₁ + x₂, y = 2^(n/2) y₁ + y₂
  • x y = 2ⁿ x₁ y₁ + 2^(n/2)(x₁ y₂ + x₂ y₁) + x₂ y₂
  • Computing x₁ y₁, x₂ y₂, (x₁ + x₂)(y₁ + y₂) suffice
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Knowledge

Integer Multiplication Running Time

3 points

A
  • Additions and 3 multiplications of (n/2)-bit numbers are required
  • T(n) = 3 T(n/2) + O(n)
  • T(n) = O(n^(log₂ 3))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Knowledge

Strassen’s Algorithm Running Time

4 points

A
  • Split matrices X, Y into 8 (n/2)×(n/2) submatrices
  • Calculate XY by making additions and 7 multiplications of submatrices
  • T(n) = 7 T(n/2) + O(n²)
  • T(n) = O(n^(log₂ 7) ≈ O(n^2.81)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Knowledge

MAX-HEAPIFY

2 points

A
  • Input: Assume left and right subtrees of i are max-heaps
  • Output: Subtree rooted at i is a max-heap
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Algorithm

MAX-HEAPIFY

A 
MAX-HEAPIFY(A, i)
 n = A.heap-size
 l = 2i
 r = 2i + 1
 if l ≤ n and A[l] > A[i]
  largest = l
 else largest = i
 if r ≤ n and A[r] > A[largest]
  largest = r
 if largest ≠ i
  exchange A[i] with A[largest]
  MAX-HEAPIFY(A, largest)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Knowledge

MAX-HEAPIFY Running Time

4 points

A
  • Θ(1) to find largest among A[i], A[2i] and A[2i + 1]
  • Subtree rooted at a child of node i has size upper bounded by 2n/3
  • T(n) ≤ T(2n/3) + Θ(1)
  • T(n) = O(log n) by the Master Theorem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Knowledge

MAKE-MAX-HEAP

2 points

A
  • Input: An (unsorted) integer array A of length n
  • Output: A heap of size n
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Algorithm

MAKE-MAX-HEAP

A 
MAKE-MAX-HEAP(A)
  A.heap-size = A.length
  for i = ⌈(n + 1)/2⌉ - 1 downto 1
    MAX-HEAPIFY(A, i)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Knowledge

MAKE-MAX-HEAP Running Time

3 points

A
  • Number of nodes of height h is upper bounded by n/2ʰ
  • Running time of MAX-HEAPIFY on a node of height h is O(h)
  • T(n) ≤ Σ (n/2ʰ)O(h) = O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Algorithm

Heapsort

A 
HEAPSORT(A)
  MAKE-MAX-HEAP(A)
  for i = A.heap-size downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY(A, 1)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Knowledge

Heapsort Running Time

A

O(n log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Definition

Priority Queue

A

An abstract data structure for maintaining a set of elements, each with an associated value called a key, which either gives priority to elements with larger or smaller keys

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Knowledge

Operations Supported by a Max-Priority Queue

4 points

A
  • INSERT(S, x, k)
  • MAXIMUM(S)
  • EXTRACT-MAX(S)
  • INCREASE-KEY(S, x, k)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Algorithm

EXTRACT-MAX

Priority Queues

A 
HEAP-EXTRACT-MAX(A)
  if A.heap-size < 1
    error "heap underflow"
  max = A[1]
  A[1] = A[A.heap-size]
  A.heap-size = A.heap-size - 1
  MAX-HEAPIFY(A, 1)
  return max
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Knowledge

EXTRACT-MAX Running Time

Priority Queues

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Algorithm

HEAP-INCREASE-KEY

A 
HEAP-INCREASE-KEY(A, i, key)
  if key < A[i]
    error "new key is smaller than existing key"
  A[i] = key
  while i > 1 and A[Parent(i)] < A[i]
    exchange A[i] with A[Parent(i)]
    i = Parent(i)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Knowledge

HEAP-INCREASE-KEY Running Time

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Knowledge

Dynamic Programming

5 points

A
  • Define a sequence of subproblems with the following properties:
    1. The subproblems are ordered from smallest to largest
    2. The largest problem is the original problem
    3. The optimal solution of a subproblem can be constructed from the optimal solutions of smaller subproblems (Optimal Substructure property)
  • Solve the subproblems from smallest to largest, storing each solution
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Knowledge

Divide-and-Conquer vs Dynamic Programming

5 points

A
  • DP is an optimization technique whereas D&C is not normally used to solve optimization problems
  • Both split the problem into parts, find solutions to the parts and combine them into a solution of the larger problem
  • In D&C, the subproblems are significantly smaller than the original problem and do not overlap (share sub-subproblems)
  • In DP, the subproblems are not significantly smaller and overlap
  • In D&C, the dependency of the subproblems can be represented by a tree whereas in DP, it can be represented by a directed path from the smallest to largest subproblem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Knowledge

The Change-Making Problem

2 points

A
  • Input: Positive integers 1 = x₁ < x₂ < … < xₙ and v
  • Output: Given an unlimiteed supply of coins of denominations x₁, …, xₙ, find the minimum number of coins needed to sum up to n
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Knowledge

The Knapsack Problem

3 points

A
  • A knapsack holds a total weight of at most W kg
  • There are n items, of weight w₁, …, wₙ ∈ ℕ and value v₁, …, vₙ ∈ ℕ
  • Find the most valuable combination of items, which can fit into the knapsack without exceeding its weight
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Knowledge

The Edit Distance Problem

4 points

A
  • An edit is an insertion, deletion or character substitution
  • The edit distance between two words is the minimum number of edits needed to transform one to the other
  • Input: Two strings x[1..m] and y[1..n]
  • Output: The edit distance between x and y
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Knowledge

Depth-First Search

2 points

A
  • Input: A graph G = (V, E)
  • Output: A backpointer π[v], discovery time d[v] and finish time f[v] for each v ∈ V
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Algorithm

Depth-First Search

A 
DFS(V, E)
 for u ∈ V
  colour[u] = WHITE
  π[u] = NIL
 time = 0
 for u ∈ V
  if colour[u] = WHITE
   DFS-VISIT(u)
34
Q

Algorithm

DFS-VISIT

A 
DFS-VISIT(u)
 time = time + 1
 d[u] = time
 colour[u] = GREY
 for v ∈ Adj[u]
  if colour[v] = WHITE
   π[v] = u
   DFS-VISIT(v)
 time = time + 1
 f[u] = time
 colour[u] = BLACK
35
Q

Knowledge

Depth-First Search Running Time

3 points

A
  • DFS-VISIT is called exactly once for each v ∈ V
  • DFS-VISIT takes time O(|Adj(v)|)
  • ∑ |Adj(v)| = |E| so T = O(|V| + |E|)
36
Q

Theorem

Parenthesis Theorem

A

For all u, v exactly one of the following holds
1. d[u] < f[u] < d[v] < f[v] or d[v] < f[v] < d[u] < f[u] and neither of u and v is a descendant of the other
2. d[u] < d[v] < f[v] < f[u] and v is a descendant of u
3. d[v] < d[u] < f[u] < f[v] and u is a descendant of v

37
Q

Knowledge

Tree Edge

3 points

A
  • Edges of the DFS forest
  • If (u, v) is a tree edge then v is white when (u, v) is explored
  • d[u] < d[v] < f[v] < f[u]
38
Q

Knowledge

Back Edge

3 points

A
  • Lead from a node to an ancestor in the DFS forest
  • If (u, v) is a back edge, then v is grey when (u, v) is explored
  • d[v] < d[u] < f[u] < df[v]
39
Q

Knowledge

Forward Edge

3 points

A
  • Lead from a node to a non-child descendant in the DFS forest
  • If (u, v) is a forward edge then v is black when (u, v) is explored
  • d[u] < d[v] < f[v] < f[u]
40
Q

Knowledge

Cross Edge

3 points

A
  • Lead neither to an ancestor nor a descendant
  • If (u, v) is a cross edge then v is black when (u, v) is explored
  • d[v] < f[v] < d[u] < f[u]
41
Q

Lemma

Characterisation

A

A directed graph has a cycle if and only if its DFS forest has a back edge

42
Q

Knowledge

Topological Sort

3 points

A
  • A topological sort of a DAG G = (V, E) is a total ordering of vertices < ⊆ V×V such that if (u, v) ∈ E then u < v
  • Input: A DAG (V, E)
  • Output: Elements of V sorted in topological order
43
Q

Algorithm

Topological-Sort

A 
TOPOLOGICAL-SORT(V, E)
 Call DFS(V, E) to compute finish times f[v] for all v ∈ V
 Output vertices in orer of decreasing finish time
44
Q

Knowledge

Topological Sort Running Time

A

O(|V| + |E|)

45
Q

Knowledge

Strongly Connected Components

2 points

A
  • Input: A directed graph G
  • Output: Elements of each SCCs of G output in turn
46
Q

Algorithm

Strongly Connected Components

A 
SCC(G)
 Call DFS(G) to compute finishing times f[u] for all u
 Compute Gᵀ
 Call DFS(Gᵀ) visiting the vertices in order of decreasing f[u]
 Output the vertices in each tree of the DFS forest formed in second DFS as a separate SCC
47
Q

Knowledge

Strongly Connected Components Running Time

A

O(|V| + |E|)

48
Q

Knowledge

Breadth-First Search

3 points

A
  • δ(u, v) is the minimum number of edges on a path from u to v, if such a path exists; otherwise δ(u, v) = ∞
  • Input: A graph G = (V, E) and a source vertex s ∈ V
  • Output: For each v ∈ V, an integer d[v] and a back pointer π[v] such that d[v] = δ(s, v) and π[v] = u is the predecessor of v on a shortest path from s to v if there is such a path; otherwise π[v] = NIL
49
Q

Algorithm

Bread-First Search

A 
BFS(V, E, s)
 d[s] = 0
 π[s] = NIL
 for each u ∈ V - {s}
  d[u] = ∞
  π[u] = NIL
 Q = ∅
 ENQUEUE (Q, s)
 while Q ≠ ∅
  u = DEQUEUE(Q)
  for each v ∈ Adj[u]
   if d[v] = ∞
    d[v] = d[u] + 1
    π[v] = u
    ENQUEUE(Q, v)
50
Q

Knowledge

BFS Running Time

3 points

A
  • O(|V|) to initialise and enqueue / dequeue each vertex once
  • O(|E|) as each edge (u, v) is examined only when u is dequeued
  • So overall running time is O(|V| + |E|)
51
Q

Knowledge

Dijkstra’s Algorithm

4 points

A
  • d[v] is equal to the distance from s to v
  • π[v] is the predecessor of v on a shortest path from s to v, if such a path exists or π[v] = NIL otherwise
  • Input: A directed or undirected graph (V, E), s ∈ V, non-negative weight w: E → ℝ
  • Output: For each v ∈ V, d[v] and π[v]
52
Q

Algorithm

Dijkstra

A 
DIJKSTRA(V, E, w, s)
 for each v ∈ V
  d[v] = ∞
  π[v] = NIL
 d[s] = 0
 Q = MAKE-QUEUE(V) with d[v] as keys
 while Q ≠ ∅
  u = EXTRACT-MIN(Q)
  for each vertex v ∈ Adj[u]
   if d[u] + w(u, v) < d[v]
    d[v] = d[u] + w(u, v)
    π[v] = u
    DECREASE-KEY(Q, v, d[v])
53
Q

Knowledge

Dijkstra’s Algorithm Running Time

A

O((|V| + |E|)log|V|)

54
Q

Knowledge

Bellman-Ford Algorithm

2 points

A
  • Input: A directed or undirected graph (V, E), s ∈ V, w: E → ℝ
  • Output: FALSE if there exists a negative-weight cycle reachable from s otherwise TRUE, and for each v ∈ V, d[v] and π[v]
55
Q

Algorithm

Bellman-Ford

A 
BELLMAN-FORD(V, E, w, s)
 for each v ∈ V
  d[v] = ∞
  π[v] = NIL
 d[s] = 0
 for i = 1 to |V| - 1
  for each edge (u, v) ∈ E
   if d[u] + w(u, v) < d[v]
    d[v] = d[u] + w(u, v)
    π[v] = u
 for each edge (u, v) ∈ E
  if d[u] + w(u, v) < d[v]
   return FALSE
 else
  return TRUE
56
Q

Knowledge

Bellman-Ford Algorithm Running Time

A

O(|V||E|)

57
Q

Knowledge

Shortest Path in DAGs

2 points

A
  • Input: A DAG G = (V, E) with weight w: E → ℝ and a source vertex s
  • Output: For each v ∈ V length d[v] of shortest path from s to v
58
Q

Algorithm

Shortest Paths in DAGs

A 
TOPOLOGICAL-SORT(V, E)
for each v ∈ V
 d[v] = ∞
 π[v] = NIL
d[s] = 0
for each u ∈ V in topological order
 for each v ∈ Adj[u]
  if d[v] > d[u] + w(u, v)
   d[v] = d[u] + w(u, v)
   π[v] = u
59
Q

Knowledge

Shortest Paths in DAGs Running Time

A

O(|V| + |E|)

60
Q

Knowledge

Floyd-Warshall Algorithm

4 points

A
  • Suppose the vertex set is {1, …, n}
  • Let d[i, j; k] be the length of shortest path from i to j all of whose intermediate nodes are in the interval [1, k]
  • d[i, j; 0] = w(i, j) if (i, j) ∈ E, otherwise d[i, j; 0] = ∞
  • d[i, j; k+1] = min{d[i, j; k], d[i, k+1; k] + d[k+1, j; k]}
61
Q

Algorithm

Floyd-Warshall

A 
FLOYD-WARSHALL(V, E, w)
 for i = 1 to |V|
  for j = 1 to |V|
   d[i, j; 0] = ∞
 for each edge (i, j) ∈ E
  d[i, j; 0] = w(i, j)
 for k = 0 to |V| - 1
  for i = 1 to |V|
   for j = 1 to |V|
    d[i, j; k+1] = min{d[i, j; k], d[i, k+1; k] + d[k+1, j; k]}
62
Q

Knowledge

Floyd-Warshall Algorithm Running Time

A

O(|V|³)

63
Q

Definition

Greedy

A

At each step, the algorithm makes the choice that offers the greatest immediate benefit without reconsidering this choise at subsequent steps

64
Q

Knowledge

Spanning Trees

5 points

A
  • A spanning tree of a graph G = (V, E) is a subgraph with edge-set T ⊆ E
  • T is a tree
  • For each u ∈ V, there is some v ∈ V such that (u, v) or (v, u) is in T
  • A spanning tree is a minimal connected subgraph
  • A spanning tree is a maximal acyclic subgraph
65
Q

Definition

Safe

A

Let A ⊆ E be a subset of a MST T.
We say that an edge (u, v) is safe for A iff A ∪ {(u, v)} is a subset of some MST.

66
Q

Definition

Cut

A

A partition of the vertex-set into two subsets S and V\S

67
Q

Definition

Edge Crosses a Cut

A

An edge (u, v) ∈ E crosses a cut (S, V\S) if one endpoint is in S and the other in V\S

68
Q

Definition

Set of Edges Respects a Cut

A

A set of edges A ⊆ E respects a cut if no edge in A crosses the cut

69
Q

Definition

Light Edge Crossing a Cut

A

An edge is a light edge crossing a cut if its weight is the minimum of all edges that cross the cut

70
Q

Lemma

The Cut Lemma

A

Let A be a subset of some MST.
If (S, V\S) is a cut that respects A, and (u, v) is a light edge crossing the cut, then (u, v) is safe for A.

71
Q

Proof

(The Cut Lemma)
Let A be a subset of some MST.
If (S, V\S) is a cut that respects A, and (u, v) is a light edge crossing the cut, then (u, v) is safe for A.

3 points

A
  • Consider path between u and v
  • T’ has edge crossing the cut replaced with (u, v)
  • T’ is a tree with minimum weight that includes A
72
Q

Knowledge

Disjoint-Set Data Structure

2 points

A
  • Maintains a collection S = {S₁, …, Sₖ} of disjoint dynamic sets
  • Each set is identified by a representative, a member of the set
73
Q

Knowledge

Disjoint-Set Data Structure Operations

3 points

A
  • MAKE-SET(x) makes a new set {x} and adds it to S
  • UNION(x, y) removes Sₓ and Sᵧ from S and adds the new set Sₓ ∪ Sᵧ to the collection S
  • FIND-SET(u) returns the representative of the set containing u
74
Q

Knowledge

Kruskal’s Algorithm

2 points

A
  • Start from A = ∅
  • At every step, pick edges with the smallest weight and add it to A if it does not create cycles
75
Q

Algorithm

Kruskal

A 
KRUSKAL(V, E, w)
 A = ∅
 for each v ∈ V
  MAKE-SET(v)
 Sort E into increasing order by weight w
 for each edge (u, v) taken from the sorted list
  if FIND-SET(u) ≠ FIND-SET(v)
   A = A ∪ {(u, v)}
   UNION(u, v)
 return A
76
Q

Knowledge

Kruskal’s Algorithm Running Time

3 points

A
  • O(|E|log|E| + |V|²) for linked-list implementation of disjoint-set data structure
  • O(|E|log|E|) for weighted linked-list
  • O(|E|log|E|) for disjoint-set forest
77
Q

Knowledge

Prim’s Algorithm

3 points

A
  • Set S = {r} and A = ∅
  • At every step, find a light edge (u, v) connecting u ∈ S to v ∈ V \ S
  • Update S to S ∪ {v} and A to A ∪ {(u, v)}
78
Q

Algorithm

Prim

A 
PRIM(V, E, w, r)
 Q = ∅
 for each u ∈ V
  key[u] = ∞
  π[u] = NIL
  INSERT(Q, u)
 DECREASE-KEY(Q, r, 0)
 while Q ≠ ∅
  u = EXTRACT-MIN(Q)
  for each v ∈ Adj[u]
   if v ∈ Q and w(u, v) < key[v]
    π[v] = u
    DECREASE-KEY(Q, v, w(u, v))
79
Q

Knowledge

Prim’s Algorithm Running Time

4 points

A
  • Initialising key[v] and π[v] for every vertex takes O(|V|)
  • Each DECREASE-KEY operation takes O(log|V|)
  • While loop takes |V| EXTRACT-MIN and at most |E| DECREASE-KEY operations
  • Hence overall running time is O(|E|log|V|)
80
Q

Knowledge

Activity Selection

2 points

A
  • Given a set of activities (sᵢ, fᵢ), i = 1, …, n, select a maximum-size subset of activities that do not overlap
  • Find the activity with minimum finish time, add it to the solution, remove all overlapping activites and repeat
81
Q

Algorithm

Activity Selection

A 
ACTIVITY-SELECTION(s, f)
 Sort the activites in order of increasing f-values
 A = {1}
 k = 1
 for j = 2 to n
  if s[j] ≥ f[k]
   A = A ∪ {j}
   k = j
 return A
82
Q

Knowledge

Activity Selection Running Time

3 points

A
  • The greedy algorithm takes O(n log n) steps to sort the activites
  • It takes O(n) steps to process the activities
  • In total, it takes O(n log n) steps

Prelims Mathematics and Computer Science (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions