Transcript Summary

CS1101: Programming Methodology
http://www.comp.nus.edu.sg/~cs1101x/
Aaron Tan
This is Week 9
 Week 8:






Chapter 7: OOP Additional Details (cont.)
About String
Exercises
Chapter 8: Software Engineering
Chapter 9: Classes with Class Members
Exercises
 This week:
 Exercises
 Chapter 10 Arrays and ArrayLists
 Exercises
2
Exercises
 Please refer to BallV2.java and
BallV2Driver.java
 Have you completed the computeArea()
method in MyRectangle.java?
 Have you updated your MyRectangle.java to
include area as another data member (instance
variable)?
3
Insertion sort (1/6)
 We have discussed Selection sort and Bubble sort.

Let’s learn another basic sort: Insertion sort.
Algorithm basis


On pass i,
 Insert v[i] into the correct position in the sorted region to its
left: v[0]…v[i-1].
Example – pass 1 (assume n = 5)



Compare v[1] with v[0]
If v[1] < v[0], move v[1] to the front of v[0] (shifting needed)
The sorted region now consists of two elements: v[0] and v[1].
4
Insertion Sort (2/6)

Example – pass 1
Sorted region
0
1
2
3
4
v
10
5
7
1
6
v
5
10
7
1
6
Where to insert v[1]
in the sorted region
to its left (v[0])?
Sorted region
5
Insertion Sort (3/6)

Example – pass 2
Sorted region
0
1
2
3
4
v
5
10
7
1
6
v
5
7
10
1
6
Where to insert v[2] in
the sorted region to its
left (v[0] .. v[1])?
Sorted region
6
Insertion Sort (4/6)

Example – pass 3
Sorted region
0
1
2
3
4
v
5
7
10
1
6
v
1
5
7
10
6
Where to insert v[3] in
the sorted region to its
left (v[0] .. v[2])?
Sorted region
7
Insertion Sort (5/6)

Example – pass 4
Sorted region
0
1
2
3
4
v
1
5
7
10
6
v
1
5
6
7
10
Where to insert v[4] in
the sorted region to
its left (v[0] .. v[3])?
Sorted region
Sort completed!
8
Insertion Sort (6/6)

An array of n elements requires n-1 passes in insertion
sort. (This is the same for Selection sort and Bubble sort.)

Try to code insertion sort yourself.

In inserting the element being examined into the sorted region, try
to avoid using swaps. Instead, shift the affected elements to the
right one place to make way for the incoming element that is to be
inserted.
9
Searching
 Another classic computer science problem

Problem statement:
 Given a search value X, return the index of X in the

array if X is found. Otherwise, return -1.
We assume no duplicate value in the array.
 If there are duplicate values, we need to define which index
to be returned.
 Two algorithms
 Sequential search (also called linear search)
 Binary search (applicable for sorted array) – much
faster
10
Search result
Unsuccessful Search:
search( 45 )
-1
Successful Search:
search( 12 )
4
numbers
0
1
2
3
4
5
6
7
8
23
17
5
90
12
44
38
84
77
11
Sequential Search (or Linear Search)

Search the array from the first to the last
position in linear progression.
public static int linearSearch(int[] numbers, int searchValue)
{
for (int i=0; i<number.length; i++)
{
if (numbers[i] == searchValue)
return i;
}
return -1;
// not found
}
12
Cohesion (again)

Note that the linearSearch() method does not display
the index of the found element in the array, nor does it
even display any message on whether the search
value is found or not.

Instead, it returns the index of the first matching
element, or –1 if the search value is not found.

This follows the principle of cohesion – a method
should do a single task. In this case, it should leave it
to the caller to decide if any message needs to be
displayed.
13
Binary search
numbers


0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
If the array is sorted, then we can apply the binary search
technique.
The basic idea is straightforward. First search the value X
in the middle position of the array.



If X is the middle value, then found.
If X is less than the middle value, then search the middle of the left
half next.
If X is greater than the middle value, then search the middle of the
right half next. Continue in this manner.
14
Sequence of Successful Search (1/3)
#1
low
high
mid
0
8
4
search( 44 )
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
low
mid
38 < 44
high
low = mid+1 = 5
15
Sequence of Successful Search (2/3)
#1
#2
low
high
mid
0
5
8
8
4
6
search( 44 )
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
low
high = mid-1=5
mid
high
44 < 77
16
Sequence of Successful Search (3/3)
#1
#2
#3
low
high
mid
search( 44 )
0
5
5
8
8
5
4
6
5
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
Successful Search!!
44 == 44
low high
mid
17
Sequence of Unsuccessful Search (1/4)
#1
low
high
mid
0
8
4
search( 45 )
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
low
mid
38 < 45
high
low = mid+1 = 5
18
Sequence of Unsuccessful Search (2/4)
#1
#2
low
high
mid
0
5
8
8
4
6
search( 45 )
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
low
high = mid-1=5
mid
high
45 < 77
19
Sequence of Unsuccessful Search (3/4)
#1
#2
#3
low
high
mid
search( 45 )
0
5
5
8
8
5
4
6
5
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
low high
mid
44 < 45
low = mid+1 = 6
20
Sequence of Unsuccessful Search (4/4)
#1
#2
#3
#4
low
high
mid
search( 45 )
0
5
5
6
8
8
5
5
4
6
5
 low  high 
mid  

2

