Algorithms and Data Structures Notes PDF

Preview

Summary

Supplementary NotesFor Algorithms and Data Structures 1AUTHORCHRISTOPHERKADOWTECHNICALUNIVERSITY OFDENMARK(DTU)CONTENTS 1 Peaks 2 Searching and Sorting 2 Searching 2 Sorting 2 Divide and conquer algorithms 3 Analysis of Algorithms 3 Running time 3 Space of an algorithm 3 Asymptotic notation 3 Experi...

Description

Supplementary Notes For Algorithms and Data Structures 1

A UTHOR

C HRISTOPH ER KADOW

T ECHNICAL U NIVERSITY

OF

DENMARK (DTU)

CONTENTS 1 Peaks

1

2 Searching and Sorting 2.1 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Divide and conquer algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2 2 3

3 Analysis of Algorithms 3.1 Running time . . . . . . . . . . . . . 3.2 Space of an algorithm . . . . . . . . 3.3 Asymptotic notation . . . . . . . . . 3.4 Experimental analysis of algorithms .

. . . .

4 4 4 4 6

4 Introduction to Data Structures 4.1 Linked list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Dynamic arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 8 9

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5 Priority Queues and Heaps 11 5.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6 Introduction to graphs 14 6.1 Depth first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.2 Breadth first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.3 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7 Directed graphs 7.1 Directed Acyclic Graph (DAG) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Implicit graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 16 17 17

8 Union Find

18

9 Minimum Spanning Trees 20 9.1 Prim’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.2 Kruskal’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 10 Shortest path 22 10.1 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.2 Shortest paths on DAGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 11 Hashing

24

11.1 11.2 11.3 11.4 11.5

Dictionaries . . . . . . Hashing with chaining Uniform hashing . . . Hash functions . . . . Linear probing . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

24 24 25 25 26

12 Nearest Neighbor and Binary Search Trees 27 12.1 Binary search trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.2 Tree traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 13 Runtime for algorithms 13.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.2 Hashing and binary search trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3 Asymptotic notation properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30 31 32 33

1 PEAKS Peak Consider a table A. A[i] is a peak if A[i] is as least as large as both of its’ neighbors: • A[i] is a peak if A[i − 1] ≤ A[i] ≥ A[i + 1]. • A[0] is a peak if A[0] ≥ A[1]. • A[n − 1] is a peak if A[n − 1] ≥ A[n − 2]. In this course, we have three algorithms for finding peaks. Peak1 For each entry, check if it is a peak. Return index for first element found which is a peak. This algorithm has run time θ(n) since it is linear (worst case we have to check n elements). We observe that a maximum element of an array is a peak. We therefore only have to look for the maximum elements. FindMax Find maximal entry of an array. Though it will be faster than Peak1, it still has a run time of θ(n), since in worst case, we have to check every element in the array. Now we have a clever idea. If one was to start in the middle of the array, we would know how to find the peak quicker - since if we check the two neighbors to the middle element, we would know that if both were smaller, then the middle element would be a peak, but if one is larger, we know there would be a peak in that direction. This leads us to the last algorithm. Peak3 Consider middle entry A[m] and its’ two neighbors A[m − 1] and A[m + 1]. If A[m] is a peak, return m. Otherwise, continue search recursively in the direction of the larger neighbor (this means take the array from m + 1 to n if A[m + 1] is larger and do the same - same if A[m − 1] is larger, then take the array from 1 to m − 1). Since this algorithms halves the array the whole time, the run time will be θ(log(n)). Thereby much faster than the previous two.

1

2 SEARCHING AND SORTING In this week the goal is to look at searching and sorting. This is, finding algorithms for those two things and see if maybe searching is better, if we have a sorted array to start with. This is very common in algorithms; to determine whether or not an element is in the array, and if so finding the element.

2.1

Searching

Searching is a very simple algorithm. Given some element x, determine if that x is in the array and return the index if so. We have two basic algorithms - one for a random array and one for a sorted array. Linear Search If our array is not sorted and we want to find the element, we will do this with linear search. This is simply going to the array, and if we find the element return the index. This algorithm obviously has a run time of θ(n), since we are going through all n elements. If the array is sorted, we can use binary search, which is an algorithm much like Peak3 in section 1, since it is recursive. Binary Search Check middle entry A[m]. If x = A[m] return m. If A[m] < x continue recursively on the right half, if A[m] > x, continue recursively on the left half. This only works since it is sorted. This algorithm will have, like Peak3, a run time of θ(log(n)).

2.2

Sorting

