Assignment 1 - 40 points

Due date:  Monday, February 13.

When you are asked to write, design or describe an algorithm, you may use a computer language, or pseudo-code, or a careful English description.  When you are asked to write a program or code, you can use any compiler you like and you will need to demonstrate your program for me on various data.  Note that the programs are worth much more than the written stuff.

0.  Experiment with Constant Factors (6 points)

a.   Write a program to implement the 3n/2 recursive algorithm for calculating the largest and second largest elements of a list.  This is the algorithm that recursively processes all but two of n elements finding the two largest of n-2 elements.  Then, using three comparisons, it re-computes the two largest of all n elements.  This algorithm has a recurrence equation of
T(n) = T(n-2) + 3 which has a solution of 3n/2 comparisons.

You can implement this recursive algorithm recursively or iteratively as long as you stick to the idea of the algorithm.  Iteratively, you would process the array two numbers at a time, keeping track of the two largest numbers you have seen so far.  You update these two and using three if-statements (don't use more than 3) for each new pair of numbers scanned.  Note:, if you use recursion, you may have to adjust the stack size allowed by your compiler unless you use tail recursion and your compiler recognizes tail recursion.

b.   Write a program to implement the tournament style algorithm for the same problem that runs in n + lgn - 2 comparisons.  One way to track the second largest candidates is to use a linked list for each number.  When one number is compared to another, append the value of the smaller number to the linked list of the larger number.  Then at the end of the tournament, the candidates for the second largest number are all the numbers in the linked list of the winner.  There are other ways to keep track of the second largest too.  You should implement the tournament in the most efficient way you can.  You may assume for convenience that the number of values is a power of two.

c.   Compare which method above, (a) or (b),  is faster in practice by creating a file with random numbers, and timing both algorithms.  You should report your results for lists of length 8, 128, 1024, 8192, and 65536. Briefly discuss the results and explain why you think they turned out the way they did.

     
Note, that one would expect (b) to outperform (a) as the size of the input increases, but that does not take into account all the extra time spent creating and updating the linked lists.  This is time that is not included in our count of the comparisons.  The point is that you cannot always rely on simple theory of Big-O. Constant factors can be important considerations in practical computation.

1.  Practice with Sorting Algorithms (5 points)

Use the following array (12, 10, 3, 37, 57, 2, 23, 9) for the practice problems below and show the values of the array after the indicated operations:

 

1. Three iterations of the outer loop in Bubble Sort.
2. Four iterations of the outer loop in Insertion Sort.
3. The first call to Partition in Quicksort.
4. One iteration of the outer loop in Radix sort.
5. All the recursive calls of Mergesort.(i.e., just before the last Merge).
   

2.  Another Slow Sort (4 points)

Write a program MAXSORT to sort an array A of size strings.  MAXSORT works by finding the index of the maximum element in the array from A[0] through A[size-1] and swapping it with the current last location.  The current last location starts at size – 1, and size is decremented in each iteration until it equals 1.

 

1. (3 points) Your program should read in the array of strings, sort them alphabetically using MAXSORT, and print out the results.
   
2. (1 point) Write a recurrence equation for the worst case time complexity of your algorithm and solve it.

3.  Binary Search (2 points)

1. Binary search takes O(log n) time, where n is the size of the array.  Write an algorithm that takes O(log n) time to search for a value x in a sorted array of n positive integers, where you do not know the value of n in advance.  You may assume that the array has 0’s stored after the last positive number.  Prove that your algorithm has the correct time complexity.
2. A sorted array has been rotated so that the smallest element is no longer in index 0.  For example:  8, 12, 17, 23, 4, 6, 7.  Explain how to use binary search to find the index of the smallest integer in a rotated sorted array. Your algorithm should run in O(log n).
   

4.  A Better Quicksort? (1 point)

Quicksort has worst-case time complexity O(n²) and average-case O(n log n).  Explain how to redesign the algorithm to guarantee a worst case O(n log n).

5.  Building Heaps (8 points)

There are two ways to iteratively build a heap.  One way to build a heap is to start at the end of the array (the leaves), moving right to left through the array, and push each value down, moving left to right.  Another way is to start at the root, moving left to right through the tree, and push each value upward, moving right to left. 

 

There are two recursive ways to build a heap.  One recursively builds a heap out of the first n-1 elements and then pushes the nth element upwards.  The other recursively builds two heaps for each of the subtrees of the root, and then pushes the root downwards.

 

1. (1 point) Which one of the recursive methods corresponds to which iterative method and why? 
2. (2 points) Construct and solve two recurrence equations for each of the recursive methods and get the Big-O  time complexity for each? 
3. (4 points) Write code for each of the iterative methods, and test which one is actually faster using an array of size 100,000 where a[i]=i..
4. (1 point) For each of the methods show what heap is built out of an array with values 1-15 in ascending order.

6.  Using Heaps to Find the Kth Largest (6 points)

It is straightforward to use a heap in order to find the kth largest value by just deleting the top of the heap k times. 

 

1. (1 point) What is the time complexity of this method? Explain.

 

2. (1 point) Write an algorithm to do the same thing in O(n + k log k).  The idea is to consider at most k possible elements for the next largest.  Hints:  Use an extra heap that will have at most k elements in it, and rebuild the extra heap, leaving the original heap intact.  Initialize the extra heap to the top element of the first heap.  When you delete an element x from the second heap and fix the heap, you then add x's children in the first heap to the second heap.  To find x's children in the first heap, you must know where x is located in the first heap. To do this efficiently, you should store x's index in the first heap in the second heap.
   

 

3. (4 points) Write code for the two methods and test them on arrays with random numbers for n =1024 and 65536.  For each n, test your code for k = n/2 (512, and 32768), and k = lgn (10 and 16).  Briefly explain why you think the results turned out the way they did.  The theoretically better algorithm in comparisons will likely perform worse in practice. Why do you think this is the case?
   

 

7.    An Application of Counting/Bucket/Radix Style Sorts (2 points)

You are given two integer arrays A and B, each of length n, the values of which are all between 1 and n inclusive.  Write an algorithm that sorts C(i)=A(i)*B(i) in O(n) time.   Note: Using only counting sort gives O(n²), and using only radix sort gives O(n log n).  Hint:  Convert each product into a two-digit base n number.

8.   A Practical Ordering (3 points)

Write code to accept an array of n integers and return a String containing a permutation of the integers 1 through n, that represents the rank of each integer in the array if the array were sorted in ascending order.  For example, given the array: 35, 67, 12, 7, 42, you should return the String:  35214, because 35 is the third, 67 is the fifth, 12 is the second, 7 is the first, and 43 the fourth, in ascending order. 

Explain how your code works and prove it works in O(n log n).

9.  Algorithm Design Challenge (3 points)

Given three arrays of n real numbers (the numbers can be positive or negative), describe an algorithm and write code  to determine if there are three numbers, one from each array whose sum is 0.  Design the most efficient algorithm you can think of to solve this problem.  It can be done in O(n²) time. More points for better complexity.