0
1
2
3
4
5
6
7
8
5
12
17 23
38
44
77
84
90
high
low
Unsuccessful Search
no more elements to search
low > high
21
Binary Search Routine
public
{
int
int
int
static int binarySearch(int[] numbers, int searchValue)
low = 0;
high = numbers.length – 1;
mid = (low + high) / 2;
while (low <= high && numbers[mid] != searchValue) {
if (numbers[mid] < searchValue)
low = mid + 1;
else // (numbers[mid] > searchValue)
high = mid - 1;
mid = (low + high) / 2;
// next midpoint
}
if (low > high) {
mid = -1;
}
return mid;
}
22
Binary Search Performance

Successful Search



Unsuccessful Search



Best Case: 1 comparison
Worst Case: log2N comparisons
Best Case = Worst Case: log2N comparisons
Since the portion of an array to search is cut into half after
every comparison, we compute how many times the array
can be divided into halves.
After K comparisons, there will be N/2K elements in the
list. We solve for K when N/2K = 1, deriving K = log2N.
23
Comparing Sequential Search and Binary
Search
Array size N
Sequential Search
N
Binary Search
log2 N
8
8
3
16
16
4
100
100
7
1,000
1,000
10
10,000
10,000
14
1,000,000
1,000,000
20
1,000,000,000
1,000,000,000
30
24
Chapter 10

Let’s continue with the rest of Chapter
10.
25
Common mistake (1/2)
When you have an array of objects, it’s
very common to forget to instantiate the
array’s objects.
 Programmers often instantiate the array
itself and then think they’re done – that
leads to “java.lang.NullPointerException”.

26
Common mistake (2/2)
Point[] array = new Point[3];
array
for (int i=0; i<array.length; i++) {
array[i].setLocation(1,2);
null
null
}
null
There are no objects referred to by
array[0], array[1], and array[2]!
Corrected code:
array
x
01
y
02
Point[] array = new Point[3];
for (int i=0; i<array.length; i++) {
array[i] = new Point();
x
01
y
02
array[i].setLocation(1,2);
}
x
01
y
02
27
Rows with different lengths (1/2)

It is possible to create 2D array where rows have
different lengths.
int[][] array = { {1,3,6}, {4,2}, {5,1,8,2} };
System.out.println(arr[0].length);
System.out.println(arr[1].length);
System.out.println(arr[2].length);
3
2
4
array
28
Rows with different lengths (2/2)

Code to process such array.
int[][] array = { {1,3,6}, {4,2}, {5,1,8,2} };
for (int i=0; i<array.length; i++) {
for (int j=0; j<array[i].length; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
29
Matrices


A two-dimensional array where all rows have the same
length is sometimes known as a matrix because it
resembles that mathematical concept.
A matrix A with m rows and n columns is represented
mathematically in the following manner.
a1  1 a 1 2  a 1 n
a2  1 a 2 2  a 2 n


am  1 a m 2  a m n

Note that in implementing the matrix as an array in
Java, the row number and column number start at 0
instead of 1.
30
Matrix Addition (1/2)

To add two matrices, both must have the same number
of rows, and the same number of columns.

To compute C = A + B, where A, B, C are matrices
 ci,j = ai,j + bi,j

Example on 33 matrices:
1 2 0
 1 0 0 




0 1 1   2 1 0 
1 0 1
 0 2  1




 0 2 0


  2 2 1
 1 2 0


31
Matrix Addition (2/2)
public static int[][] add(int[][] arrA, int[][] arrB) {
// determine number of rows in solution
int m = arrA.length;
// determine number of columns in solution
int n = arrB[0].length;
// create the array to hold the sum
int[][] arrC = new int[m][n];
// compute the matrix sum row by row
for (int i = 0; i < m; ++i) {
// produce the current row
for (int j = 0; j < n; ++j) {
arrC[i][j] = arrA[i][j] + arrB[i][j];
}
}
return arrC;
}
32
Matrix Multiplication (1/2)

To multiply two matrices A and B, the number of
columns in A must be the same as the number of rows
in B. The resulting matrix has same number of rows as
A and number of columns as B.

For example, multiplying a 45 matrix with a 53 matrix
gives a 43 matrix.
33
Matrix Multiplication (2/2)

To compute C = A  B, where A, B, C are matrices
 ci,j = (ai,1  b1,j ) + (ai,2  b2,j ) + . . . + (ai,n  bn,j )
 ci,j
is sum of terms produced by multiplying the
elements of A’s row i with B’s column j.

Example on 33 matrices:
1 2 0
 1 0 0 




0 1 1   2 1 0 
1 0 1
 0 2  1




3 2 0


  2 3  1
  1 2  1


34
Exercises
 Download Matrices.java and complete
the matrixProduct() method.
 Try last year’s lab #7 exercises:
 Sudoku
 Rabbit Jumps
 Polygon
 Go to course website, “Labs” page to
retrieve last year’s lab write-ups:
 http://www.comp.nus.edu.sg/~cs1101x/3_ca/labs.html
35
Announcement/Reminder
 Lab #4
 Released: 14 October (Tuesday), 2359 hr.
 Deadline: 22 October (Wednesday), 2359 hr.
 Identical codes
 Please do not share codes for your lab
assignments!
 Last year’s lab assignments
 They are now on the course website, under
“CA”, “Labs”, for your own practice.
36
This is Week 9
 Next week?
 Chapter 11 Type Details and Alternate
Coding Mechanisms
 Another mini programming test!
37
End of file
38