Transcript CS1101: Programming Methodology

CS1101: Programming Methodology
http://www.comp.nus.edu.sg/~cs1101x/
Aaron Tan
Week 1: Introduction







History of computers
Components of a computer
Binary numbers
Introduce high-level programming languages
Introduce Java programming, compilation
and execution.
Present useful problem-solving strategies.
Writing algorithms in pseudo-codes.
CS1101X Introduction
2
History of Computers
 Websites
 ACM Timeline of Computing History
(http://www.computer.org/computer/timeline)
 The Virtual Museum of Computing
(http://www.comlab.ox.ac.uk/archive/other/museu
ms/computing.html)
 IEEE Annals of the History of Computing
(http://www.computer.org/annals/)
 and others (surf the web)
CS1101X Introduction
3
Computers as Information
Processors (1/2)
 Unlike previous inventions, computers are
special because they are general-purpose.
 Could be used to perform a variety of tasks.
 Computer = Hardware + Software.
 Hardware: physical components for
computation/processing; should be simple, fast,
reliable.
 Software: set of instructions to perform tasks to
specifications; should be flexible, user-friendly,
sophisticated.
CS1101X Introduction
4
Computers as Information
Processors (2/2)
Computer are Information Processors
Raw
data
Computer
system
Processed
information
Data Units:
1 bit (binary digit): one of two values (0 or 1).
1 byte: 8 bits.
1 word: 1, 2, or 4 bytes, or more (depends on ALU).
CS1101X Introduction
5
Components of a Computer (1/2)
 Main Components:
 CPU (Central Processing Unit: controls devices and
processes data).
 Memory: stores programs and intermediate data.
 Input Devices: accept data from outside world.
 Output Devices: presents data to the outside world.
 An analogy with Human Information Processors:
 CPU – brain’s reasoning powers
 Memory – brain’s memory
 Input Devices – eyes, ears, sensory sub-system
 Output Devices – mouth, hands, facial and body
expressions
CS1101X Introduction
6
Components of a Computer (2/2)
Headphone
(Output)
Monitor
(Output)
Hardware box
(contains processor,
memory, buses etc.)
Mouse and Keyboard (Input)
CS1101X Introduction
7
Decimal Number System




Also called the base-10 number system.
10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
In general,
(anan-1… a0 . f1f2 … fm)10 =
(an x 10n) + (an-1x10n-1) + … + (a0 x 100) +
(f1 x 10-1) + (f2 x 10-2) + … + (fm x 10-m)
Weighting factors (or weights) are in powers-of-10:
… 103 102 101 100.10-1 10-2 10-3 10-4 …
 Example: 593.68. The digit in each position is
multiplied by the corresponding weight:
5102 + 9101 + 3100 + 610-1 + 810-2
= (593.68)10
CS1101X Introduction
8
Other Number Systems
 Binary (base 2): weights in powers-of-2.
 Binary
digits (bits): 0,1.
 Essential in computing.
 Octal (base 8): weights in powers-of-8.
 Octal
digits: 0,1,2,3,4,5,6,7.
 Hexadecimal (base 16): weights in powers-of16.
 Hexadecimal
digits:
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.
 Base R: weights in powers-of-R.
CS1101X Introduction
9
Base-R to Decimal Conversion
 (1101.101)2 = 123 + 122 + 120 + 12-1 + 12-3
= 8 + 4 + 1 + 0.5 + 0.125 = (13.625)10
 (572.6)8 = 582 + 781 + 280 + 68-1
= 320 + 56 + 2 + 0.75 = (378.75)10
 (2A.8)16 = 2161 + 10160 + 816-1
= 32 + 10 + 0.5 = (42.5)10
 (341.24)5 = 352 + 451 + 150 + 25-1 + 45-2
= 75 + 20 + 1 + 0.4 + 0.16 = (96.56)10
CS1101X Introduction
10
Decimal to Binary Conversion (1/2)
 Whole number: repeated division-by-2 method.
 To convert a whole number to binary, use successive
division by 2 until the quotient is 0. The remainders
form the answer, with the first remainder as the least
significant bit (LSB) and the last as the most
significant bit (MSB).
(43)10 = (101011)2
CS1101X Introduction
2
2
2
2
2
2
43
21
10
5
2
1
0
rem 1  LSB
rem 1
rem 0
rem 1
rem 0
rem 1  MSB
11
Decimal to Binary Conversion (2/2)
 Fractions: repeated multiply-by-2 method.
 To convert decimal fractions to binary, repeated
multiplication by 2 is used, until the fractional product
is 0 (or until the desired number of decimal places).
The carried digits, or carries, produce the answer,
with the first carry as the MSB, and the last as the
LSB.
(0.3125)10 = (.0101)2
CS1101X Introduction
0.31252=0.625
0.6252=1.25
0.252=0.50
0.52=1.00
Carry
0
1
0
1
MSB
LSB
12
Mathematics
 A-level Mathematics assumed.
 Common concepts encountered in programming:

prime numbers, complex numbers, polynomials,
matrices.
Mathematical maturity desirable.
CS1101X Introduction
13
Software (1/4)

Program


Execution


Performing the instruction sequence
Programming language


Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors



Machine language or object code
Assembly language
High-level
CS1101X Introduction
14
Software (2/4)

Program


Execution


Performing the instruction sequence
Programming language


Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors



Machine language or object code
Program to which computer
Assembly language
can respond directly. Each
High-level
instruction is a binary code
that corresponds to a native
instruction.
Example: 0001001101101110
CS1101X Introduction
15
Software (3/4)

Program


Execution


Performing the instruction sequence
Programming language


Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors



Machine language or object code
Assembly language
Symbolic language
High-level
for coding machine
language instructions.
Example: ADD A, B, C
CS1101X Introduction
16
Software (4/4)

Program


Execution


Performing the instruction sequence
Programming language


Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors



Machine language or object code
Assembly language
Detailed knowledge of the
High-level
machine is not required. Uses a
vocabulary and structure closer
to the problem being solved.
Examples: Java, C, C++,
Prolog, Scheme.
CS1101X Introduction
17
Translation


High-level language programs (source programs)
must be translated into machine code for execution
Translator


Compiler


Accepts a program written in a source language and
translates it to a program in a target language
Standard name for a translator whose source language is
a high-level language
Interpreter

A translator that both translates and executes a source
program
CS1101X Introduction
18
Java

A high-level object-oriented language developed by
Sun.

Two types of Java programs



Applet: runs within a web browser.
Application: a complete stand-alone program.
Java’s clean design and wide availability make it an
suitable language for teaching the fundamentals of
computer programming.
CS1101X Introduction
Acknowledgement: Cohoon and Davidson
19
Java translation


Two-step process
First step


Translation from Java to bytecodes
 Bytecodes are architecturally neutral object code
 Bytecodes are stored in a file with extension .class
Second step

An interpreter translates the bytecodes into machine
instructions and executes them
 Interpreter is known as a Java Virtual Machine (JVM), a
program that mimics the operation of a real machine
 JVM reads the bytecodes produced by Java compiler and
executes the bytecodes
CS1101X Introduction
Acknowledgement: Cohoon and Davidson
20
Task

Ask for user’s name and display a welcome message.
Hi <name>.
Welcome to CS1101!
CS1101X Introduction
Acknowledgement: Cohoon and Davidson
21
Sample output
Compilation
Interpretation
Program output
CS1101X Introduction
22
Welcome.java (1/4)
// Author: Aaron Tan
// Purpose: Ask for user’s name and display a welcome message.
import java.util.*;
public class Welcome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“What is your name? ");
String name = scanner.next();
System.out.println("Hi " + name + ".");
System.out.println("Welcome to CS1101!\n");
}
}
CS1101X Introduction
23
Welcome.java (2/4)
// Author: Aaron Tan
// Purpose: Ask for user’s name and display a welcome message.
import java.util.*;
public class Welcome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“What is your name? ");
String name = scanner.next();
System.out.println("Hi " + name + ".");
System.out.println("Welcome to CS1101!\n");
}
These statements make up the action of method
}
main().
Method main() is part of class Welcome.
CS1101X Introduction
24
Welcome.java (3/4)
// Author: Aaron Tan
// Purpose: Ask for user’s name and display a welcome message.
import java.util.*;
public class Welcome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“What is your name? ");
String name = scanner.next();
System.out.println("Hi " + name + ".");
System.out.println("Welcome to CS1101!\n");
}
}
CS1101X Introduction
A method is a named piece of code that performs
some action or implements a behavior.
25
Welcome.java (4/4)
// Author: Aaron Tan
// Purpose: Ask for user’s name and display a welcome message.
import java.util.*;
public class Welcome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“What is your name? ");
String name = scanner.next();
System.out.println("Hi " + name + ".");
System.out.println("Welcome to CS1101!\n");
}
}
CS1101X Introduction
An application program is required to have a
public static void method named main().
26
Problem Solving Process (1/3)




