Week 1: Intro to Algos

Question 1

What is an Algorithm?

Answer 1

An algorithm is a set of rules which must be followed when solving a particular problem.

Question 2

What is a computational problem?

Answer 2

A computational problem, is a desired relationship between inputs and outputs.

Question 3

Properties of an Algorithm?

Answer 3

Does it solve the problem?
Is it correct?
How fast is it?
How much memory does it use?
In the best case? The worst case? The average case?
Is it deterministic?
Will it always terminate?

Question 4

What is Pseudocode?

Answer 4

Pseudocode is a way of describing algorithms, with no fixed syntax
It is written in careful English, and it is designed to be abstract
When writing Pseudocode, we assume it is executed in an abstract machine which:
Sequential execution
Constant operations
Infinite memory

Question 5

What is a Data Structure?

Answer 5

A Data structure is a way to store and organise data in order to facilitate access and modifications
A data structure implements an ADT.
Examples: Linked List, Binary Tree, Hash Table

Question 6

What is an Abstract Datatype (ADT)?

Answer 6

An Abstract Datatype (ADT) defines the behaviour of a set of possible operations on data of a certain type
It defines as little as possible about how the ADT will actually be implemented
Example: a list ADT may have the operations append, head, tail etc

Question 7

Properties of a Data Structure?

Answer 7

Similar to an algorithm, data structures have a variety of properties:
Is it correct?
Does it implement the given ADT correctly?
How do operations perform:
In terms of time?
In terms of memory use?
In relation to the size of the DS?
In relation to the layout of the DS?
What are the trade offs:
Between time and memory?
Between different operations?

Question 8

How do we solve a computational problem?

Answer 8

1. Carefully read the whole problem
2. Produce a computational problem description in maths.
3. Define the exact format of inputs and outputs, and any requirements for them
4. Design some test data
5. Design a solution
6. Test and improve the solution

Question 9

How do we test and improve a solution?

Answer 9

Testing involves verifying the algorithm is correct.
For simple algorithms this can be done formally in a maths-like way.
For complex algorithms, the test data may be the only realistic way to show correctness.
Also analyse the complexity of the solution.
This includes both time (speed) and space (memory use).
Check how the these scale as the input size changes.