CSC 349 Algorithms & Definitions
Questions and Answers
Big O Notation - answer An analysis / upper bound on the running time of an
algorithm.
slowest to fastest:
O(1)
O(log n)
O(n^c) (where 0<c<1)
O(n)
O (n * log n)
O(n^2)
O(n^c) (where c > 1)
O(c ^ n)
O(n!)
O(n^n)
Rank the following running times in order from fastest to slowest:
17n, n^3, 2^n, n!, 36, log b (n), 48 n log b (n), 367 n^2 log b (n), n^n - answer 36, log
b (n), 17n, 48 n log b (n), 367 n^2 log b (n), n^3, 2^n, n!, n^n
T(n) = T(n/2) + O(n) - answer O(n)
n + n/2 + n/4 + ... +n/n
n * (1 + 1/2 + 1/4 + ... + 1/n)
<= O(2n)
= O(n)
T(n) = T(n/2) + O(n^2) - answer O(n^2)
n^2 + (n/2)^2 + (n/4)^2 + ... + (n^2 / n ^ 2)
n^2 * ( 1 + 1/4 + 1/16 + ... + 1/n^2)
<= O(4/3 * n^2)
= O(n^2)
T(n) = 3T(n/3) + O(1) - answer O(n)
1 + 3 + 9 + ... + n/3 + n
n/n + n/(n/3) + n/(n/9) + ... + n/3 + n
n * (1/n + 1/(n/3) + ... + 1/3 + 1)
<= O(3 * n)
,= O (n)
T(n) = T(n/3) + O(n) - answer O(n)
n + n/3 + n/6 + ... + 1
n + n/3 + n/6 + ... + n/n
n * (1 + 1/3 + 1/6 + ... + 1/n)
<= O(3 * n)
= O(n)
If X and Y are n x n matrices and
X = [ A B, C D]
Y = [ E F, G H]
Prove the product property that XY can be expressed as - answer Subdivide X into a
(1, 1) - (n/2, n/2) elements in the top right, b (1, n/2 + 1) -(n/2, n) elements in the top left,
c (n/2 + 1, 1) - (n, n/2) elements in the bottom left, and d (n/2 + 1, n/2 + 1) -(n, n) in the
bottom right, and do the same for Y with e, f, g, and h respectively. Then combine the
two using the dot product and show each subdivision = its product (i.e. top left = AE +
BG but with elements)
Design and analyze a divide and conquer algorithm for an index search whether there
exists an index i such that ai = i in a sorted list - answer --IndexSearch--
Input: A sorted list of distinct integers A {a1, a2, a3, ..., an}, and integers min and max.
(min = 0 and max = n - 1)
Output: A truth value depending on whether there exists an index i such that ai = i
1: i = floor((max + min) / 2)
2: if i = max and i = min and i != ai:
return False
3: else:
4: if i = ai:
return True
5: else if i < ai:
return IndexSearch(A, min, i - 1)
6: else:
return IndexSearch(A, i + 1, max)
Lemma: If there is no such i then IndexSearch returns false.
Proof by contradiction: Suppose there is no such i and that IndexSearch returns
something other than -1. Only way to return something that is not -1 is if there exists
such an i. Thus, our contradiction.
Lemma: If there exists such an i and max - min = n, then IndexSearch returns true.
, Proof by induction:
Base Case: Suppose that there exists such an i and max - min = 0. Then max = min = i
= floor((max + min) / 2). Line 4 of IndexSearch returns True
Inductive Hypothesis: If there exists an i and max - min <= k, then IndexSearch returns
True
Inductive Step: Suppose that there exists an i and max - min = k + 1
1. i < A[midpoint]
2. i > A[midpoint]
3. i = A[midpoint]
Case 1: There exists such an i in A(min, midpoint - 1) since the list is sorted and
(midpoint - 1) - min <= k, so the inductive hypothesis is met and Line 5 of IndexSearch
returns True
Case 2: Symmetrical to Case 1
Case 3: On Line 6, IndexSearch returns True if i = A[midpoint]
Design and analyze a divide and conquer algorithm that finds the heavy marble out of
3^n marbles using the balancing scale at most n times - answer --MarbleSearch--
Input: A set of marbles M that weigh identically except for one heavier marble and a
balancing scale function BalancingScale() that compares weights
Output: The heavy marble
1. if set = one marble:
return marble
2: Let the set of marbles be divided equally into 3 subsets named first, second and third.
3: if BalancingScale(first) > BalancingScale(second) and BalancingScale(first) >
BalancingScale(third):
MarbleSearch(first)
4: else if BalancingScale(second) > BalancingScale(first) and BalancingScale(second) >
BalancingScale(third):
MarbleSearch(second)
5: else:
MarbleSearch(third)
Design and analyze a divide and conquer algorithm that counts the number of
occurrences of x in a sorted list - answer --IntegerCount--
Input: An integer x, and a sorted list of integers A {a1, a2, ... an}
Output: The number of occurrences of x in the list
1: midpoint = floor((max + min) / 2)
2: if x = A[min] and x = A[max]:
