Computer Software & Software
Development
H&K Chapter 1
Instructor – Gokcen Cilingir
Cpt S 121 (June 20, 2011)
Washington State University
Problem Solving

Problem solving is the process of transforming the
description of a problem into the solution of that
problem.

We are, as human machines, are problem solving
agents. We have receptors to perceive our
environment, we detect problems, design problemsolving strategies and tools, apply our solutions and get
output.

Steps involved in any problem solving process:
◦ Get the input
◦ Calculate/Create/Perform what is needed to solve the
problem
◦ Output the result
In this class…

We’re going to learn how to translate
solution strategies to given problems into
C programs.

For given problems, we’re going to
design sets of instructions that can be
executed by a computer, which provides
general solutions.

Algorithm: A sequence of instructions
that solve a problem
Greatest common divisor
Problem: Find the largest positive integer
that divides the given two positive integers
evenly (i.e., the greatest common
divisor(GCD) ).

Solve a problem instance → math

Solve the general problem, i.e. describe the
procedure to calculate GCD of any two
numbers → algorithm design
Euclid’s Algorithm
Problem: Find the largest positive integer that
divides the given two positive integers
evenly(i.e., the greatest common divisor).
Algorithm:
1. Assign M and N the values of the larger and
smaller of the two positive integers,
respectively.
2. Divide M by N and call the remainder R.
3. If R is not 0, then assign M the value of N,
assign N the value of R, and return to Step 2.
Otherwise, the greatest common divisor is the
value currently assigned to N.
Finding the GCD of 24 and 9
(Specific Solution)
M
24
9
6
N
9
6
3
R
6
3
0
So, GCD of 24 and 9 is 3.
Euclid’s Algorithm (con’t)

Do we need to know the theory that Euclid
used to come up with this algorithm in order
to use it?

Is this the only algorithm that solves the
GCD problem?

What intelligence is required to find the
GCD using this algorithm?

Can you make a machine that only understands
from 1s and 0s follow these instruction? > With
enough layers of encoding and abstraction, sure!
The Idea Behind Algorithms
Once an algorithm behind a task has been
discovered

We don't need to understand the principles.

The task is reduced to following the instructions.

The intelligence is "encoded into the algorithm."
Why bother writing an algorithm?

If we can specify an algorithm, we can
automate the solution

A computing agent (human, robot,
computer) can interpret and carry out the
instructions to solve the problem
Examples of Algorithms

Washing machine instructions

Instructions for baking a dish

Finding the greatest common divisor (GCD)
of two numbers using Euclid’s algorithm
Washing Machine Instructions
Separate clothes into white clothes and
colored clothes.
 For white clothes:




Set water temperature knob to HOT.
Place white laundry in tub.
For colored clothes:


Set water temperature knob to COLD.
Place colored laundry in tub.
Add 1 cup of powdered laundry detergent to
tub.
 Close lid and press the start button.

Observations About the Washing
Machine Instructions

There are a finite number of well-ordered steps.

Each of the instructions are executable: we are
capable of doing each of them.

At certain level of understanding, each of the
instructions are unambiguous.

When we have followed all of the steps, the washing
machine will wash the clothes and then will stop. So
that we’ll observe the result in finite amount of
time.
Formal Definition of Algorithm
An algorithm is a
A well ordered collection. . .
 Of unambiguous (clear) and effectively
computable operations. . .
 That produces a result. . .
 And halts in a finite amount of time.

Algorithm Representation

Syntax and Semantics

Syntax refers to the representation itself.

Semantics refers to the concept represented
(i.e., the logic).

In the English language, we have both
syntax and semantics.

Syntax is the grammar of the language,
semantics is the meaning.

Same applies to all languages.
How are Algorithms Put
Together?

Sequential instructions


Conditional instructions


do them in the order given
do them if a condition is true
Iterative instructions

do them while a condition is true
C. Hundhausen, A. O’Fallon
Sequential instructions

A series of steps or statements that are
executed in the order they are written.

Example:
Display “Enter two numbers: “
Get number1
Get number2
sum = number1 + number2
Display “sum = “, sum
Conditional instructions

Defines one or more courses of action
depending on the evaluation of a condition.

Synonyms: selection, branching,
decision

Examples:
If (condition is true)
do this
If (condition is true)
do this
Else
do that
Iterative instructions
Allows one or more statements to be
repeated as long as a given condition is
true.
 Synonyms: looping, repetition
 Example:
While (condition is true)
do this


Notice the repetition structure in Euclid’s
Algorithm
Can Algorithms Solve All
Problems?

Some problems are unsolvable


Some problems have no tractable solution, meaning
no solution can be found in a reasonable amount of
time


No algorithmic solution exists
“Brute-force” algorithms
We simply don’t know an algorithm that will solve
some problems

Many “artificial intelligence” problems rely on heuristic
search
C. Hundhausen, A. O’Fallon
Formal Definition of Computer
Science

Computer science is the study of algorithms
including
their formal and mathematical properties
 their hardware realizations
 their linguistic realizations
 their applications

It spans theory and practice
 It requires thinking in abstract and concrete
terms

C. Hundhausen, A. O’Fallon
High-Level Programming
Languages (1)

High-level programming languages

The continuum of languages:
Low-level languages were created from the
perspective of the machine
 High-level languages, in contrast, are
geared toward human programmers

C. Hundhausen, A. O’Fallon
High-Level Programming
Languages (2)

Problem: Computers can’t understand
high-level programming languages

Solution: They must be translated


Programmer uses a text editor to write a text-based
source file in a programming language
Compiler translates source file


Checks to make sure that program is syntactically correct
If so, the compiler translates the program into an object file
with machine language instructions
C. Hundhausen, A. O’Fallon
22
High-Level Programming
Languages (3)

Object file translated by compiler will not
execute!

High-level programs often make use of software
libraries containing predefined pieces of code,
including

Math functions

Input/output functions
In order to execute, object file must be linked to object
files containing these predefined pieces of code
 A Linker program performs this operation
 A Loader program loads the linked program into
memory so that it can be executed

C. Hundhausen, A. O’Fallon
23
Figure 1.11 of H&K: Entering,
Translating, and Running
a High-Level Language Program
High-Level Programming
Languages (4)

Executing Programs

In this class, programs will execute in a textbased window called a console

Input data can be entered at command-line
prompts

Output results will be displayed in the console
window

In the real world, most programs have a graphical
user interface

GUI programming is, however, beyond the scope
of this course
C. Hundhausen, A. O’Fallon
25
High-Level Programming
Languages (5)

Integrated Development Environments (IDE)

Combine compiler, linker, and loader with a source
code editor

Insulate programmers from the details of compiling,
linking, and loading

Provide a variety of tools to assist programmers, for
example,

Source code syntax highlighting

Auto-completion lists ("Intellisense")

A debugger, which allows a programmer to step through
programs, one instruction at a time
C. Hundhausen, A. O’Fallon
26
References

J.R. Hanly & E.B. Koffman, Problem
Solving and Program Design in C (6th Ed.),
Addison-Wesley, 2010

http://www.cs.umbc.edu/courses/104/fall05/
ordonez/powerpoint/

http://www.eecs.wsu.edu/~aofallon/cpts121/
Descargar

Slide 1