CS 41 -- Homework 4

Due: Tuesday, Oct. 2

Reading

  • Read handout from class. Extra copies will be in a folder at the CS office
  • Read ch. 5 as needed for your comfort
  • Read ch. 6.1-4,6
  • Read Pg. 688-700 on parallel algorithms

    Problems

  • Ex. 6.2-3, pg. 109
  • Ex. 6.3-2, pg. 114
  • Problem 6-2, pg. 133
  • Ex. 8.3-1, pg. 163
  • Ex. 8.3-4, pg. 163

    Additional Exercise:

    The expected run-time of quicksort can be given as:

  • Best Case = B(n) = O(n)
  • Average Case = A(n) = O(n lgn)
  • Worst Case = W(n) = O(n^2)

    A randomized version of quicksort changes this (with high probability) such that:

  • B(n) = A(n) = W(n) = O(n lgn)

    This is known as creating an "Ultimate Homogenization Condition". Algorithms that have ultimate homogenization are sometimes known as Sherwood Algorithms.

    Let's look at a linear search of a list, L[1:n], where all elements are distinct and the ordering is unknown.

  • What are B(n), A(n) and W(n)?
  • A simple random algorithm has us flip a coin to decide which direction to search L ( heads we start from 1 and go to n, tails we start at n and go to 1). Show that this is a Sherwood Algorithm and give the expected run time.