From Algorithms to Execution

So you have a problem. And you want a computer to solve it and print out the answer on your monitor. How do we go from a problem in your head to an answer on your monitor? The solution requires many steps.

1. Create Problem Description
2. Develop Algorithm (often in Pseudo-code)
3. Write, Debug and Test Software

Problem Formation

A formal description of a problem specifies a set of inputs along with any properties that they might have and a set of outputs with their properties.

The ADDITION problem
Given any two numbers, output the sum of the numbers.

The SORTING problem
Given a sequence of numbers, output a permutation of the sequence so that they are in order from lowest to highest.

The PRIME (decision) problem
Given a number, output YES if the number is prime, otherwise output NO.

Algorithms and Pseudo-code

An algorithm specifies a sequence of instructions that can be used to produce the output using the input.

The MAXIMUM Problem
Given a sequence of numbers, output the largest number in the sequence.

An algorithm for the MAXIMUM Problem is given below.

Set max equal to the first element in the sequence of numbers

Until you reach the end of the sequence
    If the next element is greater than max
        Set max equal that element

Return max

An algorithm written in English, like the one above, is said to be written in pseudo-code. It has elements of actual code (variables, keywords, indentation) but its not actual code.

Although computers can not execute pseudo-code, (they only understand binary code (0’s and 1’s)), we often write algorithms in pseudo-code so as to

  1. Work out some logical bugs before we code.
  2. Be able to explain the algorithm to other humans (now or later).
  3. Create a programming language independent description of a solution to the problem.

Now we need to translate the pseudo-code into programming language code that can be compiled into machine code that the computer can understand.

Programming Languages

The nice thing about pseudo-code is that it is programming language independent. We can implement the algorithm in a variety of programming languages.

Every programming language has a well-defined set of rules that specify how statements in the language are constructed.  These rules form the syntax of the language. The semantics of a statement in a language defines the meaning of the statement.

Now, a computer is actually quite simple.  It’s CPU can only do a handful of different things: arithmetic operations, logical operations, jump to another statement in code, fetch information from memory, and store information to memory.  These things are defined in what is called an instruction set.  What makes computers so powerful is that they do billions of these operations each second.

The most widely used programming languages (e.g. Java, C++, Python) are called imperative languages.  Programs written in these languages essentially specify the machine instructions (remember those handful of things) to execute and the order in which to execute them.

A segment of code written in Java that solves the Maximum Problem is shown below.

/*
 * precondition: assume numbers.length > 0
 */

int maximum(int[] numbers) { 
    int max = numbers[0];
    int length = numbers.length;

    for(int i = 1; i < length; i++) { 
        if (numbers[i] > max) {
            max = numbers[i];
        }
    }

    return max;
}

A programmer writes programs like the one above using an editor. We’ll use the Vim editor in this class. A programmer saves the code that they’ve written in a plain-text file. These files are referred to as source code files.

The Compilation Process

A computer’s CPU does not understand psuedo-code written in English, nor does it understand the plain-text source code written in a programming language. It only understands machine instructions.  A compiler, however, is a program that translates source code to machine code and outputs the machine instructions in file called an executable or binary.

A typical compilation process uses the following programs:

  1. Preprocessor (fetches other source code that ours references)
  2. Compiler (converts plain-text code to assembly code)
  3. Assembler (converts assembly code to machine code)
  4. Linker (links machine code to other platform dependent machine code has already been compiled)

The Java Compilation Process

Typically, for languages like C++, an executable is created for a particular OS and a specific instruction set.   That is why an executable for a 32-bit Windows machine will not run on a 64-bit Mac.  In order to run the same program on the Mac, you’d need to recompile the source code for the Mac.

Java is not typical. Java was designed to be “write once – run everywhere”.

Rather than have developers compile, assemble and link the code to platform dependent libraries, the developers of Java postpone assembling and linking to when the code is actually run.  That is, developers perform the preprocessing and compiler phases using a Java Compiler  to produce what is called byte-code and share the byte-code with users.  The users run the byte-code on a platform-specific Java Runtime Engine (JRE) that performs the assembler and linker phases to produce an executable.

A Modern Computer Model

So what is a computer? Well, modern computers are not very different than the first digital computer. They all have what is called von-Neumann style architecture.

Von-Neumann was a consultant on the Manhattan Project and in 1944 wrote a paper about the design of the EDVAC machine, a design by Eckert, Mauchly’s and others at the University of Pennsylvania.  Unfortunately, the paper did not give the designers credit.

Nonetheless, it was the design of EDVAC, a stored-program computer that has influenced the design of modern computers – and gave von-Neumann notoriety.

A stored-program digital computer keeps its program instructions and data in the same read-write random-access memory (RAM).

Von-Neuman Architecture

Von Neumann Architecture

  • Control Unit contains instruction registers and counter
  • Fetch instructions and data I/O operations share the same bus.
  • The CPU is an integrated circuit that essentially propagates electronic signals according to a clock. At each clock tick, electrical signals are propagated along wires until the circuit reaches the next state. As the computer transfers from state to state, instructions are executed.

What You’ll Learn in this Course

In this course you’ll learn how to take a problem, identify its inputs and outputs, formulate an algorithm, write a computer program in the Java programming language that follows the algorithm, compile it, and test it for correctness.

© 2017, Eric. All rights reserved.