Computer Science 01

Engineers are people who can map problems into computational frameworks.

A good computer scientist is someone who has the skills to make a computer do whatever they want it to do.

Let's start with the question... What is computation? To answer this, we first look at two kinds of knowledge:

1) Declarative - It is composed of statements of facts. It does not tell us how to arrive at a conclusion, but if a piece of declarative knowledge is correct, we can use it to test computations. An example of declarative knowledge is: "A chocolate cake is delicious".

2) Imperative - Imperative knowledge tells how to solve something. For example, a recipe for a chocolate cake is imperative knowledge.

We use the recipe to create a dish (Imperative Knowledge), and if the dish is indeed delicious, looks everything like the description of a chocolate cake (Declarative Knowledge) then we know we've made a chocolate cake.

Let's look at an approximation algorithm that lets us solve a square root. Say for example, we are looking for the value of sqrt(25).

We first get facts about the declarative knowledge we know of squares and their roots. It is as such:

g^2=x

We have x, we need to find g.

The approximation algorithm, a form of imperative knowledge, for obtaining the sqrt(x) is as such:
1) Guess a value g.
2) Compute the value of g^2.
3) If g^2 is x, or close enough to x, then g is the root of x.
4) Else, the next value of g will be (g+x/g)/2 (The average of g and x/g). Compute again from Step 2.

Programmatically, we write it like this:

while(math.pow(g,2)!=x)
{
    g=g+x/g;
}

When you get the value of g which when squared gives you x, it is said that the algorithm has converged.

An algorithm is made up of the following components:
Instructions - Operations that are carried out, e.g. "g=g+x/g"
Flow Control - The way and sequence the instructions are carried out.
Termination Condition - When are we satisfied with the answer, e.g. "g^2 equals x or is close enough to x"

There are two types of programs:

1) Fixed Program Computer - These computers are designed to do specific and fixed things. Instructions are hard-coded into circuitry (think logic gates in ASICs) and only input and output is considered data.

2) Stored Program Computer -The input, instructions and output are all considered data and are all stored alongside in memory. This allows infinite amount of flexiblity and programs can now produce programs. This is the current state of computers.

In the Stored Program Computer, people think of a computer as a Hardware Program, known as an Interpreter.

A basic Stored Program Computer has the following things:
1) Memory - Memory used for storing of data and program.
2) Control Unit - Interprets instructions from memory and turns it into a form that the ALU can understand.
3) Arithmetic Logic Unit - Accepts instructions from Control Unit, pulls and pushes data from Memory, computes and stores results in its Accumulator (the ALU's own Memory).
4) Input/Output - Allows interaction with external systems.

A British mathematician proved that there are 6 primitive instructions that can be used to do anything that can be done with the computer.

In Programming, we make use of a set of Primitive Instructions and a set of Flow Control. Using and combining these two elements, we can come up with different programs.

A Programming Language comprises of:
1) Syntax - Which sequence of characters and symbols constitute a well-formed string, e.g. g=5+6.
2) Static Semantics - Which well-formed strings have a meaning, e.g. 6+4 by itself is well-formed but does not have a proper meaning/purpose.
3) Semantics - What that meaning is. A program can have a proper syntax and proper static semantics, but it may mean differently from what the programmer wants it to do.

A program with improper semantics can:
1) Crash - The program stops running and shows an obvious sign that it's happened. A properly designed program environment will keep damages minimal and local (i.e. does not damage the program or system).
2) Never Stop - The program never finishes the job, which is also known as "Hang". These programs typically have entered an infinite loop due to a deadlock or semantics error.
3) Wrong Output - The program runs to completion, but produces the wrong answer. This is the worst kind of problem because people may think it's running fine and it isn't.

There are two types of Programming Languages:
1) Interpreted - Python, where the source code is executed directly and does not need to be compiled.
2) Compiled - Java, where a compiler changes source code into an object code, which is executed by the Hardware Interpreter.