Spring 2016, The College of Saint Rose

Lecture 25: Searching and Sorting
Date: Thursday, April 28, 2016

Agenda

• Announcements
• Matrix 2D wrapup
• In-class Exercise 25 - (20 lecture assignment points) due before the start of our next class.

Your task is to add some more functionality to the Matrix2D example and write code to test it in the main method there. The functionality you are to add:

• A method max that returns the largest number in the matrix (5 points)
• A destructive method, that is, a method that modifies the matrix on which it is called, named scale that multiplies each entry in the matrix by a number (5 points)
• A non-destructive method, that is, one that does not change the matrix on which it is called, named multiply that works much like add but computes the matrix-matrix multiplication result. If you don't remember how to multiply matrices, see the "Matrix Product" section of the Wikipedia entry to Matrix multiplication. (10 points)

Please demonstrate your program or submit only the file Matrix2D.java by email before the start of our next class. Email submissions should use a meaningful subject line, clearly indicating the course number and assignment name.

• Strings and Characters by example (Hangman)
• "Evil" Hangman
• Searching
• linear search
• binary search
• A bit on sorting
• selection sort
• insertion sort
• merge sort

Due at the start of class, Tuesday, May 3.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to terescoj AT strose.edu by the start of class. Please use a clear subject line when submitting by email (e.g., CSC 252 Lecture 25 Assignment, Mary Smith). We will discuss these questions at the start of class, so no late submissions are accepted.

Don't forget that the program for LA 24 is also due the same day!

• Give a simple example showing how a binary search can fail to find a value that exists in a given array if that array is not sorted. (2 points)
• If it takes 1 second to perform a selection sort on an array of 1000 elements, how long would you expect it to take to perform a selection sort on array of these sizes: 2000 elements, 10,000 elements, 1,000,000 elements? (3 points)
• Apply the selection sort algorithm to the array below. Show all steps. (5 points)
```9 4 7 8 2 1 3
```
• Apply the insertion sort algorithm to the array from the previous problem. Show all steps. (5 points)

Terminology

• searching
• binary search
• divide and conquer
• sorting
• selection sort
• insertion sort
• merge sort

Examples