Assignment 10

Due Wednesday April 10, 2013 at 7pm.

1. Suppose you are writing an income tax predictor program that uses the following Person class to store information about a person:

   class Person{
     int income;      // yearly income of person in dollars
     boolean student; // true if person is a student
     int age;         // age of person
   }
   

   Your income tax predictor will either suggest that a given person will receive a tax refund or that they owe money.

   Write a single if-else statement for each of the following prediction rules using the logical operators && and || (assume each rule is independent):

   1. You will receive a refund if you are a student and you make less than $25,000.
   2. You owe money if you are older than 25 but younger than 55 and you make more than $100,000.
   3. You will receive a refund if you not a student and you are older then 40 and you make more than $250,000.
   4. You will receive a refund if your age is an even number and your income is an odd number or if you are a student and you income multiplied by your age is less than 100,000.
   5. You will owe money you are older then 200 or if you are younger than 100 or if you make more than $25,000 or if you are student or if you are not a student and you are older then 25 making less than $17,000.

2. For each of the following, estimate how many times the main loop would have to run in the case of (i) linear search when the data is randomly ordered; (ii) binary search when the data is sorted. Assume the worst-case scenario where the target object is not in the array.

   1. 120 elements (approximately the population of 1005B/1405B)
   2. 900,000 elements (approximately the population of Ottawa)
   3. 34 million elements (approximately the population of Canada)
   4. Given that binary search is so much faster than linear search, why would we ever use linear search at all?

3. Suppose you have an array of 1024 random numbers. The bubble, insertion and selection sorts that we saw in class can sort this array with about 1024*1025/2 comparison operations (that is roughly 500,000 operations). Note: a comparison operation is when we compare two numbers in the array to each other.

   The best known algorithms to sort this array, that also compare two numbers in the array at a time to make decisions, takes about 1024*10 comparison operations (roughly 10,000). This is much better.

   Suppose that you also know that the numbers in the array are unique and are all between 1 and 1024. Can you sort the array with less work than the best known comparison based sorting algorithms? Describe a VERY efficient way of sorting this array (in less operations than 10,000). Estimate the worst case cost of your method.

Note: For each question, add the processing folder with your sketch to your ZIP file, not just your sketch (.pde file). Label each folder/sketch as Question4, Question5, etc. Do not put a space between "Question" and the number.

Note: For all of your sketches, the output window should have width and height at least 300 (but do not make them extremely large).

Note: For this and the remaining assignments, it is expected that you WILL use setup() and draw() unless specifically asked not to.

4. Write a sketch that "pixelates" an image. Using the pixelate() function from Assignment 8 (Question 2) as a helper function, load an image, convert it into a pixelated version, and then save the new pixelated image.

   You should work with the entire image (do not resize it to fit in the output window). Use a size value of about 16 for your pixelation.

   Once your image has been pixelated, use the save method of the PImage class to save it. Use a different name to save the pixelated image. For example, if your PImage is called img and your original picture is in file penguin.jpg, after you pixelate your image, you might save it as

   img.save("penguinPixelated.jpg");
   

   Be sure to include your starting image file with your submission. Do not include your pixelated image (as we will use your code to generate it).

5. Write a sketch that allows you to navigate around an image that is larger than the output window.

   In particular, write a sketch with an output window with size 640x440. Load an image from a file that is larger than 600x400 and initially display it centred in your output window. Your output window should have a 20 pixel border on each side (top, bottom, left and right). When the mouse is pressed in one of these border regions, the visible part of the image should scroll in that direction. Only scroll an image in a given direction until you reach the border of the actual image (with the 600x400 display).

   Be sure to include your image in your submission.

6. A superincreasing sequence of numbers is a sequence such that any given number in the sequence is larger than the sum of all the numbers before it.

   For example, {1, 2, 4, 10, 20} is superincreasing because 2 > 1, 4 > 1+2=3, 10> 4+2+1=7, and 20>10+4+2+1=17, and {1, 2, 4, 10, 15} is not, because 15 < 10+4+2+1=17.

   Write a function

   boolen isSuperincreasing( int [] sequence ){...}
   

   that returns true of the numbers in the input array are a superincreasing sequence of numbers and false otherwise.

   Note: Arrays can be initialized then declared using by specifying their contents between curly braces. For example,

   int[] myArray = {1,2,4};
   

   creates an array called myArray with the 3 numbers as given. When initializing an array in this way, we do not need to use the new operator.

   Use this method of initializing arrays to generate arrays to test your function with.

7. Write a sketch that creates an array of 100 random integers. Your sketch should display the first 10 numbers in your array (lined up horizontally across the screen) and the last 10 numbers in your array (also lined up horizontally across the screen). You should indicate with some appropriate output that these are the initial numbers.

   Write a function

   void sort(int[] numbers){...}
   

   that sorts the numbers in the array. (Do not simply call a sorting algorithm that comes with Java. You must implement your own function.)

   Sort the numbers in your array using your sort function. Display the first and last 10 numbers in the array after sorting with some appropriate output to indicate these are the sorted numbers. All 4 lines of numbers (both unsorted lines and both sored lines) should be on the screen.

8. Use the following Person class:

   class Person{
      String name;
      int    age;
   }
   

   You can add a constructor or other methods to this class if you wish.

   Write a sketch that has an array of Persons in it. Write and test the following two functions:

   void sortAge(Person[] people){...}
   // sorts the array by age of the persons (youngest first)
    
   void sortname(Person[] people){...}
   // sorts the array alphabetically by the name of the persons
   // If there is a tie (two people have the same name) then 
   // break the ties by sorting by the age (oldest first)
   

   In Processing (and Java) you can only compare primitive data types with <, <=, etc. For Strings, which are objects, we need to use the compareTo() method of the String class. If s1 and s2 are strings, then

   s1.compareTo(s2)  
   

   will return a negative integer is s1 < s2 (alphabetically), will return 0 if they are the same string, and will return a positive integer if s1 > s2 (alphabetically).

   Use the following skeleton code for this question. Just add your functions and run it.

   Aside: In COMP1006/1406, you will write your own compareTo() methods for your classes so that you can compare two objects in some logical way.