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.

SSH and SFTP

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.

Linux and Vi

If you search the web for ‘linux cheat sheet‘ you find numerous one-page documents that list the most commonly used Linux commands.  I recommend that you print or bookmark one to help you learn them.

Navigating the File System

Some of the most common commands that we’ll use are for listing the files within a directory and moving around the file system.

  • ls
  • ls -l
  • ls -al
  • pwd
  • cd /
  • cd $HOME
  • cd ..
  • cd [dir] (absolute or relative path)

UNIX directory structure

Standard-unix-filesystem-hierarchy

Manipulating Directories and Files

  • mkdir [dir]
  • rmdir [dir]
  • mv [src] [dest]
  • touch [file]
  • cp [orig] [new]
  • cp -r [src_dir] [dest_dir]
  • rm [file]
  • rm -r [dir]    (BE CAREFUL!)
  • chmod [mode] [file]

Displaying File, Manual, Environment and System Information

  • cat [file]
  • man [command]
  • which [command]
  • whereis [command]
  • env
  • whoami
  • hostname
  • date
  • clear

Viewing and Killing Processes

  • ps
  • ps -ax
  • kill [pid]
  • kill -9 [pid]

Pipes

  • [command] | [command]
  • cat filename | less

Vi – The Editor of Champions

  • Insert Mode (i)
    • arrow keys
    • delete
  • Command Mode (esc)
    • x – delete char
    • r [char] – replace char
    • dd – delete line
    • # dd – delete multiple lines
    • u – undo last command
    • yy – copy to clipboard
    • # yy – copy multiple lines
    • p – paste contents of clip board
    • $ – go to the end of a line
    • 0 – go to the beginning of a line
    • shift + G – go to the end of the file
    • shift + H – go to the beginning of the file
    • :# – goto line a particular line
    • :/search_term – search for a particular term
    • :%s/old/new/g – find and replace
    • :w – write the file
    • :q – quit vi
    • :q! – quit without writing
    • shift+z+z – write and quit

Kattis

Kattis is an online service that provides students with programming problems to solve and a system to check if their solutions are correct.  Anyone can create an account, pick a problem, write a solution and submit it to see if it is correct.  The service will respond with a judgment usually within 1 minute.

The service is also used by programing contests and by college faculty for their courses.  I’ve created a Kattis course that includes a set of problems for you to solve during this course.

Registration

The first thing you need to do is create a Kattis account.  You can do so at the following URL:  https://bridgewater.kattis.com/register

Next, you need to register as a student in my CSCI-105 Kattis course by going to https://bridgewater.kattis.com/courses/CSCI-105/Fall2016/register  and entering the Registration Key “CSCI-105”.

Problem Sets

You can view the list of problems for the course here: https://bridgewater.kattis.com/courses/CSCI-105/Fall2016/problems.

You will be given a separate handout specifying when each of the problem groups are due. 

Writing a Solution

When you are working on a solution to a Kattis problem, keep the Kattis Java guidelines in mind.  The guidelines can be found here:  https://open.kattis.com/help/java.

Some things to remember are:

  1. Your program should read its input from standard input and produce output on standard output.
  2. Kattis will inspect the exit code of your program. If it is non-zero, she will judge your submission as Run Time Error. So don’t call exit() with a positive number as the argument.  Always return 0.
  3. Uncaught java exceptions will almost always be judged as Run Time Errors with some extra information.