Data Structures and Algorithms (H) Lecture 1 Notes

Getting Started

Definition: Algorithm

An algorithm is a well-defined computational procedure that takes some input and produces some output.

This means:

• It is a tool for solving a well-specified computational problem. e.g. the sorting problem:
• Input: a sequence of numbers .
• Output: a permutation of the input sequence s.t.

A sequence like is called a instance of the sorting problem. We expect the algorithm to solve all instances of a specific problem.

To define the algorithms precisely, we use a abstract language, pseudocode.

An ideal algorithm should be

• correct
• efficient
• easy to read, cheap to design
• etc.

Definition: Correctness of Algorithm

An algorithm is correct if for every input instance it halts with the corrent output. A correct algorithm solves the problem.

To show the correctness of algorithms, we need to make mathematical reasoning.

Next, to measure the running time of a given algorithm, we need a model that provides a good level of abstraction:

• Gives a good idea about the time an algorithm needs.
• Allows us to compare different algorithms.
• Without getting bogged down with details.

Definition: Random-access Machine Model

A generic random-access machine, where instructions are executed one after another, with no concurrent operations. The elementary operations are:

• Arithmetic operations
• Logical operations, shifts, comparisons
• Data movement: variable assignments
• Control instructions: loops, subroutine/method calls

The RAM model assumes that each elementary operations takes the same amount of time (a constant time).

Then to measure the runtime, we only need to count the number of elementary operations in the RAM model, this is known as the common cost model.

But we often abstract from the constants and concrete operation numbers, and focus on the asymptotic growth of runtime with problem size.

Example: Insertion Sort

insertion-sort

Correctness

To prove the correctness of the above algorithm, we use proof by loop invariants, a popular way of proving correctness of algorithms with loops.

Definition: Loop Invariant

A loop invariant is a statement that is always true and that reflects the progress of the algorithm towards producing a correct output.

• Initialization: the loop invariant is true at initialization.
  • This part is often trivial.
• Maintenance: if the loop invariant is true after iteration, it is also true after iterations.
  • Essentially the same as the proof by induction.
• Termination: when the algorithm terminates, the loop invariant tells that the algorithm is correct.

Applying this to the insertion sort, we get:

• Loop invariant: At the start of each iteration of the for loop of lines 1-9, the subarray consists of the elements originally in , but in sorted order.
• Initialization: For the subarray is the original and it is sorted (trivial).
• Maintenance: The while loop moves one position to the right and inserts at the correct position . Then contains the original , but in sorted order.
• Termination: The for loop ends when . Then the loop invariant says that the array contains the original in sorted order.

Runtime of Insertion Sort (In a naive way)

A naive way of calculating runtime of insertion sort is:

• Assume that line take time to run once (cost).
• Count the number the line has executed.
• Sum up the product of cost and execution time.

Define as the number of times the while loop is executed for that :

Line	Cost	Times
1
2
3
4
5
6
7
8
9

Then the runtime of the algorithm is:

- Best case: the array is already sorted, in that case, :

So it’s linear w.r.t. the input size. - Worse case: the array is inversely ordered, in that case, :

So it’s quadratic w.r.t. the input size