Analysis
Design
Implementation
Testing
Determine the inputs, outputs, and other components
of the problem.
Description should be sufficiently specific to allow you to solve
the problem.
CS1101X Introduction
27
Problem Solving Process (1/3)




Analysis
Design
Implementation
Testing
Describe the components and associated processes
for solving the problem.
Straightforward and flexible
Method – process
Object – component and associated methods
CS1101X Introduction
28
Problem Solving Process (1/3)




Analysis
Design
Implementation
Testing
Develop solutions for the components and use those
components to produce an overall solution.
Straightforward and flexible
CS1101X Introduction
29
Problem Solving Process (1/3)




Analysis
Design
Implementation
Testing
Test the components individually and collectively.
CS1101X Introduction
30
Problem Solving Process (2/3)
CS1101X Introduction
31
Problem Solving Process (3/3)

Refer also to Jumpstart to SoC on course website,
“Misc…”, “For Freshmen”.
CS1101X Introduction
32
Pólya: How to Solve It (1/2)
A great discovery solves a great problem but there is a
grain of discovery in the solution of any problem.
Your problem may be modest; but if it challenges your
curiosity and brings into play your inventive faculties,
and if you solve it by your own means, you may
experience the tension and enjoy the triumph of
discovery.
Such experiences at a susceptible age may create a
taste for mental work and leave their imprint on mind
and character for a lifetime.
-- George Pólya
CS1101X Introduction
33
Pólya: How to Solve It (2/2)

