Transcript Summary

CS1101: Programming Methodology
http://www.comp.nus.edu.sg/~cs1101x/
Aaron Tan
This is Week 6
 Last week:
 Week 4’s Exercise 5 (Prime number)
 A mini programming test!
 Chapter 5: Using Pre-Built Methods
 Other classes: Random, DecimalFormat
 This week:
 Chapter 10: Arrays
 Only sections 10.1 to 10.6
 We will cover the other sections some other time.
2
Arrays
 In computer science, we deal with very large

amount of data.
 Eg: 3000 integers, 365 days, 1 million real numbers.
 Do you want to create so many variables?
If the data are homogeneous (of the same
type), we can group them into a single
collection.
 Array is an indexed collection of homogeneous

data.
Let’s get to Chapter 10 now!
3
Array Declaration Syntax
 Array declaration syntax:
<element-type>[] <array-variable>;
Example: double[] values;
 Alternative syntax:
<element-type> <array-variable>[];
Example: double values[];
 I prefer the first one, it’s more readable and
meaningful. The second form is more
commonly used by C/C++ programmers.
4
Classic Array Problems
 Sum the values in an array.
 Find the maximum (or minimum) value in an


array.
Search for a value in an array.
Sort the values in an array.
5
Loading an Array
 Before we solve a problem involving array, we need to
first load values into the array!
 If you know the values before-hand, use array element
initialization
 Eg: int[] numbers = { 3, 7, -12, 8, 7 };
 Slides 12 and 14 of Chapter 10
 If not, you need to read the values from the user
 Use a loop to read in the values
 Slides 6-7, and 15-16 of Chapter 10
 We will learn how to read data from a file some other
time.
6
Exercise 1: Summing an Array
 Write a program SumArray.java to compute the sum of
all the values in an array containing double values.
Display the sum in 3 decimal places.
 Let’s do it into 2 phases: load the array with values
first, then compute the sum. (Instead of accumulating
the sum as we load the array.)
Size of array: 10
Enter 10 values: 5.1 16 3.2 1.8 -4 12.3 8 3.3 -2 9.1
The sum is 52.800
 Download SumArray.java from course website,
“Resources”, “Lectures” page.
7
Exercise 2: Finding maximum value
 Write a program FindMax.java to find the largest value
in an integer array. (Assume there is at least one
element in the array.)
Size of array: 5
Enter 5 values: 10 -20 43 79 8
The largest value is 79
 Take home exercise: What if you want to report the
index of the largest value, instead of the value itself?
(This problem is not well-defined! Why?)
Size of array: 5
Enter 5 values: 10 -20 43 79 8
The largest value is at index 3
8
Common Mistake: Index Out of Range
 Beware of ArrayIndexOutOfBoundsException.
public static void main(String[] args) {
int numbers = new int[10];
. . .
for (int i=1; i<=numbers.length; i++)
System.out.println(numbers[i]);
}
9
Modular Programming (1/5)
 As our problems get more complex, the main() method
might get too long.
 It is advisable to split the problem into smaller subproblems, and to write appropriate methods for the
sub-problems.
 In general a problem is solved in 3 steps: input 
computation  output.
 It is customary to write a separate method to perform
the computation step. (If the computation is complex, it
should be split further into smaller steps and each step
performed by a method.)
10
Modular Programming (2/5)
 Download CheckNRIC.java program which we did
before. Here’s the partial code:
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
These variables
are used in the
computation of
the check code.
System.out.print("Enter 7-digit NRIC number: ");
int number = stdIn.nextInt();
int digit7, digit6, digit5, digit4, digit3,
digit2, digit1, step1, step2, step3;
char checkCode;
// computation of check code - code omitted
...
System.out.println("Check code = " + checkCode);
}
11
Modular Programming (3/5)
 ‘Modularizing’ CheckNRIC.java:
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("Enter 7-digit NRIC number: ");
int number = stdIn.nextInt();
char checkCode;
// computation of check code
checkCode = generateCheckCode(number);
System.out.println("Check code = " + checkCode);
}
Delegate the job to the
method
generateCheckCode().
What are you expecting
generateCheckCode() to
return? A character.
Pass number into the
method
generateCheckCode().
12
Modular Programming (4/5)
The method returns
a character.
 How does generateCheckCode() method look like?
public static char generateCheckCode(int num) {
// Extract digits
int digit7 = num%10; num /= 10;
int digit6 = ...
...
char code = ...
...
return code;
}
The method
expects an integer
argument.
The return statement
passes the character
to the caller.
 Download NewCheckNRIC.java and compare it with
