Hanzehogeschool Groningen
Algoritme en
datastructuren
Samenvatting
M. Scholten
11-3-2019
,Inhoud
Recursion ......................................................................................................................................................... 2
The big O notation........................................................................................................................................... 3
Sorting ............................................................................................................................................................. 7
Insertion sort ............................................................................................................................................... 7
Bubble sort .................................................................................................................................................. 8
Merge sort ................................................................................................................................................... 9
Quick sort .................................................................................................................................................. 10
Lists, Stacks & Queues ................................................................................................................................... 11
Lists ............................................................................................................................................................ 11
Stack .......................................................................................................................................................... 12
Queues ...................................................................................................................................................... 12
Binary Search Tree ........................................................................................................................................ 12
AVL Trees ....................................................................................................................................................... 13
Hashing .......................................................................................................................................................... 16
Set.............................................................................................................................................................. 16
Map ........................................................................................................................................................... 16
Hashing ...................................................................................................................................................... 17
Graphs ........................................................................................................................................................... 18
Basics ......................................................................................................................................................... 18
Graph Traversals........................................................................................................................................ 19
Backtracking .................................................................................................................................................. 20
Dynamic Programming .................................................................................................................................. 21
Dijkstra’s Algorithm ....................................................................................................................................... 22
A* Algorithm ................................................................................................................................................. 23
Prim’s Algorithm............................................................................................................................................ 24
Practice Exam ................................................................................................................................................ 25
1
,Recursion
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances
of the same problem. So, the tactic is to divide a problem into subproblems of the same type as the
original, solve all the subproblems and combine the results. Recursion is essentially repetition without a
loop.
All recursive methods have the following characteristics:
- One or more base cases are used to stop recursion (a base case is the simplest case)
- Every recursive call reduces the original problem, bringing it increasingly closer to a base case
until it becomes that case.
Let’s consider a simple problem of printing a message for n times. You can break the problem into two
subproblems: one is to print the message one time and the other is to print the message for n-1 times.
The second problem is the same as the original problem with a smaller size. The base case for the
problem is n==0. You can solve this problem using recursion as follows:
nPrintln(“Welcome”, 5);
public static void nPrintln(String message, int times) {
if (times >= 1) {
System.out.println(message);
nPrintln(message, times - 1);
} // The base case is times == 0
}
Recursion bears substantial overhead. Each time the program calls a method, the system must assign
space for all the method’s local variables and parameters. This can consume considerable memory and
requires extra time to manage the additional space.
Recursion is good for solving the problems that are inherently recursive
2
, The big O notation
Most algorithms transform input object into output object where the running time typically grows with
the input size. The average case time is difficult to determine, so we focus on the worst-case running
time. The worst-case running time is easier to analyze and is crucial to applications such as games, finance
and robotics
Experimental studies:
- Write a program implementing the algorithm
- Run the program with inputs of varying size and composition
- Use a method like System.currentTimeMillis() to get an accurate measure of the actual running
time
- Plot the results
Limitations of Experiments
- It is necessary to implement the algorithm, which may be difficult
- Results may not be indicative of the running time on other inputs which are not included in the
experiment
- To compare two algorithms, the same hardware and software environments must be used
Theoretical Analysis
- Uses a high-level description of the algorithm instead of an implementation (pseudo code)
- Characterizes running time as a function of the input size, n.
- Considers all possible inputs
- Allows us to evaluate the speed of an algorithm independent of the hardware/software
Pseudocode
- High-level description of an algorithm
- More structured than English prose, but less detailed than a program
- Preferred notation for describing algorithms
- Hides program design issues
- Example: find max element of an array:
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax A[0]
for i 1 to n − 1 do
if A[i] currentMax then
currentMax A[i]
return currentMax
3
Algoritme en
datastructuren
Samenvatting
M. Scholten
11-3-2019
,Inhoud
Recursion ......................................................................................................................................................... 2
The big O notation........................................................................................................................................... 3
Sorting ............................................................................................................................................................. 7
Insertion sort ............................................................................................................................................... 7
Bubble sort .................................................................................................................................................. 8
Merge sort ................................................................................................................................................... 9
Quick sort .................................................................................................................................................. 10
Lists, Stacks & Queues ................................................................................................................................... 11
Lists ............................................................................................................................................................ 11
Stack .......................................................................................................................................................... 12
Queues ...................................................................................................................................................... 12
Binary Search Tree ........................................................................................................................................ 12
AVL Trees ....................................................................................................................................................... 13
Hashing .......................................................................................................................................................... 16
Set.............................................................................................................................................................. 16
Map ........................................................................................................................................................... 16
Hashing ...................................................................................................................................................... 17
Graphs ........................................................................................................................................................... 18
Basics ......................................................................................................................................................... 18
Graph Traversals........................................................................................................................................ 19
Backtracking .................................................................................................................................................. 20
Dynamic Programming .................................................................................................................................. 21
Dijkstra’s Algorithm ....................................................................................................................................... 22
A* Algorithm ................................................................................................................................................. 23
Prim’s Algorithm............................................................................................................................................ 24
Practice Exam ................................................................................................................................................ 25
1
,Recursion
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances
of the same problem. So, the tactic is to divide a problem into subproblems of the same type as the
original, solve all the subproblems and combine the results. Recursion is essentially repetition without a
loop.
All recursive methods have the following characteristics:
- One or more base cases are used to stop recursion (a base case is the simplest case)
- Every recursive call reduces the original problem, bringing it increasingly closer to a base case
until it becomes that case.
Let’s consider a simple problem of printing a message for n times. You can break the problem into two
subproblems: one is to print the message one time and the other is to print the message for n-1 times.
The second problem is the same as the original problem with a smaller size. The base case for the
problem is n==0. You can solve this problem using recursion as follows:
nPrintln(“Welcome”, 5);
public static void nPrintln(String message, int times) {
if (times >= 1) {
System.out.println(message);
nPrintln(message, times - 1);
} // The base case is times == 0
}
Recursion bears substantial overhead. Each time the program calls a method, the system must assign
space for all the method’s local variables and parameters. This can consume considerable memory and
requires extra time to manage the additional space.
Recursion is good for solving the problems that are inherently recursive
2
, The big O notation
Most algorithms transform input object into output object where the running time typically grows with
the input size. The average case time is difficult to determine, so we focus on the worst-case running
time. The worst-case running time is easier to analyze and is crucial to applications such as games, finance
and robotics
Experimental studies:
- Write a program implementing the algorithm
- Run the program with inputs of varying size and composition
- Use a method like System.currentTimeMillis() to get an accurate measure of the actual running
time
- Plot the results
Limitations of Experiments
- It is necessary to implement the algorithm, which may be difficult
- Results may not be indicative of the running time on other inputs which are not included in the
experiment
- To compare two algorithms, the same hardware and software environments must be used
Theoretical Analysis
- Uses a high-level description of the algorithm instead of an implementation (pseudo code)
- Characterizes running time as a function of the input size, n.
- Considers all possible inputs
- Allows us to evaluate the speed of an algorithm independent of the hardware/software
Pseudocode
- High-level description of an algorithm
- More structured than English prose, but less detailed than a program
- Preferred notation for describing algorithms
- Hides program design issues
- Example: find max element of an array:
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax A[0]
for i 1 to n − 1 do
if A[i] currentMax then
currentMax A[i]
return currentMax
3