Phase 1: Understanding the problem

Phase 2: Devising a plan

Phase 3: Carrying out the plan

Phase 4: Looking back
CS1101X Introduction
34
Pólya: How to Solve It (2/2)

Phase 1: Understanding the problem

Phase 2: Devising a plan

Phase 3: Carrying out the plan

Phase 4: Looking back

What is the unknown? What are the data?

What is the condition? Is it possible to satisfy the
condition? Is the condition sufficient to determine the
unknown?

Draw a figure. Introduce suitable notation.
CS1101X Introduction
35
Pólya: How to Solve It (2/2)

Phase 1: Understanding the problem

Phase 2: Devising a plan

Phase 3: Carrying out the plan

Phase 4: Looking back

Have you seen the problem before? Do you know a related
problem?

Look at the unknown. Think of a problem having the same or
similar unknown.

Split the problem into smaller sub-problems.

If you can’t solve it, solve a more general version, or a
special case, or part of it.
CS1101X Introduction
36
Pólya: How to Solve It (2/2)

Phase 1: Understanding the problem

Phase 2: Devising a plan

Phase 3: Carrying out the plan

Phase 4: Looking back

Carry out your plan of the solution. Check each step.

Can you see clearly that the step is correct?

Can you prove that it is correct?
CS1101X Introduction
37
Pólya: How to Solve It (2/2)

Phase 1: Understanding the problem

Phase 2: Devising a plan

Phase 3: Carrying out the plan

Phase 4: Looking back

Can you check the result?

Can you derive the result differently?

Can you use the result, or the method, for some other
problem?
CS1101X Introduction
38
Algorithmic Problem Solving

An algorithm is a well-defined computational
procedure consisting of a set of instructions, that takes
some value or set of values, as input, and produces
some value or set of values, as output.
Input
CS1101X Introduction
Algorithm
Output
39
Algorithm

Each step of an algorithm must be exact.

An algorithm must terminate.

An algorithm must be effective.

An algorithm must be general.

Can be presented in pseudo-code or flowchart.
CS1101X Introduction
40
Euclidean algorithm

First documented algorithm by Greek mathematician
Euclid in 300 B.C.

To compute the GCD (greatest common divisor) of two integers.
1. Let A and B be integers with A > B ≥ 0.
2. If B = 0, then the GCD is A and algorithm ends.
3. Otherwise, find q and r such that
A = q.B + r
where 0 ≤ r < B
Note that we have 0 ≤ r < B < A and GCD(A,B) = GCD(B,r).
Replace A by B, and B by r. Go to step 2.
CS1101X Introduction
41
Find minimum, maximum and average (1/3)

