HW1 ANSWER KEY

1.
a. prog1 = binary-search.c (logarithmic)
b. prog2 = 2-to-n.c        (exponential)
c. prog3 = seq-search.c    (linear)
d. prog4 = fac_time.c      (growing till n=16)
e. prog5 = insert-sort.c   (polynomial-O(n^2))
f. prog6 = triple.c        (polynomial-O(n^3))
g. prog7 = merge-sort.c    (O(nlogn))

2. Exercises 1-3 through 1-7

1-3
a. Yes, O(n^2) is the worst case. For some inputs it can take less 
   than the worst case.
b. Yes,Suppose i have an algorithm that is O(n) on all inputs, 
   but all i have been able to prove that it takes O(n^2) in the worst
   case.(If f(n)=O(g(n)) and h(n) grows faster than g(n) than also
   f(n)=O(h(n)) ).
c. Yes,for some input it may take less than the worst case situation.
d. No,For an input that correspond to the worst case time
   theta(n^2) implies omega(n^2) which contradicts O(n).
e. Yes, for even n 100n^2=O(n^2) when c=100.
	for odd n take c1=19,c2=20: 19n^2 <= 20n^2-nlogn <= 20n^2.
	since logn<n

1-4
a. No, There is no constant c such that 3^n <=c*2^n.
b. Yes, log3^n <= c*log2^n is equivalent to nlog3 <= nclog2
   so take c >= log3/log2.
c. Yes, take c=1 so 3^n >= 2^n for all n>=0.
d. yes, since 2^n <= 3^n ==> log2^n <= log3^n. take c=1.

1-5
Counterexample:
1. f(n)=n^3 ,F(n)=n^3 ( n^3=O(n^3))
2. g(n)=n   ,G(n)=n^2 ( n=O(n^2) )

f(n)/g(n)=n^2, F(n)/G(n)=n
and n^2 != O(n).

1-6
No.Counterexample:
f(n)=2n
g(n)=n  (2n=O(n))

but 2^(2n) != O(2^n)

1-7
A counter example is given with an oscillating function.

An example of such a case is f(n)=n and g(n)=n^2*(((-1)^n)+1)
when n is odd  f(n) is n and g(n) is 0;
when n is even f(n) is n and g(n) is 2n^2;

Quite obviously f(n)!=O(g(n)) because there is no n0 > 0 and C > 0 such that 
for all n > n0 Cg(n) > f(n)
Proof
suppose Cg(n) > f(n) for some n > n0
For an odd n Cg(n) = 0 while f(n) = n
Hence assumption is wrong and statement is proved.

Also g(n) != O(f(n)) because there is no n0 > 0 and C > 0 such that  
for all n > n0 Cf(n) > g(n)
Proof
suppose Cf(n) > g(n) for some n > n0
For an even n Cf(n) = Cn while g(n) = n^2 + 1
For large enough n0 we can find n^2 + 1 > Cn for any value of C
Hence assumption is wrong and statement is proved.

3.
a) f(n) = theta(g(n))
b) f(n) = omega(g(n)) only
c) f(n) = omega(g(n)) only 
d) f(n) = omega(g(n)) only
e) f(n) = omega(g(n)) only
f) f(n) = theta(g(n))
g) f(n) = omega(g(n)) only
h) f(n) = O(g(n)) only

