Transcript ppt - Courses

i206: Lecture 5:
Algorithms and Pseudocode
Marti Hearst
Spring 2012
1
Let’s Go Through Another
Machine/Assembly Language program
Goal: Count from 0 to 5, incrementing by 1 each time
Images from http://courses.cs.vt.edu/~csonline/MachineArchitecture/Lessons/
2
Let’s Go Through Another
Machine/Assembly Language program
http://courses.cs.vt.edu/~csonline/MachineArchitecture/Lessons/CPU/index.html
3
How does it all start?
Bootstrapping!
• How do you get the code loaded into memory
in the first place?
• Here is one trick:
– Hardcode one instruction into the first word of RAM.
– The Program Counter always starts at the first
memory address.
– The program is stored on an external memory
device.
• Floppy disk, flash memory drive, etc.
4
How does it all start?
Bootstrapping!
• Loop:
– Is the input blank?
• Then Halt
– Else
• Read an addressing instruction from the input into
memory address 1.
• Read an instruction from the input into the location
that is currently pointed to in memory address 1.
• Jump to the top of the loop.
5
Instruction
in Input
(one line)
Address
in RAM
Contents
of RAM
Meaning
00*
001*
Read input into
memory address 01
002
800
01
010
017
011
02
03
018
04
012
…
117
10
013
11
218
12
…
13
…
After a line of input is processed,
the next line is read in.
*First instruction is hard-coded
into RAM
Instruction
in Input
(one line)
Address
in RAM
Contents
of RAM
Meaning
00*
001*
Read input into
memory address 01
01
002
Read input into
memory address 02
800
010
017
011
02
03
018
04
012
…
117
10
013
11
218
12
…
13
…
7
Instruction
in Input
(one line)
010
Address
in RAM
Contents
of RAM
Meaning
00*
001*
Read input into
memory address 01
01
002
Read input into
memory address 02
02
800
Jump to instruction
in address 00
017
011
03
018
04
012
…
117
10
013
11
218
12
…
13
…
8
Instruction
in Input
(one line)
010
017
011
018
012
117
013
218
…
Address
in RAM
Contents
of RAM
Meaning
00*
001*
Read input into
memory address 01
01
010
Read input into
memory address 10
02
800
Jump to instruction
in address 00
017
(program code)
03
04
…
10
11
12
13
…
9
Instruction
in Input
(one line)
Address
in RAM
Contents
of RAM
Meaning
00*
001*
Read input into
memory address 01
01
011
Read input into
memory address 11
02
800
Jump to instruction
in address 00
011
03
018
04
012
…
117
10
017
(program code)
11
018
(program code)
013
218
…
12
13
…
10
Instruction
in Input
(one line)
Address
in RAM
Contents
of RAM
Meaning
00*
001*
Read input into
memory address 01
01
012
Read input into
memory address 12
02
800
Jump to instruction
in address 00
03
04
012
…
117
10
017
(program code)
11
018
(program code)
12
117
(program code)
013
218
…
13
…
11
Summary of This Unit
Programming Languages
Assembly Language
CPU
Address Space
Circuits
Code vs. Data
Gates
Machine Instructions
Orders of Magnitude
Boolean Logic
Number Systems
Bits & Bytes
Binary Numbers
12
Summary of This Unit
• Boolean logic is used to make logic gates,
which build up into circuits.
• Binary is used to represent both code and data
in memory, in instruction registers, and in the
arithmetic logic unit.
• Binary instructions move through the circuits,
controlling the computer’s operation and also
doing the operations themselves.
– Adding, subtracting, moving locations.
• This is pretty much what it takes to do
computation!
13
Distributed
Systems
Boolean Logic
CPU Operation
Security
Cryptography
Network
Standards
& Protocols
Inter-process
Communication
I/O
Operating
System
Methodologies/
Tools
Process
Application
Memory
Compiler/
Interpreter
Analysis
Data Structures
Op-code, operands
Instruction set arch
Data
storage
Circuits
Lossless v. lossy
Info entropy &
Huffman code
Numbers, text,
audio, video,
image, …
Assembly
Instructions
Algorithms
Machine
Instructions
CPU
Data
compression
Formal models
Finite automata
regex
Program
Memory
hierarchy
Design
Principles
Decimal,
Hexadecimal,
Binary
Data
Data
Representation
Gates
Adders, decoders,
Memory latches,
ALUs, etc.
Boolean
Logic
AND, OR, NOT,
XOR, NAND, NOR,
etc.
Number
Systems
Binary
Numbers
Bits & Bytes
Truth table
Venn Diagram
DeMorgan’s Law
14
Distributed
Systems
Analysis of
Algorithms
Security
Cryptography
Network
Standards
& Protocols
Inter-process
Communication
I/O
Operating
System
Methodologies/
Tools
Process
Application
Program
Memory
hierarchy
Memory
ALUs, Registers,
Compiler/
Program Counter,
Instruction Register Interpreter
Analysis
Big-O
Data Structures
Op-code, operands
Instruction set arch
Data
storage
Circuits
Lossless v. lossy
Info entropy &
Huffman code
Numbers, text,
audio, video,
image, …
Algorithms
Formal models
Machine
Instructions
CPU
Data
compression
Assembly
Instructions
Design
Principles
Decimal,
Hexadecimal,
Binary
Data
Data
Representation
Gates
Adders, decoders,
Memory latches,
ALUs, etc.
Boolean
Logic
AND, OR, NOT,
XOR, NAND, NOR,
etc.
Number
Systems
Binary
Numbers
Bits & Bytes
Truth table
Venn Diagram
DeMorgan’s Law
15
The central role of algorithms in
computer science
From Brookshear; Copyright 2003 Pearson Education
16
What is an algorithm?
• The idea behind the computer program.
• Stays the same independent of:
– Which kind of hardware it is running on
– Which programming language it is written in
• Solves a well-specified problem in a general way
• Is specified by:
– Describing the set of instances (input) it must work on
– Describing the desired properties of the output
Adapted from http://www.cs.sunysb.edu/~algorith/lectures-good/node1.html
17
Brookshear’s Definition
• An algorithm is
–
–
–
–
an ordered set
of unambiguous
executable
steps that defines a terminating process.
18
Algorithms: Levels of Abstraction
• Problem: motivation for algorithm
• Algorithm: procedure to solve the
problem
– Often one of many possibilities
• Representation: description of
algorithm sufficient to communicate it
to the desired audience
– Always one of many possibilities
– Programs are representations of algoirthms
19
Folding a Bird from a Square
Piece of Paper
Origami Primitives
Source: Brookshear
20
Origami primitives
Syntax
vs. Semantics
From Brookshear; Copyright 2003 Pearson Education
21
Important Properties of Algorithms
• Correct
– always returns the desired output for all legal
instances of the problem.
• Unambiguous
• Precise
• Efficient
– Can be measured in terms of
• Time
• Space
– Time tends to be more important
Adapted from http://www.cs.sunysb.edu/~algorith/lectures-good/node1.html
22
Algorithm for a Machine Cycle in a CPU
• Until the instruction = HALT, execute the
following steps:
a. Fetch an instruction.
b. Decode the instruction.
c. Execute the instruction.
23
Algorithms
• Hand-waving not allowed!
24
Algorithms
• Hand-waving not allowed!
• Specifying an algorithm requires you to say what is
really involved in making it work.
• Example:
– How does a computer work?
– Hand-wave: zeros & ones
– Real answer: see first two weeks of class.
• You learn to know when you don’t know
– “I know nothing except the fact of my ignorance.”
– Socrates, from Diogenes Laertius, Lives of Eminent Philosophers
25
Expressing Algorithms
• English description
More easily
expressed
• Pseudo-code
More
precise
• High-level
programming language
Adapted from http://www.cs.sunysb.edu/~algorith/lectures-good/node1.html
26
Pseudo-code
• A shorthand for specifying algorithms
• Leaves out the implementation details
• Leaves in the essence of the algorithm
-1
Code corrected from Brookshear; Copyright 2003 Pearson Education
27
Sequential search algorithm in
pseudo-code
From Brookshear; Copyright 2003 Pearson Education
28
Primitive Operations
•
•
•
•
•
•
•
Assign a value to a variable
Call a method
Arithmetic operation
Comparing two numbers
Indexing into an array
Following an object reference
Returning from a method
29
The RAM Model
• Random Access Machine (not Memory)
• An idealized notion of how the computer works
– Each "simple" operation (+, -, =, if) takes exactly 1
step.
– Each memory access takes exactly 1 step
– Loops and method calls are not simple operations,
but depend upon the size of the data and the
contents of the method.
• Measure the run time of an algorithm by
counting the number of steps.
Adapted from http://www.cs.sunysb.edu/~algorith/lectures-good/node1.html
30
Counting Primitive Operations
Algorithm ArrayMax(A,n)
Input: An array A storing N integers
Output: The maximum element in A.
currentMax A[0]
for i 1 to n-1 do
if currentMax < A[i] then
currentMax A[i]
return currentMax
Adapted from Goodrich & Tamassia
31
Counting Primitive Operations
Algorithm ArrayMax(A,n)
Input: An array A storing N integers
Output: The maximum element in A.
n-1
times
currentMax A[0] 2 steps + 1 to initialize i
for i 1 to n-1 do 2 step each time (compare i to n, inc i)
if currentMax < A[i] then 2 steps
currentMax A[i] 2 steps
How often done??
return currentMax 1 step
Between 4(n-1) and 6(n-1) in the loop
It depends on the sort order the numbers appear in A[]
Adapted from Goodrich & Tamassia
32
Algorithm Complexity
• Worst Case Complexity:
– the function defined by the maximum number of
steps taken on any instance of size n
• Best Case Complexity:
– the function defined by the minimum number of
steps taken on any instance of size n
• Average Case Complexity:
– the function defined by the average number of steps
taken on any instance of size n
Adapted from http://www.cs.sunysb.edu/~algorith/lectures-good/node1.html
33
Practice Pseudo-code
• Recipe for Strawberry Rhubarb Pie ( or chose
your favorite dish).
• Define Pseudo-code at different levels of
description
34