CS 146: Homework due 3/1 and 3/6

Due 3/1:

1. Suppose that you have a max-heap H, with the maximum element at the top. You want to write an algorithm which, given k and val answers "true" if the kth largest element in H is larger than val, and false otherwise. The algorithm does not need to find the kth largest element of H. Give algorithms and analyze their efficiency for each of the two following cases:
   • The heap is a black box to you, and you only have access to it through 3 procedures: get-max, insert, and delete.
   • You have full access to the heap, in explicit tree format. Here, consider that you can look at each subchild of the heap root recursively, and each is the root of a smaller heap. Hint: remember our class discussion on search within heaps.
2. Programming assignment: For the first programming assignment, consider the 3n+1 problem. (It is taken from the the Programming Challenges website.) You need to write a java program for this problem, and submit it to me electronically. Note: both the input and output format are very precisely specified for the problem. If you assume a different input format, or give a different output, your solution will be rejected. Do not add extra spaces, do not make any assumptions not in the problem specification. I will be automating the testing of your programs, and the automated system will not be very forgiving. If I cannot get your program to run with little effort, it is wrong.

   You need to submit your solutions to me. You should email them to me with the following subject line: "CS146Spring06: Program 1 TaylorDS", without the quotes, and where TaylorDS is replaced by Your last name and initials. The email should be empty, other than an attached file of source code, in a single text file named "prog1.java" (no quotes). I should be able to compile it, and run it on a test case of my own with no fuss. Please follow these directions carefully, as the process will be (hopefully) automated. I will allow you to use any fairly recent version of Java.

   This assignment should not be a complex programming assignment, it is to test basic competancy in Java. Try to make your program run quickly, but no efficiency analysis is needed. Remember, you do need to submit working programs during the course to qualify for different grades. Refer back to the greensheet for more details.

   A style guide for programming is found here, and it is used by the department in general. Look at it, use it, follow it. I will not enforce it to the letter for the first program, but will be less lenient as the semester progresses.

   Due 3/6:

   Sorting: Consider each of the following scenarios, and try to determine which sorting algorithms are appropriate in each case:
   1. You need to sort n numbers, and you know nothing about the numbers to be given to you. The program should be quick, but a constant quicker isn't critical.
   2. Suppose that you needed to sort a set of 5000 numbers for a meeting at work. You have the numbers on your computer, but due to crashed systems, no pre-written sorting software is available, so you need to write a soring algorithm yourself. Time is critical -- your time, because you need the numbers for a meeting which starts in 10 minutes.
   3. You need to sort a set of numbers, but the numbers are almost in sorted order to start. For example, all but O(1) of the numbers (and you don't know which ones) are within O(1) of their final positions in the array you are given to sort.
   4. You need to sort a set of n integers, each with value 0 to n^3-1.
   5. You are given n floats, each between 1 and 2^n. For any 1 <= i <= n, the probability that a given number falls between 2^i-1 and 2^i is 1/n.
   6. You need to write a program which will sort just a few numbers, say 6. The program will be called many many times, and its runtime is critical, it must run as quickly as possible. You have been assigned full time for 1 month to work on the problem, so you should be able to convince your boss that you have given the best answer. Your boss wants a tried-and-true sorting method, one of the above, he doesn't like ``new stuff'', so you don't need to come up with any specialized sorting algorithm. What do you do? (For this problem, describe what you would do at work during that month.)