Transcript Review #2

Review 2
Chapters 5,6,7, & 8
Chapter Goals
• Read an ad for a computer and understand the
jargon
• List the components and their function
in a von Neumann machine
• Describe the fetch-decode-execute cycle of the
von Neumann machine
• Describe how computer memory is organized
and accessed
• Name and describe different auxiliary storage
devices (hard drives)
Computer Components
What does all this jargon mean?
• Intel® Core™ 2 Duo (2.66GHz/1066Mhz
FSB/6MB cache)
• 4GB Shared Dual Channel DDR2 at 800 MHz
• 500 GB SATA Hard Drive at 5400RPM
• 15.6” High Definition (1080p) LED Backlit
LCD Display (1366 x 768)
• 8X Slot Load DL DVD+/- RW Drive
• 14.8”W X 1.2”H X10.1” D, 5.6 lbs.
Computer Components
• 512 MB ATI Mobility Radeon Graphics
• 85 WHr Lithium Ion Battery
• (2) USB 2.0, HDMI, 15-Pin VGA, Ethernet 10/100/1000
IEEE 1394 Firewire, Express Card, Audio line-in, line-out,
mic-in
• Microsoft® Windows 7® Professional
• Microsoft® Office Home and Student 2007
• 36-Month subscription to McAfee Security Center Antivirus
Sizes in Perspective
Powers of 10 for time, powers of 2 for storage
Sizes in Perspective
Intel Processor
speed 2.66 GHz
To which do these
apply?
SDRAM
size 4GB
speed 800 MHz
Bigger is better
Faster is better
Smaller is better
500GB SATA at 5400 RPM
Transfer rate 300MB per second
Flat screen dot pitch .28mm
Stored-Program Concept
Instructions
and data both
stored in
memory unit
Memory
Memory
A collection of cells, each with a
unique physical address
Most computers are byteaddressable
Cell at address 11111110
contains 10101010
“Little endian” bit numbering:
Arithmetic/Logic Unit
Performs basic arithmetic operations such
as addition and subtraction
Performs logical operations such as AND,
OR, and NOT
Most modern ALUs have a small amount of
special storage units called registers that
can be accessed faster than main memory
Control Unit
Control unit
The organizing force in the computer
Instruction register (IR)
Contains the instruction that is being executed
Program counter (PC)
Contains the address of the next instruction to be
executed
Central Processing Unit (CPU)
ALU and the control unit called the Central
Processing Unit, or CPU
Flow of Information
Bus
In general: A communication system that transfers data between components
inside a computer or between computers; the medium (wires, optical fiber, etc.)
and the protocols (rules for sharing the medium nicely)
“The” bus: Connects the CPU, main memory, I/O devices, and possibly other
components (e.g. hard disk drive)
The Fetch-Execute Cycle
Fetch the next instruction
Decode the instruction
Get data if needed
Execute the instruction
Why is it called a cycle?
The Fetch-Execute Cycle
RAM and ROM
Random Access Memory (RAM)
Memory in which each location can be accessed
and changed
Read Only Memory (ROM)
Memory in which each location can be accessed
but not changed
RAM is volatile, ROM is not
What does volatile mean?
Magnetic Disks
Seek time
Time for read/write head to be over right track
Latency
Time for sector to be in position
Access time
Can you define it?
Transfer rate
Rate at which data moves from the disk to memory
Chapter 6
Low level programming
Chapter Goals
• List the operations that a computer can perform
• Distinguish between machine language and assembly
language
• Describe the steps in creating and running an assemblylanguage program
• Describe the pseudocode constructs used in expressing
an algorithm
• Use pseudocode to express an algorithm
• Describe two approaches to testing
• Design and implement a test plan for a simple
assembly-language program
17
Computer Operations
Computer
A programmable electronic device that can
store, retrieve, and process data
Data and instructions to manipulate the
data are logically the same and can be
stored in the same place
18
Machine Language
Machine language
The language made up of binary coded
instructions built into the hardware of a particular
computer and used directly by the computer
Why would anyone choose to use machine language?
(Hint: they had no choice. Why?)
19
Machine Language
Characteristics of machine language:
– Every processor type has its own specific set
of machine instructions
– The digital logic of the CPU recognizes the
binary representations of the instructions
– Each machine-language instruction does only
one (typically) very low-level task
20
Instruction Format
Operation code
Specifies which instruction is to be carried out
Register specifier
Specifies which register is to be used (for our
purposes it always specifies the accumulator)
Addressing-mode specifier
Says how to interpret the operand part of the
instruction
21
Assembly Language
Assembly language
A language that uses mnemonic codes to
represent machine-language instructions
Assembler
A program that reads each of the
instructions in mnemonic form and
translates it into the machine-language
equivalent
22
Assembly Process
23
Following an Algorithm
Algorithm for preparing a Hollandaise sauce
IF concerned about cholesterol
Put butter substitute in a pot
ELSE
Put butter in a pot
Turn on burner
Put pot on the burner
WHILE (NOT bubbling)
Leave pot on the burner
Put other ingredients in the blender
Turn on blender
WHILE (more in pot)
Pour contents into lender in slow steam
Turn off blender
24
Testing
Test plan
A document that specifies how many times and with what
data the program must be run in order to thoroughly test it
Code coverage
An approach that designs test cases by looking at
the code
Data coverage
An approach that designs test cases by looking at the
allowable data values
25
Testing
Test plan implementation
Using the test cases outlined in the test plan to
verify that the program outputs the predicted
results
26
Chapter 7
Problem Solving
and Algorithms
Chapter Goals
• Distinguish between a simple type and a composite type
• Describe two composite data-structuring mechanisms
• Recognize a recursive problem and write a recursive
algorithm to solve it
• Distinguish between an unsorted array and a sorted
array
• Apply the binary search algorithm
• Demonstrate an understanding of the algorithms in this
chapter by hand-simulating them with a sequence of
items
28
Algorithms
Algorithm
A set of unambiguous instructions for solving a
problem or subproblem in a finite amount of time
using a finite amount of data
Abstract Step
An algorithmic step containing unspecified details
Concrete Step
An algorithm step in which all details are specified
29
Summary of Methodology
Analyze the Problem
Understand the problem!!
Develop a plan of attack
List the Main Tasks (becomes Main Module)
Restate problem as a list of tasks (modules)
Give each task a name
Write the Remaining Modules
Restate each abstract module as a list of tasks
Give each task a name
Re-sequence and Revise as Necessary
Process ends when all steps (modules) are concrete
30
Composite Data Types
Records
A named heterogeneous collection of items in
which individual items are accessed by name. For
example, we could bundle name, age and hourly
wage items into a record named Employee
Arrays
A named homogeneous collection of items in
which an individual item is accessed by its position
(index) within the collection
31
Composite Data Types
Following algorithm, stores values into the fields of record:
Employee employee
// Declare and Employee variable
Set employee.name to “Frank Jones”
Set employee.age to 32
Set employee.hourlyWage to 27.50
32
Composite Data Types
numbers[0]
numbers[4]
33
An Unsorted Array
data[0]...data[length-1]
is of interest
34
Sequential Search of an Unsorted Array
A sequential search examines each item in turn
and compares it to the one we are searching.
If it matches, we have found the item. If not, we
look at the next item in the array.
We stop either when we have found the item or
when we have looked at all the items and not
found a match
Thus, a loop with two ending conditions
35
Sequential Search Algorithm
Set Position to 0
Set found to FALSE
WHILE (position < length AND NOT found )
IF (numbers [position] equals searchitem)
Set Found to TRUE
ELSE
Set position to position + 1
36
Booleans
Boolean Operators
A Boolean variable is a location in memory that can contain
either true or false
Boolean operator AND returns TRUE if both operands are
true and FALSE otherwise
Boolean operator OR returns TRUE if either operand is true
and FALSE otherwise
Boolean operator NOT returns TRUE if its operand is false
and FALSE if its operand is true
37
Sorted Arrays
The values stored in an array have unique keys of a
type for which the relational operators are defined
Sorting rearranges the elements into either
ascending or descending order within the array
A sorted array is one in which the elements are in
order
38
Sequential Search in a Sorted Array
If items in an array are sorted, we can stop
looking when we pass the place where
the item would be it were present in the
array
Is this better?
39
A Sorted Array
A sorted array of
integers
40
Binary Search
Sequential search
Search begins at the beginning of the list and
continues until the item is found or the entire list
has been searched
Binary search (list must be sorted)
Search begins at the middle and finds the item or
eliminates half of the unexamined items; process
is repeated on the half where the item might be
Say that again…
41
Binary Search
42
Bubble Sort
Bubble Sort uses the same strategy:
Find the next item
Put it into its proper place
But uses a different scheme for finding the next
item
Starting with the last list element, compare
successive pairs of elements, swapping
whenever the bottom element of the pair is
smaller than the one above it
43
Bubble Sort
44
Subprogram Statements
We can give a section of code a name and
use that name as a statement in another
part of the program
When the name is encountered, the
processing in the other part of the program
halts while the named code is executed
Remember?
45
Subprogram Statements
What if the subprogram needs data from the
calling unit?
Parameters
Identifiers listed in parentheses beside the
subprogram declaration; sometimes called formal
parameters
Arguments
Identifiers listed in parentheses on the
subprogram call; sometimes called actual
parameters
46
Subprogram Statements
47
Subprogram Statements
48
Recursion
Recursion
The ability of a subprogram to call itself
Base case
The case to which we have an answer
General case
The case that expresses the solution in terms of a
call to itself with a smaller version of the problem
49
Recursion
For example, the factorial of a number is defined
as the number times the product of all the numbers
between itself and 0:
N! = N * (N  1)!
Base case
Factorial(0) = 1 (0! is 1)
General Case
Factorial(N) = N * Factorial(N-1)
50
Chapter 8
Abstract Data Types
and Subprograms
Chapter Goals
• Distinguish between an array-based
visualization and a linked visualization
• Distinguish between an array and a list
• Distinguish between and a unsorted list and a
sorted list
• Distinguish between the behavior of a stack and
a queue
• Distinguish between the binary tree and a binary
search tree
52
Chapter Goals
• Draw the binary search tree that is built from
inserting a series of items
• Understand the difference between a tree and a
graph
• Explain the concept of subprograms and
parameters and distinguish between value and
reference parameters
53
Logical Implementations
Two logical implementations of containers:
Array-based implementation
Objects in the container are kept in an array
Linked-based implementation
Objects in the container are not kept physically
together, but each item tells you where to go to get
the next one in the structure
54
Stacks
Stack
An abstract data type in which accesses are
made at only one end
– LIFO, which stands for Last In First Out
– The insert is called Push and the delete is
called Pop
55
Stacks
WHILE (more data)
Read value
Push(myStack, value)
WHILE (NOT IsEmpty(myStack))
Pop(myStack, value)
Write value
Can you hand simulate this algorithm?
56
Queues
Queue
An abstract data type in which items are entered at
one end and removed from the other end
– FIFO, for First In First Out
– No standard queue terminology
• Enqueue, Enque, Enq, Enter, and Insert
are used for the insertion operation
• Dequeue, Deque, Deq, Delete, and Remove
are used for the deletion operation.
57
Queues
WHILE (more data)
Read value
Enque(myQueue, value)
WHILE (NOT IsEmpty(myQueue))
Deque(myQueue, value)
Write value
Stacks and Queues
Stack and
queue
visualized as
linked
structures
59
Lists
Think of a list as a container of items
Here are the logical operations that can be applied
to lists
Add item
Remove item
Get next item
more items
60
Put an item into the list
Remove an item from the list
Get (look) at the next item
Are there more items?
Array-Based Implementations
61
Linked Implementations
62
Trees
Structure such as lists, stacks, and queues
are linear in nature; only one relationship is
being modeled
More complex relationships require more
complex structures
Can you name three more complex
relationships?
63
Trees
Binary tree
A linked container with a unique starting
node called the root, in which each node is
capable of having two child nodes, and in
which a unique path (series of nodes) exists
from the root to every other node
64
Trees
Root node
Node with two children
Node with right child
Leaf node
Node with left child
65
What is the unique path
to the node containing
5? 9? 7? …
Binary Search Trees
Binary search tree (BST)
A binary tree (shape property) that has the
(semantic) property that characterizes the
values in a node of a tree:
The value in any node is greater than the
value in any node in its left subtree and less
than the value in any node in its right
subtree
66
Binary Search Tree
Each node
is the root
of a subtree
made up of
its left and
right children
Prove that this
tree is a BST
67
Binary Search Tree
68
Binary Search Tree
Trace the
nodes passed
as you search
for 18, 8, 5,
4, 9, and 15
What is special
about where
you are when
you find null?
69
Subprogram Statements
We can give a section of code a name and
use that name as a statement in another
part of the program
When the name is encountered, the
processing in the other part of the program
halts while the named code is executed
Remember?
70
Subprogram Statements
What if the subprogram needs data from the
calling unit?
Parameters
Identifiers listed in parentheses beside the
subprogram declaration; sometimes called formal
parameters
Arguments
Identifiers listed in parentheses on the
subprogram call; sometimes called actual
parameters
71
Subprogram Statements
Value parameter
A parameter that expects a copy of its
argument to be passed by the calling unit
Reference parameter
A parameter that expects the address of its
argument to be passed by the calling unit
72
Subprogram Statements
Think of arguments as being placed on a message board
73