CSC212 Homework 8 2014

--D. Thiebaut (talk) 20:30, 12 November 2014 (EST)

---

This homework assignment is due Nov. 21st, 2014, at 11:55 p.m.

Problem #1

• Write a program called Hw8_1.java based on the Quicksort program of Lab 12, that has the following properties:

• It receives an array A of ints (int[] A), along with two ints defining the low and high indexes it must apply itself.
• It receives an integer N, with N' less than or equal to the size of A.

        public static void Quicksort( int[] A,int low, int high, int N ) {
            ...
        }

• It partially sorts the array A so that the lowest N integers of the array end up sorted in the left-most side of the array, which contains index 0. For example, assume that the modified Quicksort receives A = [10, 3, 5, 1, 2, 9, 0, 3], and N = 3. Quicksort will stop as soon as the lowest 3 integers of A are located in the cells of A with lowest index, i.e. A = [0, 1, 2, 5, 10, 3, 9]. Note that only the lowest 3 integers are sorted, and less than all the other integers of A, which are left in the array A, unsorted.

• The purpose of this modified Quicksort is to have a very fast algorithm for locating the N lowest (or N highest) items of a large collection, without having to spend the time to sort the whole array.

Performance

• Your program has to be robust and avoid O(N²) complexity arrays
• Your program's execution time will be measured and compared to that of the solution program, on different arrays, some random, some sorted in increasing order, and others sorted in decreasing order. Your function will also be tested with values of N ranging from 0 to the length of A.
• The grade will be proportional to the speed of your program.

Submission

• Submit your program to Moodle, in the Homework 8, Problem 1 section.

Problem #2

Page under construction!

Your Assignment

• Write a Java program that reads a collection of tweets stored in a csv file, and outputs the tweet corresponding to the person with the most followers.
• Your program should be called Hw8_2.java.

Additional Information

CSV File

• You can use this file as a practice file for your Java program: tweets.csv
• To make your file accessible to your program, you have two options:

In Eclipse: click on the src folder containing your HW8_2.java file, and add a new File. Call it tweets.csv.
To access the file, use this code as inspiration:

String fileName = "tweets.csv";
URL url = Hw8_2.class.getClassLoader().getResource( fileName );
Scanner s = new Scanner( new File( url.getPath() ) );

On Beowulf2: put the file in the same directory where your program resides, and your code will find the file without problem.