# 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