Humboldt State University
Department of Computer Science
CS 312: Algorithms
Assignment 2
Due on Thursday, September 23
I have included page numbers, since the problem numeration in the book is
confusing (problems like 2.3-4 are number by subsections in the book,
while 2-1 is an end-of-chapter exercise). Page numbers are by the Third
Edition only. Please make sure you do the correct problems!
This assignment is a substantial amount of work, one of the longest ones
this semester. Several of these problems require creative thinking. Get
together with fellow students to work on it, and don’t put this off until the
night before it is due!
1. Let f (n) and g(n) be nonnegative functions. Using the basic
definition of O() notation, prove that max (f (n), g(n))=O(f ( n ) + g ( n ) ).
Note: you need an n0 and a c.
2. Do problem 2-1 on page 39-40. This problem is in parts, they’re
walking you through the mathematical steps to show the main
result. Yes, this is a common way to implement sorting!
3. We can express insertion sort as a recursive procedure as follows.
In order to sort A[1 .. n], we recursively sort A[1 .. n – 1] and
then insert A[n] into the sorted array A[1 .. n – 1]. Write a
recurrence for the running time of this recursive version of
insertion sort.
4. Do exercise 3.1-6 on page 53.
5. In lieu of doing problem 3-3 part a, I am posting the solution for
that problem from pages 61-62 of your text to Canvas. Use the
solutions posted for that problem to help you rank the following
functions from smallest to largest by order of growth. At least
one needed item is on your formula sheet. In doing this problem,
partition your list into equivalence classes such that f ( n ) and g ( n )
are in the same equivalence class if and only if f ( n )=Θ ( g ( n ) ). So for
example, you might write n !=2n+2 =Θ ( ln n ) if those two functions
were in that equivalence class.
lg n2 lgn log 2 ( n ∙ 2n ) 2 ( n! )
log 4 ( lg n)
2
3 2 n
n +8 n 16 log 2 n
n +1
ln n ! 2 n ln n
lg n !
2 ¿
6. Do problem 3-4 parts a-g on page 62. “Prove or disprove” means
exactly that, you have to figure out which is the correct thing to
do. For the proofs, you’ll use the definition of O( ) or Θ( ). HINTS:
Most are false. Remember that exponentials are more likely to
behave badly. Try simple, obvious functions until you see what is
going on. Spend part of your time trying to prove, and part trying
to disprove until you get there.
