Computer Science 252
Problem Solving with Java

Fall 2015, The College of Saint Rose

Home     Syllabus     Schedule     Examples     Style Guide     Refcard

Agenda

• Announcements
  • Submit Lab 10: Final Project by Friday
• Final exam information
  • Tuesday, 12/15, start at 10:45
  • same ground rules as exams 1 and 3: closed notes, closed book, closed network, closed neighbors
  • focus on recent topics, but everything from the course is fair game
  • necessary reference information will be included
  • practice exam questions out
  • optional review session 3:30 Monday in Albertus 212
• Lecture 24 assignment recap
• Strings and Characters by example (Hangman)
• "Evil" Hangman
• Searching
  • linear search
  • binary search
• A bit on sorting
  • selection sort
  • insertion sort
  • merge sort
• In-class Exercise 25 - (10 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 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.

Lecture 25 Assignment

Due at the start of class, Thursday, December 10.

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 , Joe Student). We will discuss these questions at the start of class, so no late submissions are accepted.

• 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

• Matrix2D
• Hangman