Week 6-7: Algorithms 2

Question 1

recursive algorithms

Answer 1

• algorithm is called recursive if it solves a problem by reducing it to
  an instance of the same problem with smaller input

Question 2

complexity of recursive algorithms

Answer 2

• complexity of recursive algorithms is derived by formulating and solving
  recurrences
• start at first occurrence and work until it ends

Question 3

recursive algorithm for fibonacci numbers

Answer 3

procedure fib1(n: nonnegative integer);
if n = 0 or n = 1 return n
return fib1(n-1) + fib1(n-2)

Question 4

the euclidean algorithm

Answer 4

• largest divisor that divides both m and n
  is called the greatest common divisor of m and n
• denoted as gcd(m, n)

Question 5

recursive binary search

Answer 5

• Array a[1…n] contains n elements in non-decreasing order; search for element x
  using the recursive version on binary search
  procedure binary_search(x, low, high, a)
  if high < low
  return -1
  set m := (low+high)/2
  if x = a[m]
  return m
  if x < a[m]
  return binary_search(x, low, m-1, a)
  return binary_search(x, m+1, high, a)

Question 6

complexity of recursive binary search

Answer 6

-recurrence is 𝑇(𝑛) = 𝑇(𝑛/2) + 𝑎 and 𝑇(1) = 𝑏.
- The solution 𝑇 𝑛 ∈ 𝑂(𝑙𝑜𝑔 𝑛) by unwinding because there are log 𝑛 recursive calls

Question 7

merge sort

Answer 7

• takes an array and sorts elements a[I] through a[u-1] denoted by a[I: u]
• copies the data to a work array b, recursively sorts the two halves of b, and merges the results back into a

Question 8

merge sort algorithm

Answer 8

merge(a, l, m, u, b)
set i = l and j = m
for k = l to u
if i < m and (j >= u or a[I] <= a{[j])
b[k] <– a[I] and i <- i + 1
else
b[k] <– a[j] and j <– j + 1

Question 9

complexity of merge sort

Answer 9

• time complexity recurrence is T(n) = 2T(n/2) + O(n) and T(1) = 1 with n = u - l
• for n > 0, there are two recursive calls plus O(n) for copying and merging
• solution is O(n log n) by inductio
• space complexity is O(n logn) but can be reduced to O(n) by using tow arrays instead of a new b each time

Question 10

towers of Hanoi

Answer 10

• Given are 3 rods and n disks of different sizes, One peg contains the n disks stacked by
  decreasing size.
• Move the n disks to
  another peg
• Only one disk may be moved at a
  time.
• No disk may be placed on top of a
  disk that is smaller than it.
• One move: take the upper disk from one of the stacks and place it on top of another stack or on an
  empty peg

Question 11

towers of hanoi recursive solution

Answer 11

Let 𝐻𝑛= number of moves needed to solve problem with
𝑛 disks.
➢ In 𝐻𝑛−1 steps move top 𝑛 − 1 disks.
➢ Move the largest disk from peg 1 to peg 2.
➢ In 𝐻𝑛−1steps move 𝑛 − 1 disks from peg 3 to peg 2
procedure hanoi (i, j, k, n)
1. hanoi(i, k, j, n - 1)
2. move(i, j) // move bottom peg from i to j
3. hanoi(k, j, i, n - 1)