main

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.
  2. 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.
  3. 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