Homework Assignment #1

Due Friday, Jan. 31, 11:59 PM

1. (10 pts) Consider sorting n numbers stored in array A by first finding the smallest element of A and putting it in the first entry of another array B (or in the first entry of array A, if you prefer). Then find the second smallest element of A and put it in the second entry of B (or array A). Continue in this manner for the n elements of A. Write pseudocode for this algorithm, which is known as selection sort. Give the best-case and worst-case running times of selection sort in Big-O notation.  Write a program in C++ that implements your selection sort algorithm on an array of sample numbers. Include your source code with your answer to this problem.

2. (5 pts) Consider linear search, where the input is a sequence of n numbers in an array A and a value v. The output is the index of the array where v matches A[index], and NULL if v does not appear in A. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Big-O notation? Justify your answers.

3. (5 pts) Using the tree given in the notes or the book as a model for merge sort, illustrate the operation of merge sort on the array A=[3,41,52,26,38,57,9,49].

4. (10 pts) Referring back to the linear searching problem, observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is O(lg n).  Write a program in Java that implements your binary search algorithm with an array of sample numbers. Include your source code with your answer to this problem.

5.  (10 pts) Insertion sort on small arrays in merge sort:

Although merge sort runs in O(nlgn) time, and insertion sort runs in O(n^2) time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

1. Show that the n/k sublists, each of length k, can be sorted by insertion sort in O(nk) worst-case time.
2. Show that the sublists can be merged in O(n lg(n/k)) worst-case time.
3. Given that the modified algorithm runs in O(nk + nlg(n/k)) worst case time, what is the largest asymptotic (O notation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort?
4. How should k be chosen in practice?

6.  (4 pts)  Big-O and Log Review

Is 2^(n+1) = O(2^n)?
Is 2^(2n) = O(2^n)?
Is lg(2/n) = O(lg(n))?
Is 2^(lg n) = O(lg(n))?

7.  (5 pts) Coin Spotting

You have 50 coins that are all supposed to be gold coins of the same weight, but you know that one coin is fake and weighs less than the others. You have a balance scale; you can put any number of coins on each side of the scale at one time, and it will tell you if the two sides weigh the same, or which side is lighter if they do not weigh the same. Outline an algorithm to find the fake coin. How many weighings will you do? Find an algorithm that uses the least number of weighings possible.