Transcript Jan 7 - SFU Computing Science

Chapter 1
An Overview of Computers and
Programming Languages
Chapter Objectives
Learn about different types of computers
Explore the hardware and software
components of a computer system
Learn about the language of a computer
Learn about the evolution of programming
languages
Examine high-level programming languages
© Janice Regan 2003
Chapter Objectives
Discover what a compiler is and what it does
Examine how a Java program is processed
Learn what an algorithm is and explore
problem-solving techniques
Become aware of structured and objectoriented programming design methodologies
© Janice Regan 2003
Introduction
Computers have greatly effected our daily
lives – helping us complete many tasks
Computer programs (software) are designed
specifically for each task
Software is created with programming
languages
Java is an example of a programming language
© Janice Regan 2003
An Overview of the History of
Computers
1950s: Very large devices available to a select
few
1960s: Large corporations owned computers
1970s: Computers get smaller and cheaper
1990s: Computers get cheaper and faster and
are found in most homes
© Janice Regan 2003
Elements of a Computer System
A computer has 2 components
Hardware
 Software

© Janice Regan 2003
Hardware Components of a
Computer
Central Processing Unit (CPU)
Main Memory
© Janice Regan 2003
Hardware Components of a
Computer
© Janice Regan 2003
Main Memory
Ordered sequence of cells (memory cells)
Directly connected to CPU
All programs must be brought into main
memory before execution
When power is turned off, everything in main
memory is lost
© Janice Regan 2003
Main Memory with 100 Storage
Cells
© Janice Regan 2003
Secondary Storage
Provides permanent storage for information
Examples of secondary storage:
Hard Disks
 Floppy Disks
 ZIP Disks
 CD-ROMs
 Tapes

© Janice Regan 2003
Input Devices
Definition: devices that feed data and
computer programs into computers
Examples:
Keyboard
 Mouse
 Secondary Storage

© Janice Regan 2003
Output Devices
Definition: devices that the computer uses to
display results
Examples:
Printer
 Monitor
 Secondary Storage

© Janice Regan 2003
Software
Software consists of programs written to
perform specific tasks
Two types of programs
System Programs
 Application Programs

© Janice Regan 2003
System Programs
System programs control the computer
The operating system is first to load when you
turn on a computer
© Janice Regan 2003
Operating System (OS)
OS monitors overall activity of the computer
and provides services
Example services:
memory management
 input/output
 activities
 storage management

© Janice Regan 2003
Application Programs
Written using programming languages
Perform a specific task
Run by the OS
Example programs:
Word Processors
 Spreadsheets
 Games

© Janice Regan 2003
Language of a Computer
Machine language: the most basic language of
a computer
A sequence of 0s and 1s
Every computer directly understands its own
machine language
A bit is a binary digit, 0 or 1
A byte is a sequence of eight bits
© Janice Regan 2003
Evolution of Programming
Languages
Early computers programmed in machine
language
Assembly languages were developed to make
programmer’s job easier
In assembly language, an instruction is an
easy-to-remember form called a mnemonic
Assembler: translates assembly language
instructions into machine language
© Janice Regan 2003
Instructions in Assembly and
Machine Language
© Janice Regan 2003
Evolution of Programming
Languages
High-level languages make programming
easier
Closer to spoken languages
Examples:
Basic
 FORTRAN
 COBOL
 C/C++
 Java

© Janice Regan 2003
Evolution of Programming
Languages
 To run a Java program:
1. Java instructions need to be translated into an
intermediate language called bytecode
2. Then the bytecode is interpreted into a particular
machine language
© Janice Regan 2003
Evolution of Programming
Languages
 Compiler: A program that translates a program
written in a high-level language into the
equivalent machine language. (In the case of
Java, this machine language is the bytecode.)
 Java Virtual Machine (JVM) - hypothetical
computer developed to make Java programs
machine independent
© Janice Regan 2003
Processing a Java Program
 Two types of Java programs: applications and applets
 Source program: Written in a high-level language
 Linker: Combines bytecode with other programs provided by
the SDK and creates executable code
 Loader: transfers executable code into main memory
 Interpreter: reads and translates each bytecode instruction
into machine language and then executes it
© Janice Regan 2003
Processing a Java Program
© Janice Regan 2003
Problem-Solving Process
1. State the Problem
2. Analyze the problem: outline solution requirements
and design an algorithm
3. Design an algorithm to solve the problem
4. Implement the algorithm in a programming
language (Java) and verify that the algorithm works
5. Maintain the program: use and modify if the
problem domain changes
© Janice Regan 2003
Problem-Analysis-CodingExecution Cycle
Algorithm: A step-by-step problem-solving
process in which a solution is arrived at in a
finite amount of time
© Janice Regan 2003
Algorithms
Definition of an Algorithm?
What makes a good algorithm?
Example
© Janice Regan 2003
Definition
An algorithm is

Any set of instructions that specifies a series
of steps to correctly solve the problem
There may be many different algorithms
to solve a given problem
Some algorithms may be more efficient
than others
© Janice Regan 2003
Algorithms and Programs
 An algorithm is a finite set of instructions that
explains the required solution step-by-step
 A computer can be instructed to implement many
algorithms with a finite number of steps or
instructions
 A program is a set of computer instructions that
implements an algorithm
© Janice Regan 2003
Why Should I Write Algorithms?
A computer program solves a scientific
programming problem with a computer

a simulation problem, a data analysis
application, a control system, etc.
To write a computer program you need to
know the series of steps your are
implementing to solve your problem, You
need to know your algorithm!
© Janice Regan 2003
Important
 The sequence or order of the steps is usually of
