Chapter 1: An Introduction to Computer Science
Invitation to Computer Science, Java Version, Third Edition
Objectives
In chapter 1, you will learn about One definition of computer science The concept of algorithms Organization of the reference book (for your information only)
Invitation to Computer Science, Java Version, Third Edition
Introduction
Common misconceptions about computer science
Computer science is the study of computers Computer science is the study of the uses and applications of computers and software Computer science is the study of how to write computer programs
Invitation to Computer Science, Java Version, Third Edition
The Definition of Computer Science
Gibbs and Tucker definition of computer science
The study of algorithms
Formal and mathematical properties Hardware realizations Linguistic realizations Applications
Invitation to Computer Science, Java Version, Third Edition 4
The Definition of Computer Science (continued)
Algorithm
Dictionary definition
Procedure for solving a mathematical problem in a finite number of steps that frequently involves repetition of an operation A step-by-step method for accomplishing a task
Informal description
An ordered sequence of instructions that is guaranteed to solve a specific problem
Invitation to Computer Science, Java Version, Third Edition 5
The Definition of Computer Science (continued)
An algorithm is a list that looks like
STEP 1: Do something. STEP 2: Do something. STEP 3: Do something. . . . . . . STEP N: Stop. You are finished.
Invitation to Computer Science, Java Version, Third Edition 6
The Definition of Computer Science (continued)
Computer scientist designs and develops algorithms to solve problems Operations involved in designing algorithms
Formal and mathematical properties
Studying the behavior of algorithms to determine whether they are correct and efficient
Hardware realizations
Designing and building computer systems that are able to execute algorithms
Invitation to Computer Science, Java Version, Third Edition 7
The Definition of Computer Science (continued)
Linguistic realizations
Designing programming languages and translating algorithms into these machine languages
Applications
Identifying important problems and designing correct and efficient software packages to solve these problems
Invitation to Computer Science, Java Version, Third Edition 8
The Definition of Computer Science (continued)
Categories of operations used to construct algorithms
Sequential operations
Carry out a single well-defined task; when that task is finished, the algorithm moves on to the next operation Examples: Add 1 cup of butter to the mixture in the bowl Subtract the amount of the check from the current account balance Set the value of x to 1
Invitation to Computer Science, Java Version, Third Edition 9
The Definition of Computer Science (continued)
Conditional operations
Ask a question and then select the next operation to be executed on the basis of the answer to that question Examples
If the mixture is too dry, then add one-half cup of water to the bowl
Invitation to Computer Science, Java Version, Third Edition
10
The Definition of Computer Science (continued)
Conditional operations examples (continued):
If the amount of the check is less than or equal to the current account balance, then cash the check; otherwise, tell the person that the account is overdrawn If x is not equal to 0, then set y equal to 1/x; otherwise, print an error message that says we cannot divide by 0
Invitation to Computer Science, Java Version, Third Edition
11
The Definition of Computer Science (continued)
Iterative operations
Tell us to go back and repeat the execution of a previous block of instructions Examples
Repeat the previous two operations until the mixture has thickened While there are still more checks to be processed, do the following five steps Repeat steps 1, 2, and 3 until the value of y is equal to 11
Invitation to Computer Science, Java Version, Third Edition 12
The Definition of Computer Science (continued)
If we can specify an algorithm to solve a problem
we can automate its solution and let a computing agent to do it
Computing agent
The machine, robot, person, or thing carrying out the steps of the algorithm Does not need to understand the concepts or ideas underlying the solution
Invitation to Computer Science, Java Version, Third Edition
16
The Formal Definition of an Algorithm
Algorithm
A well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time
Invitation to Computer Science, Java Version, Third Edition
17
The Formal Definition of an Algorithm (continued)
Unambiguous, understandable operation
An operation that can be understood and carried out directly by the computing agent without needing to be further simplified or explained
Effectively computable (doable)
Computational process exists that allows computing agent to complete that operation successfully
Invitation to Computer Science, Java Version, Third Edition
18
The Formal Definition of an Algorithm (continued)
The result of the algorithm must be produced after the execution of a finite number of operations
Infinite loop
The algorithm has no provisions to terminate A common error in the design and coding of algorithms
Invitation to Computer Science, Java Version, Third Edition 19
The Importance of Algorithmic Problem Solving
Algorithmic solutions can be
Encoded into some appropriate language Given to a computing agent to execute
The computing agent
Would mechanically follow these instructions and successfully complete the task specified Would not have to understand
Creative processes that went into discovery of solution Principles and concepts that underlie the problem
Invitation to Computer Science, Java Version, Third Edition 20
Example
Algorithm: A well-ordered collection of unambiguous and
effectively computable operations that, when executed, produces a result and halts in a finite amount of time
A valid algorithm for shampooing your hair?
Wet your hair Lather your hair Rinse your hair Repeat
No. The problems are
Repeat what? for how many times?
Invitation to Computer Science, Java Version, Third Edition
21
Example
Two valid algorithms for shampooing your hair
Algorithm 1
Wet your hair Lather your hair Rinse your hair Lather your hair Rinse your hair
Algorithm 2
Wet your hair Repeat the following steps until your hair is clean
Lather your hair Rinse your hair
Invitation to Computer Science, Java Version, Third Edition 22
Organization of the Text
The reference book is divided into six separate sections called levels Each level addresses one aspect of the definition of computer science Computer science/algorithms
Invitation to Computer Science, Java Version, Third Edition
24
10
Figure 1.9 Organization of the Text into a Six-Layer Hierarchy
Invitation to Computer Science, Java Version, Third Edition 27
Summary
Computer science is the study of algorithms 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 If we can specify an algorithm to solve a problem, then we can automate its solution
Invitation to Computer Science, Java Version, Third Edition
28
11