CSCI 201: Intro to Programming (Java)

Assignment 8.    Due: Wed, Dec 31

Please put your work in directory cs201 on your Linux account before 11:59pm of the day above.

This is an extra credit assignment. Successful completion of any of these projects will increase your total score in this class on 3 points. "Successful completion" means that that you program has to compile and produce correct results. No partial credits will be issued. You have to do it strictly individually as an exam task, no group work or discussion is allowed.

No late submission for this assignment

1. Problem 16.7 on page 815 in the book (Bucket Sort algorithm).
   You can assume that no number in the array has more than 6 decimal places (use the range argument in randomIntArray() method of class ArrayUtil to establish this).
   Embed your implementation into the profiling environment as we did for other sorting methods and compare its efficiency with the BubbleSort method developed in class. Put the results of your analysis as a comment at the top of your class file.

   Name the source file Hw8_1.java
   Solution

2. Exercise 8.18 on page 414 (Huge Integer Class). Assume dealing with non-negative (unsigned) integers only.

   You can store the integers as ASCII strings with up to 40 digits and use the "school algorithms" for operating with them digit by digit. Think on the folloiwng example showing how to use the school methods to add and subtract two numbers:

     925     925
   + 718   - 718
   -----   -----
    1643     207
   

   Name the source file Hw8_2.java
   Solution

3. Design a Java application that accepts a positive integer n > 1 as a command line parameter and outputs all strictly increasing integer sequences starting with 1 and ending with n.

   For example, for n=5 the following sequences should be output (not necessarily in the shown order):

   1 5
   1 2 5
   1 3 5
   1 2 3 5
   1 4 5
   1 2 4 5
   1 3 4 5
   1 2 3 4 5
   

   You can generate those sequences recursively according to the last-but-one entry as in the above table. The first sequence is a particular one and can be served as a termination condition for the recursion. The second sequence has 2 as the last-but-one entry, the next two sequences have 3 as the last-but-one entry and the remaining ones have 4 as that entry.

   Name the source file Hw8_3.java
   Solution

4. Exercise 7.1(a) on page 328. Modify the applet for drawing the spiral from the second midterm to draw the "rectilinear" spiral as it is shown in Fig. 7.24 on the same page. Your applet should have the same GUI as the one above and accept the winding number for the user.

   Name the source file Hw8_4.java. Place the HTML file Hw9_4.html in your public_html folder.