Sorting is also a very basic algorithm. If we have an array, the sorting algorithm should take this array, sort it, and then return the array in sorted order. Usually when sorted order is mentioned, we see it as non-decreasing order. As with searching, we have two algorithms. One where we sort one array, and one where we merge two arrays together and sort them that way. Insertion Sort Insertion sort is basically going through the element and deciding where we should put them in the order. Start with the unsorted array and proceed left-to-right in rounds. This is, when an array A[0..i − 1] is sorted, then take element i and insert it in the array s. t. A[i] is sorted. Basically: Take the element i, and proceed to see if it is bigger than the largest element in the array A[0..i − 1], if note, move it one left and check again, if it is - insert it. The run time of this algorithm is θ(n2 ). We also have the algorithm Merge Sort. This is a form of recursive sorting, where we each time split the array up in sub-arrays.

2

2

SEARCHING AND SORTING

Merge Sort Goal of this is to merge two sorted arrays into one sorted array. What we do is we scan each array from left-to-right. We then compare the two elements we are currently scanning, inserting the smallest in a new array - then check again, where we now have moved one right in the array where we just took the smallest element from. Doing this for all elements makes sure that the new bigger array is sorted. The run time for this is θ(|A1 | + |A2 |), where A1 and A2 are the two arrays merged. Merge sort can be applied to an unsorted array by splitting the array up in halves until it is split up in n arrays consisting of one element. Then applying merge sort to those until we have sorted the entire array yields a run time of θ(n log(n)), which is way quicker than θ(n2 ).

2.3

Divide and conquer algorithms

A divide and conquer algorithm is basically an algorithm which divides a problem into sub-problems (divide) and then solves the sub-problems recursively (conquer). When we combine all the solutions for the sub-problems we will solve the big problem. Merge sort is an example of a divide and conquer algorithm.

3

3 ANALYSIS OF ALGORITHMS When we analyze algorithms our goal is to ensure correctness and to analyze the running time of the algorithm. Another relevant thing to check is also how much space the algorithm will use - that is, how much data is stored and is it possible to be better (less)? A good way to check the run time is by doing an experimental analysis of it, but it is always possible to also do the theoretical calculations first.

3.1

Running time

The running time of an algorithm is how many steps the algorithm performes on an input size of n. There are a few things counting as steps: • Every time we read or write memory (x := y, A[i], i = i + 1, etc.). • Arithmic or boolean operations (+,−,∗,/,%,&&,||,&,|,∧) • Comparisons (< , > , = , = , = , 6=) • Program flow (if-then-else, while, for, goto, function calls, etc.) When we talk about running time, if nothing else is stated, we will talk about the worst case running time. This is how many operations is needed for the worst case possible. Sometimes we also talk about the best possible or the average running time. Some other variants of running time is also mentioned in this course, but nothing that anyone should delve deeper into. This is ammortized running time, randomized, deterministic and so on.

3.2

Space of an algorithm

The space of an algorithm is essentially the number of memory cells used by the algorithm. For example, a variable and pointers/references are one memory cell and an array of length k is using k memory cells. This is very important in algorithms handling large amounts of data, but nothing this course will talk a lot about.

3.3

Asymptotic notation

Asymptotic notation is a quick and easy way to explain how much time and space an algorithm is using and a fundamental tool for mentioning time and space. The notation is used to bound the

4

3

ANALYSIS OF ALGORITHMS

