1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
# COMP 200
# 1.1 Introduction to Computer Science
1. Misconception 1: Computer science is the study of computers
* science is not about tools. it is about how we use them and what we find out when we do.
1. Misconception 2: Computer science is the study of how to write computer programs
* programming is a tool that researchers use to study new ideas and build and test new solutions
1. Misconception 3: Computer science is the study of the uses and applications of computers and software.
* It is a computer scientist who is responsible for specifying, designing,
building and testing software packages as well as the computer systems on
which they run.
# 1.2 The Definition of Computer Science
The central concept of computer science is the `algorithm`.
It is the task of the computer scientist to design and develop algorithms to
solve a range of important problems. This design process includes the following
operations:
* Studying the behaviour of algorithms to determine if they are correct and
efficient (their formal and mathematical properties)
* Designing and building computer systems that are able to execute algorithms
(their hardware realizations)
* Identifying important problems and designing correct and efficient software
packages to solve these problems (their applications)
> algorithm: a procedure for solving a mathematical problem in a finite number
> of steps that frequently involves repetition of an operation; broadly: a
> step-by-step method for accomplishing some task.
An algorithm is an ordered sequence of instructions that is guaranteed to solve
a specific problem. It is a list that looks something like this:
1. Do something
2. Do something
3. Do something
...
N. Stop, you are finished
All operations used to construct algorithms belong to one of only three
categories:
1. Sequential operations: A sequential instruction carries out a single
well-defined task. When that task is finished, the algorithm moves on to the
next operation. Sequential operations are usually expressed as simple
declarative sentences.
* 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.
1. Conditional operations: These are the `question-asking` instructions of an
algorithm. They ask a question, and the next operation is selected on the
basis of the answer to that question.
* if the mixture is too dry, then add one-half cup of water to the bowl.
1. Iterator operations: These are the "looping" instructions of an algorithm.
They tell us not to go on to the next instruction but, instead, to go back
and repeat the execution of a previous block of instructions.
* repeat the previous two operations until the mixture has thickened.
> If we can specify an algorithm to solve a problem, then we can automate its
> solution.
In computer science terminology, the machine, robot, person or thing carrying
out the steps of an algorithm is called a `computing agent`.
Computer science can also be viewed as the science of algorithmic problem
solving.
1.3 Algorithms
1.3.1 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.
An `unambiguous operation` is one that can be understood and carried out
directly by the computing agent without further simplification or explanation.
When an operation is unambiguous, we call it a `primitive operation` or simply a
`primitive`.
An algorithm must be composed entirely of primitives.
> What are the primitive operations of a typical modern computer system?
The formal term for "doable" is `effectively computable`.
# 2.2.3 Conditional and Iterative Operations
* Sequential Algorithm: Executes its instructions in a straight line from top to bottom.
* Control Operations: allow us to alter the normal sequential flow of control in an algorithm.
* Conditional Statements: allow an algorithm to ask a question and select the
next operation to perform on the basis of the answer to that question.
* iteration: looping
* continuation condition: evaluates "true/false condition"
* loop body: block of operations
* infinite loop: if continuation condition is never false
* algorithm discovery: finding a solution to a given problem
* sequential search : start at the beginning of the list and search for the item
by visiting each item in the list until the end. (unsorted data)
* library: collection of useful, prewritten algorithms.
* abstraction: refers to the separation of the high-level view of an entity or
an operation from the low-level details of its implementation.
* top-down design: Viewing an operation at a high level of abstraction and
fleshing out the details of its implementation at a later time constitute an
imporant computer science problem-solving strategy.
# Chapter 3: The Efficiency of Algorithms
|
