C6: Algorithms and Programming

Algorithm

A step by step sequence of instructions for carrying out some task.

Programming

Can be viewed as the process of designing and implementing algorithms that a computer can carry out.

• Create an algorithm for accomplishing a given objective

• Translate the steps of the algorithm into a programming language that the computer can understand.

Real World Algorithms

The use of algorithms is not limited to the domain of computing.

• Examples:

  • Recipes for baking cookies

  • Directions to your house

Algorithm Analysis

Determining which algorithm is “better” is not always clear cut.

• It depends upon what features are most important to you.

  • If you want to be sure it works, choose the clearer algorithm.

  • If you care about the time or effort required, need to analyze performance.

Big-Oh Notation

To represent an algorithm’s performance in relation to the size of the problem.

• Executing an O algorithm requires time proportional to the size of problem.

  • Given an O algorithm, doubling the problem size doubles the work.

Sequential search

An algorithm that involves examining each list item in sequential order. until the desired item is found.

• Guarantees you will find them:

  • But it is not very practical for very large databases.

  • Worst case: you may have to look at every entry in the list.

Binary Search

Involves continually cutting the desired search list in half until the item is found.

• Only applicable if list of numbers in increasing order or in words in alphabetical order.

Searching

A common problem in computer science involves storing and maintaining large amounts of data, then searching the data for particular values.

• Data storage and retrieval are key to many industry applications

• Search algorithms are necessary to storing and retrieving data efficiently.

Newton’s Algorithm for Finding the square root of N

1. Start with an initial approximation of 1

2. As long as the approximation isn’t close enough, repeatedly.

Machine Languages

The first programming languages

• Consist of instructions that correspond directly to the hardware operations of a particular machine.

• Instructions are written in binary

Assembly languages

In the early 1950s, evolved from machine languages.

• replaced binary codes with words like ADD, MOVE

  • Easier to remember and debug, but still machine-specific.

Assembler

A separate program translated the assembly instructions into machine language.

High level languages

Introduced in late 1950s

• They allow the programmer to write code closer to the way humans think (as opposed to mimicking hardware operations)

• More natural, plus machine-independent

Interpreter

Can be used to provide a real-time translation

• Hears a phrase, translates, and then immediately speaks the translation

  • Advantage: The translation is immediate

  • Disadvantage: If you want to hear the speech again, must interpret all over again.

    • Ex: A press conference

Translator

Also known as compiler. Translates the entire speech offline.

• Takes a copy of the speech, returns when the entire speech is translated.

  • Advantage: once translated, it can be read over and over very quickly.

  • Disadvantage: Must wait for the entire speech to be translated.

    • Written things.