asymptotic growth of the algorithm, and we are talking about three different types of notation; Ω, O and θ notation to be more exact. In the appendix a list over the run time and space of all the different algorithms in this course will be provided. This is very useful, since we create a lot of algorithms in the assignments in this course based on algorithms we already know. O-notation The definition of the O notation is, that f (n) = O(g (n) if f (n) ≤ cg(n) for some constant c ∈ R and for a large enough n. This means that if we are looking at the running time of the an algorithm, if we can find a function g(n) which will grow larger than the time of the algorithm f (n), we have found that the algorithm runs in O(g(n)) time. Basically, this is an upper bound of the running time of the algorithm. We have to remember O(g(n)) is a set of functions. That is, that we should think about f (n) = O(g(n)) actually is f (n) ∈ O(g(n), and we should therefore always write f (n) = O(n) but O(n) = f (n) does not make sense. Example 5n2 +3n = O(n2 ), since for some large enough n, we know 5n2 +3n ≤ 6n2 . 5n3 6= O(n2 ) since n3 always grows quicker than n2 , no matter what constant is multiplied. Ω-notation Much like the definition of O(n), Ω(n) is defined as f (n) = Ω(g(n)) if f (n) ≥ cg(n) for some constant c ∈ R and for a large enough n. So this is basically the opposite of O-notation, where we need a function to always grow slower than the time of our algorithm does. Notation is as it was with Ω(n). θ-notation The θ notation is the middle of the two we have already seen. It is defined as: f (n) = θ(g(n)) if f (n) = O(g(n)) and f (n) = Ω(g(n)). So basically if the function g(n) only bounds by a constant (so for some constant it is always smaller and for some constant it is always larger for some n), it is defined as θ(g(n)). The following plot shows an illustration of this:

Figure 3.1: Plot showing how it would look if f (n) = θ(g(n)). As one can see, the function g(n) is above f (n) for some constant, but below for some other constant.

5

3

ANALYSIS OF ALGORITHMS

θ-notation is what we will see the most, but O-notation is also very common. Ω is not that useful and not something one would see a lot. Basic properties Here are some basic properties, making it easy to determine the asymptotic notation: • Any polynomial grows proportional to its’ leading term: a0 + a1 n + a2 n2 + · · · ad nd = θ(nd ). • All logarithms are asymptotically the same: log a(n) = θ (logb (n)) = θ (log(n)), for any constants a,b > 0. • All logarithms grows slower than any polynomial log(n) = O(nd ) for any d > 0. • All polynomials grows slower than any exponential: nd = O(r n ) for any d > 0 and r > 1. This will be very useful to remember.

3.4

Experimental analysis of algorithms

There is an easy way to determine the running time of an algorithm by just measuring the time when changing the input. The easiest way is the doubling technique. First, calculate the theoretical run time of the algorithm. For example, let us say the algorithm runs in θ(n2 ) time. Then if we double the input n, how much will it grow? Let us check by inserting 2n in the running time. (2n)2 = 4n2 . As we see, the time will grow with a factor 4 every time we double the input. Now we can relate this to an experimental check. Simply measure the time for some input n, then double it, measure it again - and do that a few times to make sure the sample is big enough. Then simply check by dividing the time for the doubled input with the input not double and see if it is close to 4. If it is, our theoretical calculation of the running time was probably correct. The table of the ratios could look like the following:

Figure 3.2: Table showing the experimental analysis of an algorithm with theoretical running time θ(n2 ), where the time should grow with a factor 4 when input size is doubled. This seems to hold.

6

4 INTRODUCTION TO DATA STRUCTURES In this section a brief introduction is giving about what a data structure is followed by a few simple examples. Data structures are one of the key elements used when programming algorithms, since they make the job much easier, and often the algorithm will also run faster. A data structure is a method for organizing data in a quick and easy way to efficiently do a lot of different things with the data - for example accessing, searching and manipulation. The goal when making a data structure is that it is fast and compact to make the algorithms more efficient. The most simple data structures are stacks and queues. Stack A stack is a dynamic sequence of numbers, where one is only able to pull and put data at the top of the sequence. It is implemented by having an array A and a value top, which is making sure one knows where the top is (index of the top). The stack has three operations: The variable top is initially -1. • Push(x): Add the number x to the top of the array. Implemented by saying A[top + 1] = x and top = top + 1. • Pop(): Remove the top element of the stack. Implement by returning A[top] and top = top−1. • isEmpty(): Check if the stack is empty. This can be done by simply checking if top = −1. The time of all three operations are constant (θ(1)) and it is using θ(n) space, since it is only storing an array and a variable. It is limited by we have to know how big the stack is when we initiate it. Further, we are most of the time storing an array which is bigger that what we need, hence wasting space. Figure 4.1 shows an illustration of how the operations work.

Figure 4.1: Illustration of the operations Push(x) and Pop() in a stack. Queue A queue is also a dynamic sequence, but this works as a queue would. Meaning we can only pull the last element of the queue out, and we can only add elements in the beginning. This is also using an array A to be implemented. Further, it uses to variables, one called head and one called tail. head keeps track of where the queue starts in the array, and tail keeps track of the 7

4

INTRODUCTION TO DATA STRUCTURES

end of the queue. Further we need a counter to count how many elements we have. It has three operations as well: • Enqueue(x): Add x to the queue. Implemented by adding x to A[tail] and the we need to update the variable tail cyclically, which means if tail is at the end of the array, we need to put it at the start. Update count as well. • Dequeue(): Remove the element in the front of the queue. Implement by returning A[head] and again update head cyclically as with tail. Also update the count variable. • isEmpty(): Check if the queue is empty. It should return true if count = 0. As with the stack, all the operations are constant in time and the space is θ(n). It is again limited by we need to know how big the array needs to be for it to be implemented. Further, it is wasting space since we are allocating more space than we are using most of the time. Figure 4.2 shows an illustration of how a queue would look like implemented.

Figure 4.2: This is an illustration of how a queue would work.

4.1

Linked list

Now we will look at a concept called linked list. It is essentially data structures used to maintain a dynamic sequence of elements in linear space. The order of the sequence of the numbers are maintained by so called ’links’, which is pointers, pointing from one element to another. Singly and doubly linked lists A singly linked list are essentially just an array of numbers, where the sequence is maintained by pointers, where the first element points to the second and so on throughout the elements. A doubly linked list is the same, but when it is doubly they also point back again. This means, that when the first element points to the second, the second will also point to the first. This is illustrated in Figure 4.3.

8

4

INTRODUCTION TO DATA STRUCTURES

Figure 4.3: An illustration of the difference between a singly and a doubly linked list. There are three very simple operations on a linked list, but there is another thing to consider; where do we start? A simply way to make sure we know where the array starts is by using a pointer to the starting element, called head. The three operations are as follows: • Se...