CPSC 171 Introduction to
Computer Science
Lecture: MWF 1:15pm-2:35pm, Colton 103
Lab 1: TH 9:40am-11:40am, Colton 106
Lab2: TH 2pm-4pm, Colton 106
Course Description
The introduction to the computer science
discipline which establishes a scientific
foundation for a variety of topics,
including computer programming,
computer design, information
processing, the algorithmic solution of
problems, and the study of the
algorithmic process itself. Prerequisites:
Computer Science 172 or 170 (corequisite) or permission.
Instructor & TAs
Louis Oliphant
Office: 111 Colton
Office Hours:
MWF 2:35pm-4:35pm
TH 4pm-5pm
Open Door Policy
Email:
[email protected]
Stefan Maurer
[email protected]
Christian Ebinger
[email protected]
Matt Young
[email protected]
Dan Gavazzi
[email protected]
Cody Depew
[email protected]
Textbook
Invitation to Computer
Science: Java Version
(Paperback)
Third Edition
G. Michael Schneider &
Judith L. Gersting
Reading Assignment
Chapter 1 in Textbook
Homework Assignment
page 34 of Textbook
Problems 5,7,8,9,13
Due Sept 4 at beginning of class
Lab Book
Invitation to Computer
Science Lab Manual:
C++ and
Java(Paperback)
Kenneth Lambert &
Thomas Whaley
Be sure you do NOT buy a manual
with any handwriting in it. In the first
lab session, your manual will be
checked for writing. You must have
the original copy of the disk in the
manual for the labs as this will meet
licensing agreements.
Grading
Lab Portion 30%
One lab report each
week
Lab reports due one
week after assigned
late labs lose 10% per
day.
Late lab reports may
only be handed in up
to 3 days late.
Lecture Portion 70%
1st Midterm 20%
2nd Midterm 20%
Final Exam 20%
Assignments 10%
To pass the course you must pass each part independently
Academic Integrity
All examinations and labs must be done
individually. Cheating or plagiarizing will
result in a zero. You are encouraged to
work together on homework
assignments. Please discuss problems in
a general manner to understand
concepts and ideas. Do not copy or
allow others to copy your work.
Class Web Site
www.cs.hiram.edu/~oliphantLT/cpsc171
Who Are You?
Name (and how to pronounce it)
What you would like to be called
Year in College
Major (declared or considering)
Reason for taking course


Fullfils some requirement (which one?)
Considering computer science
What is Biology?
Computer Science?
Astronomy?
The branch
scienceof
that
physics
studies
that
living
studies
organisms
celestial bodies and the universe as a
whole
www.wordnetweb.princeton.edu
Computer Science is NOT
Computer science is NOT the study of
computers.
Computer science is NOT the study of how to
write computer programs.
Computer science is NOT the study of the uses
and applications of computers and software
Computer Science is
Computer science: The study of
algorithms, including




Their
Their
Their
Their
formal and mathematical properties
hardware realizations
linguistic realizations
applications
Textbook definition
An Algorithm is
A well-ordered collection of
Unambiguous and
Effectively computable operations that,
when executed
Produces a result and
Halts in a finite amount of time
Textbook definition
A VERY SIMPLE ALGORITHM
1.
2.
3.
4.
Wet your hair.
Lather your hair.
Rinse your hair.
Stop.
Observe:
Operations need not be
executed by a computer only
by an entity capable of
carrying out the operations
listed.
We assume that
The algorithm begins executing at the top of the
list of operations.
The "Stop" can be omitted if we assume the last
line is an implied "Stop" operation.
Well-Ordered Collection of Operations
The question that must be answered is:
At any point in the execution of the algorithm, do you
know what operation is to be performed next?
Well-ordered operations:
1. Wet your hair.
Not well-ordered
operations:
2. Lather your hair.
1. Either wet your hair or
lather your hair.
3. Rinse your hair.
2. Rinse your hair.
Well-Ordered Collection of Operations
Don't assume that you can't make choices:
Well-ordered operations:
1. If your hair is dirty, then
a. Wet your hair.
b. Lather your hair.
c. Rinse your hair.
2. Else
a. Go to bed.
Well-ordered operations:
If your hair is dirty, then
Wet your hair.
Lather your hair.
Rinse your hair.
Else
Go to bed.
Note: We will often omit the numbers and the letters
and assume a "top-down" reading of the operations.
Unambiguous Operations
The question that must be answered is:
Does the computing entity understand what the
operation is to do?
This implies that the knowledge of the computing
entity must be considered.
For example, is the following ambiguous?
Make the pie crusts.
Unambiguous Operations
To an experienced cook,
Make the pie crusts.
is not ambiguous.
But, a less experienced cook may need:
Take 1 1/3 cups of flour.
Sift the flour.
Mix the sifted flour with 1/2 cup of butter
and 1/4 cup of water to make dough.
Roll the dough into two 9-inch pie crusts.
or even more detail!
Unambiguous Operations
Definition: An operation that is
unambiguous is called a primitive
operation (or just a primitive)
One question we will be exploring in the course is
what are the primitives of a computer.
Note that a given collection of operations may be an
algorithm with respect to one computing agent, but
not with respect to another computing agent!!
Effectively Computable Operations
The question that must be answered is:
Is the computing entity capable of doing the operation?
This assumes that the operation
must first be unambiguous, i.e. the computing agent
understands what is to be done.
Not effectively computable operations:
Write all the fractions between 0 and 1.
Set A to (S/N).
Add 1 to the current value of X.
…Produces a Result
The question that must be answered is:
Can the user of the algorithm observe a result
produced by the algorithm?
The result need not be a number or piece of text
viewed as "an answer".
It could be an alarm, signaling something is wrong.
It could be an approximation to an answer.
It could be an error message.
Halts in a Finite Amount of Time
The question that must be answered is:
Will the computing entity complete the operations in
a finite number of steps and stop?
Do not confuse "not finite" with "very, very large". A
failure to halt usually implies there is an infinite loop
in the collection of operations:
1. Write the number 1 on a piece of paper.
2. Add 1 to the number and write
it on a piece of paper.
3. Repeat 2.
4. Stop.
An Algorithm is
A well-ordered collection of
Unambiguous and
Effectively computable operations that,
when executed
Produces a result and
Halts in a finite amount of time
Note: Although I have tried to give clean cut examples to
illustrate what these new words mean, in some cases, a
collection of operations can fail for more than one reason.
Textbook definition
Computer Science is
Computer science: The study of
algorithms, including




