15110 Fall 2012 [Kaynar/Touretzky]

Programming Assignment 4 - due Tuesday, September 25

Overview

In this assignment, for each of the problems described below, you will create a Ruby source file containing Ruby functions implementing your solution. If you find it useful, you may define additional helper functions that your primary function calls to solve a sub-problem. Definitions for these helper functions should be included in the same Ruby source file as the primary function. You should store your source files in a folder named pa4.

Note: You are responsible for protecting your solutions to these problems from being seen by other students, either physically (e.g., by looking over your shoulder) or electronically.

The Algorithms

[2 points] Counting.

In the file num_greater.rb, define a Ruby function num_greater(list, item) that takes an integer array list and an integer item as parameters. It should return the number of elements in list that are strictly greater than item.
Example:
```
>> load "num_greater.rb"
=> true
>> num_greater([3, 8, 12, 30, 7, 32, 10], 8)
=> 4
```
[2 points] Index of Perfect Square.
In sq_index.rb, define a Ruby function sq_index(list) that returns the index of the first number in list that is a perfect square. (A number is a perfect square if its square root is a whole number. The value of x is a whole number if x%1 == 0.) If there are multiple perfect squares in list, then sq_index should return the index of the first one.

Example:
```
>> load "sq_index.rb"
=> true
>> sq_index([3, 25, 30, 16, 5])
=> 1
```
[2 points] Second Largest Element.
In second_largest.rb, define a Ruby function second_largest(list) that takes an array of integers and returns the second largest integer in the array list . Use the following algorithm:
1. Set first to the maximum of first element of list and second element of list.
2. Set second to the minimum of first element of list and second element of list.
3. Set index to 2.
4. While index is less than the length of list, do the following:
  1. If element at index is greater than first then set second to first and first to element at index.
  2. Else if element at index is between first and second then set second to element at index.
  3. Set index to index + 1.
5. Return second.
In Ruby, you can use the max and min functions to find, respectively, the maximum and the minimum of two integers.
Example:
```
>> max(3, -2)
=> 3
>> min(3, -2)
=> -2
>> load "second_largest.rb"
=> true
>> second_largest([3, -2, 10, -1, 5])
=> 5
>> second_largest([-2, 1, 1, -3, 5])
=> 1
```
Selection Sort

In addition to Insertion Sort, there are many other algorithms for sorting the elements of an array. One of these is Selection Sort. This algorithm works by moving an index left to right through the array and at each step, scanning everything to the right of the index to select the most extreme value, which is then swapped with the value currently at the index.
1. [2 point] In the file dsort.rb, create a helper function called max_index_after(list,start_index), which returns the index of the maximum element in list that is located at or after the index start_index. If there are more than one such element the function returns the index of the first one.
  
  Example:
```
>> load "dsort.rb"
=> true
>> max_index_after(["b", "d", "c"], 0)
=> 1
>> max_index_after(["b", "d", "c"], 1)
=> 1
>> max_index_after(["b", "d", "c"], 2)
=> 2
```
2. [2 points] In dsort.rb, define a Ruby function dsort!(list) that modifies list by rearranging its elements so they are sorted in "descending order" (from largest to smallest). (The "!" in the name of a function is a Ruby convention indicating that the function modifies its parameters.)
  
  This function should implement the selection sort algorithm using the following steps:
  1. For each integer i from 0 through two less than the length of list, do the following:
    1. Set max_index equal to the index of the maximum element in list that is located at or after index i. (HINT: Call the function you wrote for part a.)
    2. Set tmp equal to the element at index i in list.
    3. Set the element at index i in list to the element at index max_index in list.
    4. Set the element at index max_index in list to tmp.
  2. Return list.
  Example:
```
 
>> load "dsort.rb"
=> true
>> a1 = [3, -2, 1, 0, -4, -5, 7]
=> [3, -2, 1, 0, -4, -5, 7]
>> dsort!(a1)
=> [7, 3, 1, 0, -2, -4, -5]
>> a1
=> [7, 3, 1, 0, -2, -4, -5]
>> a2 = [4, 5, -10, 9, 6, 9]
=> [4, 5, -10, 9, 6, 9]
>> dsort!(a2)
=> [9, 9, 6, 5, 4, -10]
>> a2
=> [9, 9, 6, 5, 4, -10]
```

Submission

You should now have a pa4 directory. containing:

num_greater.rb
sq_index.rb
second_largest.rb
dsort.rb (with max_index_after and dsort!)

Zip up your directory and upload it using the handin system. (The handin system will accept submissions until the deadline Tuesday night.)