critical importance in writing a correct algorithm
 You must be exact when specifying an algorithm that
is to be translated into a computer program
 What is the difference between A*B+C and
(A*B)+C? Be careful, the computer will do exactly
what you ask, even it is not what you really want it to
do!!
© Janice Regan 2003
Problem Solving Methodology and
Algorithms
 Problem Specification: State the problem clearly
 Analysis: Input, Output, How to go from input to
output
 Design: Develop a step by step method
 Test Plan: How do you test to determine your
algorithm works
 Implementation or coding
 Testing
 Refinement
© Janice Regan 2003
Problem Specification I
Any problem solving process consists
of
Input  Algorithm  Output
Determine what information is
available as input to your algorithm
Determine what information is desired
as output from your algorithm
© Janice Regan 2003
Specification and Analysis
What needs to be done to the input to
determine the output?
Determine a series of steps that will transform
the input data into the output results
 Then enumerate all the special cases that the
must be handled
 If necessary modify or redesign your series of
steps to handle all special cases

© Janice Regan 2003
Verifying Algorithms
You written your algorithm, is it ready to be
translated into a program?



Verify that it gives the desired results.
Verify that all special cases are handled
Verify that the algorithm ends after the outputs are
determined
You have a series of items to verify, you also have
made a good start on determining what tests need
to be included in your test plan.
© Janice Regan 2003
Summary: Writing Algorithms?
 You will succeed in writing algorithms if you





First think about the problem, its input data and
required results (output)
Next determine a series of steps that will transform the
input data into the output results
Then enumerate all the special cases that the must be
handled
If necessary modify or redesign your series of steps so
that all special cases are handled
Verify your algorithm
© Janice Regan 2003
Example: Problem Specification
You are spending the weekend with a group of
friends. Your contribution to making breakfast
is making the coffee. The friend in charge of
grocery shopping has told you the coffee is in
the freezer.
© Janice Regan 2003
Example: Analysis and Design
You see a coffee maker on the kitchen counter
with a box of coffee filters.
You might decide to subdivide the problem of
making the coffee into the following steps
© Janice Regan 2003
Example: Algorithm
1.
2.
3.
4.
5.
6.
Take the coffee out of the freezer
Put the coffee in a filter
Put the filter in the coffee maker
Put water in the coffee maker
Turn on the coffee maker
Put the rest of the coffee back in the freezer
© Janice Regan 2003
Example: refinement I
 You look for the coffee in the freezer and
you find whole coffee beans. You know
that you need ground coffee beans to
make coffee.
 Refinement of step 2
a)
b)
c)
d)
Find the coffee grinder
Put the coffee beans into the grinder
Grind the coffee beans
Put the ground coffee in the filter
© Janice Regan 2003
Example: refinement II
 You need to decide when the coffee is
properly ground
 Refinement of step 2c
c)
Grind the coffee beans
i. Stop grinding
ii. Check to see if the coffee beans are properly
ground
iii. Continue grinding if they are not
iv. Repeat until the coffee is properly ground
© Janice Regan 2003
Example: refinement III
 What if you use the last of the coffee
and have none left to put back in the
freezer?
 Refinement of step 6
6.
If there are any coffee beans left put
them back in the freezer
© Janice Regan 2003
Example: refined algorithm I
1. Take the coffee out of the freezer
2. Put coffee in a filter
a)
b)
c)
d)
Find the coffee grinder
Put the coffee beans into the grinder
Grind the coffee beans
i. Stop grinding
ii. Check to see if the coffee beans are properly
ground
iii. Continue grinding if they are not
iv. Repeat until the coffee is properly ground
Put the ground coffee in the filter
© Janice Regan 2003
Example: refined algorithm II
3.
4.
5.
6.
Put the filter in the coffee maker
Put water in the coffee machine
Turn on the coffee machine
If there are any coffee beans left put the
rest of the coffee back in the freezer
© Janice Regan 2003
Choices
There may be several algorithms to solve a
given problem
Which algorithm is the best?
 How do we chose?

© Janice Regan 2003
Properties of Good Algorithms
 Efficiency
 Simplicity
 Precision
 Effectiveness
 Generality
 Levels of Abstraction
 Correctness
 Finiteness
 Maintainability
© Janice Regan 2003
Class discussion
Algorithm for solving a quadratic equation
© Janice Regan 2003
Problem-Analysis-CodingExecution Cycle
© Janice Regan 2003
Programming Methodologies
Two basic approaches to programming design:
Structured design
 Object-oriented design

© Janice Regan 2003
Structured Design
1. A problem is divided into smaller
subproblems
2. Each subproblem is solved
3. The solutions of all subproblems are then
combined to solve the problem
© Janice Regan 2003
Object-Oriented Design (OOD)
 In OOD, a program is a collection of
interacting objects
 An object consists of data and operations
 Steps in OOD:
1.
2.
3.
Identify objects
Form the basis of the solution
Determine how these objects interact
© Janice Regan 2003
Chapter Summary
 A computer system is made up of hardware and
software components
 Computers understand machine language; it is easiest
for programmers to write in high-level languages
 A compiler translates high-level language into
machine language
 High-level language steps to execute a program: edit,
compile, link, load, and execute
© Janice Regan 2003
Chapter Summary
Algorithm: step-by-step problem-solving
process in which a solution is arrived at in a
finite amount of time
Three steps to problem solving: analyze the
problem and design an algorithm, implement the
algorithm in a programming language, and
maintain the program
Two basic approaches to programming design:
structured and object-oriented
© Janice Regan 2003