Clarifications/patches for HW 7
-------------------------------

Patch for Problem 1:

If n is an integer and you multiply it by 7/10, you probably won't get
an integer.  So the equations won't quite do the right thing as
stated.  Exactly modelling the algorithm's running time would require
adding some calls to floor or ceiling.  However, dealing with floor
and ceiling is not much fun, and not what we intended you to learn in
this problem.

So, instead, let's assume that the function T is defined for all
positive real numbers and change the base case to read

   T(k) = 1, for every k <= 1.

Don't be worried by the fact that the input values are not integers.
You can still do the unrolling in (a) just like you'd do for integer
inputs, but most of the floor/ceiling complexity will disappear.

Adult computer scientists often handle such problems by making a
simplification of this sort, using it to figure out the basic
structure of the solution, and then patching in the floors/ceilings
only when/if they need to write up the solution formally.  Such
details only rarely affect the big-O analysis, which is our end goal.

-------------------------

Hints for Problem 1: 

Remember that the base of a logarithm can be any real >= 1.  It
doesn't have to be a "nice" number like 2 or 10.  In fact, the
irrational number e is very popular (outside computer science) as a
logarithm base.

Also remember that changing the base of a logarithm just multiplies
the result by a constant.  It doesn't really change the basic
structure of the equations.  So, if log_b is the base b log function,
then

    log_b(x)
   a           =  k * x

where k is some constant.  The word "constant" means that k may depend
on a and/or b, but not on x.  I'll leave you to figure out what k is,
as a function of a and/or b.

For parts (a) and (b), you should try to pin down details like the
value of k as well as you can.  But notice that constant multipliers
can be ignored when you get to parts (c) and (d).   

If your equations don't simplify into something nice by the time you
get to part (c), something is wrong.   Check your math, read the
above hints about logs again, and/or come to office hours.

----------------------------
Patch for Problem 3:

The code as written doesn't do anything useful. 
A version of the code that does something useful is this:

procedure select( a1,..., an, k)
for i := 1 to k
begin
    min := i
    for j := i + 1 to n
        if aj < amin then
        begin
           min := j
        end
    swap(ai, amin)
end
selected := ak

The only change is moving swap out from the inner loop. You can answer part a by analyzing this code or the old code. STATE WHICH VERSION YOU ANALYZE as the answer for a changes depending on which you use. The answer for part b will not change.

Hints for Problem 3:  

You should assume that 1 <= k <= n.   

Swap interchanges two values in the list.   So, if the
list a_1,..,a_n is
   7 1 17 6 4
and you call swap(a_2,a_4) then the list looks like
   7 6 17 1 4
That is, a_2 is 1 before the swap, but after the swap, a_2 is 6.