4.
   By definition f(n)=O(g(n) means there is some C1 such that C1*g(n) > f(n)
   for all n > n0.
   and gn=O(h(n) means there is some C2 such that C2*h(n) > g(n) for all n > n1.

   From the above fact we can see that 
   C1*C2*h(n) >C1*g(n) for all n > n1

   For n > max(n0,n1)
   we can say that 
   C1*C2*h(n) > f(n)

   This satisfies the definition of f(n)=O(h(n)) since there is a C=C1*C2
   such that for all n > n2=(max(n0,n1)) C*h(n) > f(n)
   

5.
(other answers are of course possible)

a. The population of US is approximately 270 million and there are 
approximately 5000 people per city or town.
Therefore the number of cities and towns in the US is 270*10^6/5000=
54,000.

b. We assume that the width of the river is 5 miles and the depth is 0.5 miles.
also the the river flow is 1 mile per hour so the water flows out at rate of
5*0.5*1*24=60 cubic miles per day.

6.
2-7
We have to add to each node in the datastructure 2 pointers, the first 
one will point to the node's predecessor and the second to its successor.
The operations to be modified are the Delete and Insert operations.

2-9
We have to add two variables Max and Min that will store the minimum and 
the maximum.
Modification of Insert(a): add the following lines:
if a>max then max=a.
if a<min then min=a.
Modification of Delete(a): add the following lines before delete:
if a==max then max=a->predecessor
else if a==min then min=a->successor

The Insert and Delete operation will still take O(logn) but max and min
will take O(1).


7. First we figure out the number of elements in the stack.
   To do this we pop the elements from the stack one by one until the 
   stack is empty. Along with this we use a counter to count the number of 
   elements. After this we push all elements into the stack.

a) Assume that Compare(s1,s2) returns true if top(s2) > top(s1).
   Also assume in the pseudocode that elements at the same level of indentation 
   are at the same level of nesting.

   This is a selection sort. At the end of each outer iteration the greatest 
   element is at the bottom of stack s1. The next iteration does not compare
   the previously largest selected elements. They remain at the bottom of 
   stack s1. At the end the smallest element remains at the top of the 
   stack s1.
   
   Let this number be n.
   Sort(s1,s2,s3)
      for i = 1 to n do
         for j = 1 to n-i+1 do
            Push-Pop(s1,s2);
            if(Compare(s1,s2)=TRUE)
               Swap(s1,s2,s3);
         while(s2 is not empty) do
            Push-Pop(s2,s1);

   Swap(s1,s2,s3)
      Push-Pop(s2,s3);
      Push-Pop(s1,s2);
      Push-Pop(s3,s2);

   This is an insertion sort. s3 contains a sorted list at each iteration 
   and the element in s2 is inserted into the list s3 at the right position 
   at each iteration. Thus the list grows at each iteration.

   Let this number be n.
   Sort(s1,s2,s3)
      for i = 1 to n do
         Push-Pop(s1,s2);
         k=0;
         for j = 1 to i do
            if(s3 is empty)
               Push-Pop(s2,s3);
            else 
               if(Compare(s2,s3)=TRUE)
                  Push-Pop(s3,s1);
                  k=k+1;
               else
                  break;
         Push-Pop(s2,s3);
         for j= 1 to k do
            Push-Pop(s1,s3);
      while(s3 is not empty) do
         Push-Pop(s3,s1);

b) The stack with elements 9,8,7,6,5 from top to bottom cannot be sorted using 
   two stacks and no registers. This is because the only data movement 
   operation is Push-Pop between the two stacks. This operation is incapable of 
   changing the position of any elements with respect to each other. Even 
   though the positions get reversed while popping from one stack to the other, 
   the reverse pop operation restores the order of elements in the initial 
   stack. Thus at least a third stack or register is required as a temporary 
   swap location to sort a stack of elements.

c) We can use the same insertion algorithm use in a). We also allow the Compare 
   and Push-Pop operations to be allowed for our temporary register a.

   Sort(s1,a,s3)
      for i = 1 to n do
         Push-Pop(s1,a);
         k=0;
         for j = 1 to i do
            if(s3 is empty)
               Push-Pop(a,s3);
            else 
               if(Compare(a,s3)=TRUE)
                  Push-Pop(s3,s1);
                  k=k+1;
               else
                  break;
         Push-Pop(a,s3);
         for j= 1 to k do
            Push-Pop(s1,s3);
      while(s3 is not empty) do
         Push-Pop(s3,s1);

   This is possible with a selection sort as well.
   Sort(s1,s2,a)
      for i = 1 to n do
         for j = 1 to n-i+1 do
            Push-Pop(s1,s2);
            if(Compare(s1,s2)=TRUE)
               Swap(s1,s2,a);
         while(s2 is not empty) do
            Push-Pop(s2,s1);

   Swap(s1,s2,a)
      Push-Pop(s2,a);
      Push-Pop(s1,s2);
      Push-Pop(a,s2);

8. To determine if two sets of size m and n are disjoint do the following.
   a) First sort the set of size m (where m < n). This is an O(mlog(m)) step.
   b) Using binary search search the sorted list with m elements for each of 
      the n elements.
      Since binary search is an O(log(m)) algorithm this step has complexity
      O(nlog(m)).
   c) If step b) returns no elements then the two sets are disjoint. 

   The Complexity of the above algorithm is 
   O(mlog(m) + nlog(m))
   In the case where m<<n
   nlog(m) > mlog(m)
   therefore
      O(mlog(m) + nlog(m)) = O(nlog(m)).

   This is the most efficient algorithm since if we had sorted the bigger list
   of size n. It would have taken us nlog(n) steps to sort and mlog(n) to search
   giving us a final complexity of nlog(n) which is greater than nlog(m) for 
   all m<n.
   
9.
2-15 (Extra-Credits)

Variables:
NumOfElements - keeps track of how many elements are in array B
B - array of the numbers.
A - array in which the element A[i] represent the location of integer
    i in array B. (assuming 1<=i<=n)

Initialization : NumOfElements=0

Search(x): 
The location of number x in the array B is A[x]. so retrieve B[A[x]].

Insert(x):
checking that integer x isn't in the array. (using search(x)).
Incrementing NumOfElements.
Assigning B[NumOfElements] the value of x.
Assigning A[x] the value of NumOfElements which is the location of x
in the array B.

Delete(x):
Searching for the element,coping it to the location of the last element 
in B while coping this element to its location.(swap operation)
Updating A correspondingly.
Decrementing NumOfElements.