Professor Shai Simonson

CS401   Algorithms

Assignment 1 - 40 points

 

Due date: Tuesday, September 24, to the TA.

 

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 must actually write the program using whatever tool you like.

 

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.

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 for each new pair of numbers scanned.

 

b.   Write a program to implement the tournament style algorithm for the same problem that runs in n + lgn - 1.  You should keep track of the second largest candidates, by using 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.  You should implement the tournament in the most efficient way you can.

 

c.    Compare which method is faster in practice by creating a file with random numbers, and timing both algorithms.  You should report your results for lists of length 10, 100, 1000, 10000, and 100000. 

 

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. Your program should read in the array of strings, sort them using MAXSORT, and print out the results.
  2. 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. In insertion sort, we scan back through the sorted portion of the list to determine where the new value should be inserted.  We shift all the scanned values downward, and insert the new value in the open location.  Explain how to use binary search to find the appropriate insertion spot rather than a linear scan.  Explain why this does NOT help the overall time complexity of the algorithm.

 

4.  A Better Quicksort? (1 point)

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

 

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 new 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. Which one of the recursive methods corresponds to which iterative method and why? 
  2. Construct and solve two recurrence equations for each of the recursive methods and get the Big-O time complexity for each? 
  3. 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. 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. What is the time complexity of this method? Explain.

 

  1. Challenging.  Write an algorithm to do the same thing in O(n + k log k).  Hint: Try to avoid rebuilding the original heap of size n each time.  Instead use an extra heap that will have at most k elements in it, and rebuild that.  For each element you store in the second heap, make sure to also store the index of its location in the first heap, so that you can find its children.

 

  1. Write code for the two methods and test them on arrays with various values of n and k.  How do your experiments compare with the theoretical results when k = n/2?  when k =  lg n?

 

7.    An Application of Radix Sort (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.   Hint:  Use base n.

 

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, representing the order of the integers in the given array.  For example, given the array: 35, 67, 12, 7, 42, you should return the String:  35214.  Explain how your algorithm 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), write an algorithm 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(n2) time.  Hint:  Reverse.