Transcript PowerPoint

A little hardware; a little
software
CS 139 – 08/29/07
Algorithm Review
In lab yesterday, we built algorithms.
Which was the best algorithm?
Why?
Four characteristics of good algorithms
Precise – no ambiguity
Simple – each step does one discrete thing
Complete – no steps are missing
Correct – leads to the same correct result each
time
Next week
We will work more on making the
language of algorithms more precise.
This session
We want to explore some of the
environment in which we will implement
our algorithms….the computer.
Parts of the computer
Data storage
OS
File Systems
Flow of Information
The parts are connected to one another
by a collection of wires called a bus
Figure 5.2 Data flow through a von Neumann architecture
Stored-Program Concept
Figure 5.1 The von Neumann architecture
The Fetch-Execute Cycle
Fetch the next instruction
Decode the instruction
Get data if needed
Execute the instruction
Memory
Memory is a
collection of
cells, each with a
unique physical
address
Page 122
RAM and ROM
RAM stands for Random Access Memory
Inherent in the idea of being able to access each
location is the ability to change the contents of
each location
ROM stands for Read Only Memory
The contents in locations in ROM cannot be
changed
RAM is volatile, ROM is not
This means that RAM does not retain its bit
configuration when the power is turned off,
but ROM does
Secondary Storage Devices
Because most of main memory is volatile and
limited, it is essential that there be other
types of storage devices where programs and
data can be stored when they are no longer
being processed
Secondary storage devices can be installed
within the computer box at the factory or
added later as needed
Magnetic Disks
A read/write head travels across a spinning
magnetic disk, retrieving or recording data
Figure 5.5
The organization
of a magnetic disk
Compact Disks
A CD drive uses a laser to read
information stored optically on a plastic
disk
CD-ROM is Read-Only Memory
DVD stands for Digital Versatile Disk
Sizes in Perspective
Page 119
File Systems
A file is a named collection of related
data
A file system is the logical view that
an operating system provides so that
users can manage information as a
collection of files
A file system is often organized by
grouping files into directories
Directory Trees
Figure 11.4 A Windows directory tree
Directory Trees
A directory of files can be contained within
another directory
The directory containing another is usually called
the parent directory, and the one inside is called a
subdirectory
A file system is often viewed as a directory
tree
The directory at the highest level is called the
root directory
Figure 11.5 A Unix Directory
Tree
Directory Trees
At any point in time, you can be
thought of as working in a particular
location (that is, a particular
subdirectory)
This subdirectory is referred to as the
current working directory
Path Names
To indicate a particular file using text, we
specify that file’s path, which is the series of
directories through which you must go to find
the file
An absolute path name begins at the root
and specifies each step down the tree until it
reaches the desired file or directory
A relative path name begins from the
current working directory
Path Names
Examples of absolute path
C:\Program Files\MS Office\WinWord.exe
C:\My Documents\letters\applications\vaTech.doc
C:\Windows\System\QuickTime
Suppose the current working directory is
C:\My Documents\letters
Then the following relative path names could
be used
cancelMag.doc
applications\calState.doc
Demo
Text and Binary Files
In a text file the bytes of data are
organized as characters from the ASCII
or Unicode character sets
A binary file requires a specific
interpretation of the bits based on the
information in the file
Text and Binary Files
The terms text file and binary file are
somewhat misleading
They seem to imply that the information in a
text file is not stored as binary data
Ultimately, all information on a computer is
stored as binary digits
These terms refer to how those bits are
formatted: as chunks of 8 or 16 bits,
interpreted as characters, or in some other
special format
File Types
Most files, whether they are in text or binary
format, contain a specific type of information
For example, a file may contain a Java program, a
JPEG image, or an MP3 audio clip
The kind of information contained in a
document is called the file type
Most operating systems recognize a list of specific
file types
File Types
File names are
often separated,
usually by a
period, into two
parts
Main name
File extension
Figure 11.1 Some common file types and their
extensions
The file
extension
indicates the type
of the file
File Protection
In multiuser systems, file protection is
of primary importance
We don’t want one user to be able to
access another user’s files unless the
access is specifically allowed
A file protection mechanism determines
who can use a file and for what general
purpose
File Protection
A file’s protection settings in the Unix
operating system is divided into three
categories
Owner
Group
World
Page 356
Algorithms
Problem Solving
Problem solving is the act of finding a
solution to a perplexing, distressing,
vexing, or unsettled question
Ask Questions...
…to understand the problem
What do I know about the problem?
What is the information that I have to process in
order the find the solution?
What does the solution look like?
What sort of special cases exist?
How will I recognize that I have found
the solution?
Algorithms
An algorithm is set of instructions for
solving a problem or subproblem in a
finite amount of time using a finite
amount
of data
The instructions are unambiguous
Computer Problem-Solving
Figure 6.2 The computer problem-solving process
Figure 6.3: The Interactions
Between Problem-Solving Phases
Following an Algorithm
Preparing a Hollandaise sauce
Figure 6.4
Following an Algorithm (cont.)
Preparing a Hollandaise sauce
Page 150
A Computer Example
Problem
Create an address list that includes each
person’s name, address, telephone
number, and e-mail address
This list should then be printed in
alphabetical order
The names to be included in the list are on
scraps of paper and business cards
A Computer Example
Page 156
A Computer Example
Page 157
A Computer Example
Page 158
A Computer Example
Page 159