Computer Science 252

Problem Solving with Java

Spring 2016, The College of Saint Rose

Agenda

- Announcements
- Lab 10: Final Project continues for one more week

- 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.- A method
- 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