Version 1
First, you initialise sum to zero, min to a very big number, and max
to a very small number.
Then, you enter the numbers, one by one.
For each number that you have entered, assign it to num and add it
to the sum.
At the same time, you compare num with min, if num is smaller
than min, let min be num instead.
Similarly, you compare num with max, if num is larger than max, let
max be num instead.
After all the numbers have been entered, you divide sum by the
numbers of items entered, and let ave be this result.
End of algorithm.
CS1101X Introduction
42
Find minimum, maximum and average (2/3)

Version 2
sum  count  0
// sum = sum of numbers;
// count = how many numbers are entered?
min  ?
// min to hold the smallest value eventually
max  ?
// max to hold the largest value eventually }
for each num entered,
increment count
sum  sum + num
if num < min then min  num
if num > max then max  num
ave  sum / count
CS1101X Introduction
43
Find minimum, maximum and average (3/3)
start

Terminator box
Flowchart
Process box
sum  count  0
min  ?
max  ?
Yes
Decision box
end of
input?
No
increment count
sum  sum + num
num < min?
ave  sum/count
Yes
min  num
Yes
max  num
No
num > max?
No
CS1101X Introduction
end
44
Control structures

Sequence

Branching (selection)

Loop (repetition)
CS1101X Introduction
45
Examples (1/4)

Example 1: Compute the average of three integers.
Variables used:
A possible algorithm:
num1
enter values for num1, num2, num3
ave  ( num1 + num2 + num3 ) / 3
print ave
Variables used:
num1
CS1101X Introduction
num3
ave
Another possible algorithm:
enter values for num1, num2, num3
total  ( num1 + num2 + num3 )
ave  total / 3
print ave
num2
num2
num3
total
ave
46
Examples (2/4)

Example 2: Arrange two integers in increasing order
(sort).
Algorithm A:
enter values for num1, num2
// Assign smaller number into final1,
// larger number into final2
if num1 < num2
then final1  num1
final2  num2
else final1  num2
final2  num1
Variables used:
num1
num2
final1
final2
// Transfer values in final1, final2 back to num1, num2
num1  final1
num2  final2
// Display sorted integers */
print num1, num2
CS1101X Introduction
47
Examples (3/4)

Example 2: Arrange two integers in increasing order
(sort).
Algorithm B:
enter values for num1, num2
// Swap the values in the variables if necessary
if num2 < num1
then temp  num1
num1  num2
num2  temp
Variables used:
num1
num2
temp
// Display sorted integers */
print num1, num2
CS1101X Introduction
48
Examples (4/4)

Example 3: Find the sum of positive integers up to n
(assuming that n is a positive integer).
Algorithm:
enter value for n
// Initialise a counter count to 1, and ans to 0
count  1
ans  0
while count <= n do the following
ans  ans + count
// add count to ans
count  count + 1
// increase count by 1
Variables used:
n
count
ans
// Display answer
print ans
CS1101X Introduction
49
Task 1: Area of a circle (1/2)

What is the data? Side of
square = 2a

What is the unknown? Area
of circle, C.

What is the condition? If
radius r is known, C can be
calculated.

How to obtain r?
2a
CS1101X Introduction
50
Task 1: Area of a circle (2/2)
a

r
Pythagoras’ theorem:
r2 = 2 * a2
a

Area of circle
C =  * r2
=  * 2 * a2
CS1101X Introduction
51
Task 2: Pascal’s triangle
1
1 1
Compute nCk or C(n,k)
1 2 1
nC = n! / (k! * (n – k)!)
1 3 3 1
k
1 4 6 4 1
1 5 10 10 5 1
CS1101X Introduction
52
Task 3: NE-paths

To find the number of north-east paths between any
two points.

North-east (NE) path: you may only move northward or
eastward.

How many NE-paths between A and C?
C
A
A
A
A
CS1101X Introduction
53
Task 4: Finding maximum

Given three numbers, find the maximum value.


Example: 4, 7, 3. Answer: 7
Can you extend the algorithm to four numbers, five
numbers, in general, n numbers?
CS1101X Introduction
54
Task 5: Palindrome

A word is a palindrome if it reads the same forward and
backward.


Examples: NOON, RADAR.
How do you determine if a word is a palindrome?
CS1101X Introduction
55
Task 6: Coin change

Given this list of coin denominations: $1, 50 cents, 20
cents, 10 cents, 5 cents, 1 cent, find the smallest
number of coins needed for a given amount. You do
not need to list out what coins are used.

Example 1: For $3.75, 6 coins are needed.

Example 2: For $5.43, 10 coins are needed.
CS1101X Introduction
56
End of File
CS1101X Introduction
57