Data structures Laura de Laat
Chapter 1 – The role of algorithms in computing
1.1 Algorithms
An algorithm is a well-defined computational procedure that takes an input and produces
some output. It is a tool for solving a well-specified computational problem. The instance of a
problem consists of the input needed to compute a solution. An algorithm is correct if it solves the
problem, which means that for every instance, it gives the correct output.
Data structures
A data structure is a way to store and organize data in order to facilitate access and modifications.
Hard problems
NP-complete problems are problems for which no efficient solution is known. However, this doesn’t
mean that there doesn’t exist a solution. If there is one efficient algorithm for one of the NP-complete
problems, there is an efficient algorithm for all NP-complete problems. The traveling-salesman
problem is an example of an NP-complete
1.2 Algorithms as technology
Computed time and space in memory are bounded resource. Therefore, you should use
algorithms that are efficient in terms of time or space.
Page | 1
,Data structures Laura de Laat
Chapter 2 – Getting started
2.1 Insertion sort
Insertion sort solves the sorting problem. The numbers that we want to sort are called the
keys. Insertion sort is an efficient algorithm for sorting a small number of elements. It sorts the input
numbers in place. The corresponding pseudocode is:
An example to show the process is given below.
Loop invariants and the correctness of inserton sort
Loop invariants help us understand why an algorithm is correct. It contains the following three things:
1. Initialization: it is true before the first iteration of the loop.
2. Maintenance: if it’s true before an iteration of the loop, it remains true before the next
iteration.
3. Termination: when the loop terminates, the invariant gives us a useful property that helps
show that the algorithm is correct.
How the properties hold for insertion sort:
1. At j = 2, the subarray A[1 .. j−1] consists of just one element, which is obviously sorted.
2. When the value of A [ j ] is inserted in the right position, the subarray A[1 .. j] consists of the
elements originally in A[1 .. j] but in sorted order. So incrementing j for the next iteration
preserves the loop invariant.
3. At termination, we can substitute n+1 for j , so that we get A[1 ..n ], which consists of the
elements originally in A[1 ..n ], but then sorted. So we can conclude that the entire algorithm
is sorted.
Pseudocode conventons
The following conventions are used:
1. After a loop, the counter’s value is the value that first exceeded the loop bound.
2. The keyword downto refers to a decrement, by refers to a step different than 1.
3. Compound data is organized into objects, which are composed of attributes.
4. We pass parameters to a procedure by value.
Page | 2
,Data structures Laura de Laat
5. Boolean operators are short circuiting; if in x and y x is false, we don’t consider y.
2.2 Analyzing algorithms
Analyzing the algorithm is predicting the resources that the algorithm requires. Computational
time is often of primary concern. Before analysis can start, we need a model of the implementation
technology that we will use. In this book, we assume a generic one-processor, random-access machine
(RAM) model. In RAM, instructions are executed one after another, with no concurrent operations. It
contains instructions that are commonly found in real computers: arithmetic, data movement and
control. The data types in RAM are integer and floating point. An integer is represented by c lg n bits.
Analysis of inserton sort
The time taken by the insertion-sort procedure depends on the input and how nearly sorted they
already are. The input size depends on the problem being studied. The running time is the number of
primitive operations or steps executed. A constant amount is required to execute each line of the
pseudocode, however, the time can be different for different lines. Besides the running time, we can
also compute the best-case and worst-case running time. Our focus will be on the worst-case running
time. In some cases we will look at the average-case running time, for which you look at an average
input sequence.
For insertion sort, we can find a best-case running time of an+ b, which represents a linear
function. The worst-case running time is a n 2+ bn+ c , which represents a quadratic function.
Order of growth
For the order of growth, we only consider the leading term of a formula, since the lower-order terms
are relatively insignificant for large values of n. We also ignore it’s coefficient. The order of growth
of insertion sort’s worst-case running time is Θ(n 2).
2.3 Designing algorithms
The insertion-sort algorithm was based on an incremental approach. We now consider a
divide-and-conquer approach.
2.3.1 The divide-and-conquer approach
Recursive functions, in which an algorithm calls itself to solve a problem, follow a divide-and-
conquer approach. It involves three steps:
1. Divide the problem into a number of
subproblems that are smaller instances of the
same problem.
2. Conquer the subproblems by solving them
recursively or if they are small enough just solve
the subproblems.
3. Combine the solutions to the subproblems into
the solution for the original problem.
The merge sort algorithm is a good example of the
divide-and-conquer approach, which takes Θ(n) time.
One of the steps is the merge algorithm, which is given
on the right. The prove of its correctness can be found in
the book, page 32-33.
Page | 3
, Data structures Laura de Laat
This merge procedure can be used in the merge-sort algorithm, which is given below.
2.3.2 Analyzing divide-and-conquer algorithms
When an algorithm contains a recursive call, we can describe its running time by a recurrence
equation, which describes the overall running time on a problem of size n in terms of the running time
on smaller inputs. If the problem size is small enough, the solution takes constant time, written as
Θ(1). Otherwise, the running time is the running time of the three steps added together.
Analysis of merge sort
If we have just one element, T ( n ) takes a constant time. For n>1, we get the following:
1. Divide: takes constant time, so D ( n )=Θ(1).
n
2. Conquer: recursively solving two problems of size n /2, so the running time is 2 T ( ).
2
3. Combine: as with the merge procedure, C ( n )=Θ(n).
Combining this gives us the following function for T ( n ):
{
Θ ( 1 ) ,∧n=1
T ( n )=f ( x )=
2T ()n
2
,∧n>1
We get that every step costs cn time and we have lg ( n )+ 1 steps, so this results in cn lg ( n ) +cn and
Θ(n lg ( n )).
Page | 4
Chapter 1 – The role of algorithms in computing
1.1 Algorithms
An algorithm is a well-defined computational procedure that takes an input and produces
some output. It is a tool for solving a well-specified computational problem. The instance of a
problem consists of the input needed to compute a solution. An algorithm is correct if it solves the
problem, which means that for every instance, it gives the correct output.
Data structures
A data structure is a way to store and organize data in order to facilitate access and modifications.
Hard problems
NP-complete problems are problems for which no efficient solution is known. However, this doesn’t
mean that there doesn’t exist a solution. If there is one efficient algorithm for one of the NP-complete
problems, there is an efficient algorithm for all NP-complete problems. The traveling-salesman
problem is an example of an NP-complete
1.2 Algorithms as technology
Computed time and space in memory are bounded resource. Therefore, you should use
algorithms that are efficient in terms of time or space.
Page | 1
,Data structures Laura de Laat
Chapter 2 – Getting started
2.1 Insertion sort
Insertion sort solves the sorting problem. The numbers that we want to sort are called the
keys. Insertion sort is an efficient algorithm for sorting a small number of elements. It sorts the input
numbers in place. The corresponding pseudocode is:
An example to show the process is given below.
Loop invariants and the correctness of inserton sort
Loop invariants help us understand why an algorithm is correct. It contains the following three things:
1. Initialization: it is true before the first iteration of the loop.
2. Maintenance: if it’s true before an iteration of the loop, it remains true before the next
iteration.
3. Termination: when the loop terminates, the invariant gives us a useful property that helps
show that the algorithm is correct.
How the properties hold for insertion sort:
1. At j = 2, the subarray A[1 .. j−1] consists of just one element, which is obviously sorted.
2. When the value of A [ j ] is inserted in the right position, the subarray A[1 .. j] consists of the
elements originally in A[1 .. j] but in sorted order. So incrementing j for the next iteration
preserves the loop invariant.
3. At termination, we can substitute n+1 for j , so that we get A[1 ..n ], which consists of the
elements originally in A[1 ..n ], but then sorted. So we can conclude that the entire algorithm
is sorted.
Pseudocode conventons
The following conventions are used:
1. After a loop, the counter’s value is the value that first exceeded the loop bound.
2. The keyword downto refers to a decrement, by refers to a step different than 1.
3. Compound data is organized into objects, which are composed of attributes.
4. We pass parameters to a procedure by value.
Page | 2
,Data structures Laura de Laat
5. Boolean operators are short circuiting; if in x and y x is false, we don’t consider y.
2.2 Analyzing algorithms
Analyzing the algorithm is predicting the resources that the algorithm requires. Computational
time is often of primary concern. Before analysis can start, we need a model of the implementation
technology that we will use. In this book, we assume a generic one-processor, random-access machine
(RAM) model. In RAM, instructions are executed one after another, with no concurrent operations. It
contains instructions that are commonly found in real computers: arithmetic, data movement and
control. The data types in RAM are integer and floating point. An integer is represented by c lg n bits.
Analysis of inserton sort
The time taken by the insertion-sort procedure depends on the input and how nearly sorted they
already are. The input size depends on the problem being studied. The running time is the number of
primitive operations or steps executed. A constant amount is required to execute each line of the
pseudocode, however, the time can be different for different lines. Besides the running time, we can
also compute the best-case and worst-case running time. Our focus will be on the worst-case running
time. In some cases we will look at the average-case running time, for which you look at an average
input sequence.
For insertion sort, we can find a best-case running time of an+ b, which represents a linear
function. The worst-case running time is a n 2+ bn+ c , which represents a quadratic function.
Order of growth
For the order of growth, we only consider the leading term of a formula, since the lower-order terms
are relatively insignificant for large values of n. We also ignore it’s coefficient. The order of growth
of insertion sort’s worst-case running time is Θ(n 2).
2.3 Designing algorithms
The insertion-sort algorithm was based on an incremental approach. We now consider a
divide-and-conquer approach.
2.3.1 The divide-and-conquer approach
Recursive functions, in which an algorithm calls itself to solve a problem, follow a divide-and-
conquer approach. It involves three steps:
1. Divide the problem into a number of
subproblems that are smaller instances of the
same problem.
2. Conquer the subproblems by solving them
recursively or if they are small enough just solve
the subproblems.
3. Combine the solutions to the subproblems into
the solution for the original problem.
The merge sort algorithm is a good example of the
divide-and-conquer approach, which takes Θ(n) time.
One of the steps is the merge algorithm, which is given
on the right. The prove of its correctness can be found in
the book, page 32-33.
Page | 3
, Data structures Laura de Laat
This merge procedure can be used in the merge-sort algorithm, which is given below.
2.3.2 Analyzing divide-and-conquer algorithms
When an algorithm contains a recursive call, we can describe its running time by a recurrence
equation, which describes the overall running time on a problem of size n in terms of the running time
on smaller inputs. If the problem size is small enough, the solution takes constant time, written as
Θ(1). Otherwise, the running time is the running time of the three steps added together.
Analysis of merge sort
If we have just one element, T ( n ) takes a constant time. For n>1, we get the following:
1. Divide: takes constant time, so D ( n )=Θ(1).
n
2. Conquer: recursively solving two problems of size n /2, so the running time is 2 T ( ).
2
3. Combine: as with the merge procedure, C ( n )=Θ(n).
Combining this gives us the following function for T ( n ):
{
Θ ( 1 ) ,∧n=1
T ( n )=f ( x )=
2T ()n
2
,∧n>1
We get that every step costs cn time and we have lg ( n )+ 1 steps, so this results in cn lg ( n ) +cn and
Θ(n lg ( n )).
Page | 4