Their
Their
Their
Their
formal and mathematical properties
hardware realizations
linguistic realizations
applications
Textbook definition
Formal and Mathematical
Properties
It is not enough to develop any old
algorithm to solve a problem.
We must worry about some additional
properties of an algorithm:
How efficient is it?
 What kinds of resources must be used to
execute it?
 How does it compare to other algorithms that
solve the same problem.

Hardware Realizations
Algorithms need not execute on machines.
All we really need are computing entities.

Anything that can compute – e.g., a human.
But, ultimately, most of our interest will lie
with algorithms that execute on
computing entities called "computers".
How are these entities constructed?

The emphasis will be on the logical
construction of a computer, not the physical
construction.
Linguistic Realizations
How do we represent algorithms?
We will start with one linguistic
realization, called pseudocode and later
will look at many different realizations in
various programming languages.
Applications
What are some applications of computers
in current use:
Modeling and Simulation
 Information Retrieval
 Numerical Problem Solving
 Telecommunications
 Artificial Intelligence
 Networking
 Graphics

History of Computers
ENIAC – (Electrical
Numerical Integrator And
Calculator), built by Presper
Eckert and John Mauchly at
Moore School of
Engineering, University of
Pennsylvania, 1941-46
Often called the first
computer (that was
electronic, programmable,
general purpose and
digital).
ENIAC
18,000 vacuum tubes and weighed 30 tons
Duration of an average run without some failure
was only a few hours, although it was predicted
to not run at all!
When it ran, the lights in Philadelphia dimmed!
ENIAC Stored a maximum of twenty 10-digit
decimal numbers.
Input: IBM card reader
Output: Punched cards, lights
ENIAC
Programming required rewiring of the machine
Source: http://ftp.arl.army.mil/ftp/historic-computers/
Eniac’s Vacuum Tubes
Photo taken at Computer Science History Museum, San Jose, CA,
by Dr. Robert Walker on VLSI Trip to Silicon Valley.
Vacuum Tubes
A vacuum tube similar
to those used in the
earliest computers.
Stored a single on/off
value called a bit
Source: http://www.cs.virginia.edu/brochure/images/mus_024.jpg
Second Generation Hardware
(1959-1965) - Characteristics
Transistor
Replaced vacuum tube, fast, small, durable, cheap
Magnetic Cores
Replaced magnetic drums, information available instantly
Magnetic Disks
Replaced magnetic tape, data can be accessed directly
9
Third Generation Hardware
(1965-1971)
Integrated Circuits
Replaced circuit boards, smaller, cheaper,
faster, more reliable.
Transistors
Now used for memory construction
Charles Falco/Photo Researchers
Terminal
An input/output device with a keyboard and screen
By 1968 you could buy a 1.3 MHz CPU with half a megabyte
of RAM and 100 megabyte hard drive for a mere US$1.6 million.
10
Smaller and Smaller
Faster and Faster
My Laptop
Great Job Prospects
What field has…
• …the best-rated job, and 5 of the top 10
highest paid, highest growth jobs?
• …shown strong job growth in the face of
outsourcing?
• …a looming severe shortage in college
graduates?
Computer Science!
Great Job Prospects
5 computing jobs are in the top 10 salary jobs from the
Bureau of Labor Statistics’ list of the 30 fastest growing
jobs through 2014. (Morsch, Laura. CareerBuilders.com,
Jan. 27, 2006.)
1. Computer systems software engineer: $81,140
2. Computer applications software engineer: $76,310
6. Computer systems analyst: $67,520
7. Database administrator: $61,950
9. Network systems and data communication analyst:
$61,250
Salaries are given as mean annual salaries over all regions.
Summary
Course Overview
Definitions of Computer Science and
Algorithms
Brief History of Computers
Great Job Prospects
Reading Assignment
Chapter 1 in Textbook
Homework Assignment
page 34 of Textbook
Problems 5,7,8,9,13
Due Sept 4 at beginning of class
Descargar

CPSC 171 Introduction to Computer Science