CheckNRIC.java.
13
Modular Programming (5/5)
 Let’s see how we can “modularize” our

programs for the previous two exercises.
I will show you NewSumArray.java and
NewFindMax.java.
14
Exercise 3: Coin Change



Download the file CoinChange.java from the
course website, “Resources”, “Lectures”.
Rewrite it using an array of coin denominations
(int[] coins). Name your program
NewCoinChange.java.
Modularize your program by writing a method
computeCoins().
 What
is its return type?
 Does it have any argument? If so, what is the type
of its argument?
15
Method main() (1/2)
 Now that we have learnt array, let’s check out the
main() method.
 Usual signature for main() method:
public static void main(String[] args)

 args is an array of String objects
Consider this:
public class Demo {
public static void main(String[] args) {
for (int i=0; i<args.length; i++)
System.out.println("args[" + i + "]: " + args[i]);
} // end main
} end Demo
16
Method main() (2/2)
 This allows user to specify command line arguments
when executing the program.
java Demo 10 ABC-D hello "Ice Cream"
 Output:
args[0]:
args[1]:
args[2]:
args[3]:
10
ABC-D
hello
Ice Cream
17
Sorting and Searching
 I will be covering more topics in every lecture

from now on to make up for the lost lecture on
27 October (Deepavali).
 Sorting
 Searching
The above two topics are not included in the
mid-term test.
18
Sorting
 Classic computer science problem
 Sort an array
 Three basic (but slow) sorting algorithms
 Selection sort
 Bubblesort
 Insertion sort
 Other faster sorting algorithms (covered in
CS1102 and other advanced modules)
 Mergesort
 Quicksort
 Heapsort, etc.
19
Selection Sort (1/2)
1.
Find the smallest
element in the list.
2. Exchange the element in
the first position and the
smallest element. Now the
smallest element is in the
first position.
3. Repeat Step 1 and 2 with
the list having one less
element (i.e., the smallest
element is discarded from
further processing).
min
first
0
1
2
3
4
5
6
7
8
23
17
5
90
12
44
38
84
77
exchange
0
1
2
3
4
5
6
7
8
5
17
23 90
12
44
38
84
77
sorted
unsorted
This is the result of one pass.
20
Selection Sort (2/2)
Pass #
1
0
1
2
3
4
5
6
7
8
5
17
23 90
12
44
38
84
77
Result AFTER one
pass is completed.
sorted
2
5
12
23 90
17
44
38
84
77
3
5
12
17 90
23
44
38
84
77
7
5
12
17 23
38
44
77
84
90
8
5
12
17 23
38
44
77
84
90
21
Bubble Sort (1/2)
 Algorithm
Assume array is arr
for (int i = arr.length – 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j+1]
swap arr[j] with arr[j+1]
}
}
 Can you write the code?
22
Bubble Sort (2/2)
0
1
23 17
2
3
5
4
5
6
7
Showing the first pass…
8
90 12 44 38 84 77
17 5
exchange
17 23
5
exchange
90 12 44 38 84 77
17 5
exchange
17 5
17 5
23 12 44 38 90 84 77
exchange
23 90 12 44 38 84 77
ok
23 12 44 90 38 84 77
17 5
exchange
23 12 90 44 38 84 77
exchange
23 12 44 38 84 90 77
exchange
17 5
23 12 44 38 84 77 90
The largest value 90 is at the end of
the list.
23
Searching
 Another classic computer science problem
 Search for a value in a list of items
 Two algorithms
 Sequential search (also called linear search)
 Binary search (applicable for sorted array) – much
faster
24
Announcement/Reminder (1/2)
 Lab #2
 Release: 16 September (Tuesday), 2359hr.
 Deadline: 1 October (Wednesday), 2359hr.
 Identical codes
 Please do not share codes for your lab assignments!
25
Announcement/Reminder (2/2)
 Consultation
 24 September (Wednesday), 10am – 12nn.
 I will be in PL3.
 Mid-term test
 4 October, Saturday, 12noon, LT15 (for CS1101X
students)
 Refer to course website for more info:
http://www.comp.nus.edu.sg/~cs1101x/3_ca/termtests.html
26
This is Week 6
 Next week?
 Recess! (Hooray!)
 The week after next?
 Chapter 6 Object-Oriented Programming
(finally!)
 Mid-term test (argh!)
27
End of file
28