Author: Eric

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

• 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.

SSH

From a Windows machine, we can log into a UNIX machine using a program named Putty.  Putty implements the SSH (Secure Shell) protocol that provides encrypted authentication and communication between systems.   After successful authentication, Putty displays a shell prompt to the user.  From that shell program users can execute Linux commands.

To log into a machine using Putty we have to know the name of the remote machine and have an account on the remote machine.

At BC, there is a machine named cs.bridgewater.edu that students have access.  It is closely monitored by IT, so please do not attempt to run any command as root using sudo.

To log into cs.bridgewater.edu, install Putty on your machine and then start the program.  When you see Putty’s main screen (shown below), in the field labeled “Host Name” enter username@cs.bridgewater.edu where username is replaced by your BC username.  Then press ‘Open’.

The first time you attempt to log into cs.bridgewater.edu, you will be asked if you trust the host machine (shown below).  Press ‘Yes’.

Next, you will be asked for your password.  Please enter your BC password and press ‘Enter’.

Once your credentials are verified, you are logged into the remote machine and are shown a bash command prompt (shown below).  From this command prompt you can browse the file system and execute commands. For example, if you type ls after the command prompt and press ‘Enter’, a list of the files in the current directory are displayed on the screen.  We’ll discuss more Linux commands soon.

By pressing the up arrow key we can scroll through the commands that we’ve previously executed.  This comes in handy when we want to execute a command that is long.

SFTP

If we need to transfer files from a Windows machine to cs.bridgewater.edu we can use a program called Filezilla.  Filezilla implements a protocol called Secure File Transfer Protocol (SFTP) which provides an encrypted connection between the local and remote machines.

To transfer a file from one machine to another we first have to log into the remote machine using Filezilla.  To do so, simply start the program, enter cs.bridgewater.edu in the Host field, your BC username in the Username field, your BC password in the Password field, 22 in the Port field (shown below), and press ‘Enter’.

Once your credentials have been verified the files in your home directory on cs.bridgewater.edu will be displayed in panes on the right hand side of the application.  To move a file from one compute to another, simply drag and drop the files.