BICT3101 DATA STRUCTURES AND ALGORITHMS 1 Complexity and Efficiency of Algorithms Data Structure In computer science, a data structure is a data organisation, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. Usage Data structures serve as basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type. Different types of data structures are suited to different applications and some are highly specialised to specific tasks. For example, relational databases commonly use B-tree indexes for data retrieval, while compiler implementations usually use hash tables to look up identifiers. Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms. Some formal design methods and programming languages emphasise data structures, rather than algorithms, as the key organising factor in software design. Data structures can be used to organise the storage and retrieval of information stored in both main memory and secondary memory. Examples An array is a number of elements in a specific order, typically all of the same type. Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or resizable. A linked list is a linear collection of data elements of any type, called nodes, where each node has itself a value, and points to the next node in the linked list. The principal advantage of a linked list over an array is that values can always be efficiently inserted and removed without relocating the rest of the list. Certain other operations, such as random access to a certain element, are however slower on lists than on arrays. A record (also called tuple or struct) is an aggregate data structure. A record is a value that contains other values, typically in fixed number and sequence and typically indexed by names. The elements of records are usually called fields or members. Algorithm An algorithm is a detailed step by step set of instructions for solving a programming problem. An algorithm is meant to be coded into any third generation programming language which is in use. Algorithms can be written in form of pseudocodes. A pseudocode is an algorithm that is expressed in half-English and half-code. In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, and automated reasoning tasks. As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The concept of algorithm has existed for centuries. Greek mathematicians used algorithms in, for example, the sieve of Eratosthenes for finding prime numbers and the Euclidean algorithm for finding the greatest common divisor of two numbers. An informal definition could be "a set of rules that precisely defines a sequence of operations" which would include all computer programs, including programs that do not perform numeric calculations. A program is only an algorithm if it stops eventually. Expressing Algorithms Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, drakon-charts, programming languages or control tables (processed by interpreters). Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode, flowcharts, drakon-charts and control tables are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer but are often used as a way to define or document algorithms. Design Algorithm design refers to a method or mathematical process (plan) for problem-solving and engineering algorithms. The design of algorithms is part of many solution theories of operation research, such as dynamic programming and divide-and-conquer. Techniques for designing and implementing algorithm designs are also called algorithm design patterns, such as the template method pattern and decorator pattern. One of the most important aspects of algorithm design is creating an algorithm that has an efficient run-time, also known as its Big O. Typical steps in the development of algorithms: Problem definition Development of a model Specification of the algorithm Designing an algorithm Checking the correctness of the algorithm Analysis of algorithm Implementation of algorithm Program testing Documentation preparation Algorithm Classification Every field of science has its own problems and needs efficient algorithms. Related problems in one field are often studied together. Some example classes are search algorithms, sorting algorithms, merge algorithms, numerical algorithms, graph algorithms, string algorithms, computational geometric algorithms, combinatorial algorithms, medical algorithms, machine learning, cryptography, data compression algorithms and parsing techniques. Fields tend to overlap with each other and algorithm advances in one field may improve those of other sometimes completely unrelated fields. For example, dynamic programming was invented for optimization of resource consumption in industry but is now used in solving a broad range of problems in many fields. Analysis of Algorithms Analysis of algorithms as used in computer science means analysing algorithms to determine the amount of time required for the algorithm to run on a computer and the amount of memory used in the process. However, time itself is not measured. The number of times a fundamental operation is carried out is analysed instead. Although computers are extremely fast and have extremely large memories most people think a computer can execute any program they give it at most a few seconds. This is not so especially for the large commercial and scientific programs. Therefore the efficiency of an algorithm is very important, so it pays to have some techniques for deciding which of the two or more programs will be most efficient and effective. Running Time Any program will typically take a longer amount of time on larger inputs than it will on smaller inputs. You would expect that a program that sorts numbers would take less time to sort 10 numbers than it would to sort 1,000 numbers. However, the length of time taken is purely dependent on the algorithm. Pseudocode Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a normal programming language but is intended for human reading rather than machine reading. Pseudocode typically omits details that are essential for machine understanding of the algorithm, such as variable declarations, system-specific code and some subroutines. The programming language is augmented with natural language description details, where convenient, or with compact mathematical notation. The purpose of using pseudocode is that it is easier for people to understand than conventional programming language code, and that it is an efficient and environment-independent description of the key principles of an algorithm. It is commonly used in textbooks and scientific publications that are documenting various algorithms, and also in planning of computer program development, for sketching out the structure of the program before the actual coding takes place. No standard for pseudocode syntax exists as a program in pseudocode is not an executable program. Pseudocode resembles but should not be confused with skeleton programs which can be compiled without errors. Flowcharts, drakon-charts and Unified Modeling Language (UML) charts can be thought of as a graphical alternative to pseudocode but are more spacious on paper. Application Textbooks and scientific publications related to computer science and numerical computation often use pseudocode in description of algorithms so that all programmers can understand them even if they do not all know the same programming languages. In textbooks, there is usually an accompanying introduction explaining the particular conventions in use. The level of detail of the pseudocode may in some cases approach that of formalized general-purpose languages. A programmer who needs to implement a specific algorithm, especially an unfamiliar one, will often start with a pseudocode description and then "translate" that description into the target programming language and modify it to interact correctly with the rest of the program. Programmers may also start a project by sketching out the code in pseudocode on paper before writing it in its actual language, as a top-down structuring approach, with a process of steps to be followed as a refinement. Flowchart A flowchart is a type of diagram that represents an algorithm, workflow or process. The flowchart shows the steps as boxes of various kinds, and their order by connecting the boxes with arrows. This diagrammatic representation illustrates a solution model to a given problem. Flowcharts are used in analyzing, designing, documenting or managing a process or program in various fields. Another Explanation: Flowchart Flowcharts are a methodology used to analyse, improve, document and manage a process or program. Flowcharts are helpful for: Aiding understanding of relationships among different process steps Collecting data about a particular process Helping with decision making Measuring the performance of a process Depicting the structure of a process Tracking the process flow Highlighting important steps and eliminating the unnecessary steps 1.X Measurements of Algorithmic Complexity, Time Complexity, Space Complexity Analysis of Algorithms The analysis of algorithms is the determination of the computational complexity of algorithms that is the amount of time, storage and/or other resources necessary to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behaviour, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm. The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms. In theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Big O notation, Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the length of the sorted list being searched, or in O(logn), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. Time Complexity In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor. Time Complexity can also be defined as the function which determines the amount of time an algorithm takes to give the desired output. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a function of the size of the input. Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behaviour of the complexity when the input size increases—that is, the asymptotic behaviour of the complexity. Space Complexity In computer science, the space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of the size of the input. Space Complexity can also be defined as the function that describes the total memory space consumed upon running an algorithm. Consumption of space depends upon three things: the type of data structures used in the program, the memory allocations completed for the variables used and the results stored after execution. Additional Explanation A computer program, even though derived from a correct algorithm, might be useless for certain types of input because the time needed to run the program or space needed to hold data, program variables and so on is too great. Analysis of an Algorithm refers to the process of deriving estimates for the time and space needed to execute the algorithm. In this section we deal with the problem of estimating the time required to execute algorithms. Determining the performance parameters of computer programs is a difficult task and depends on a number of factors such as the computer that is being used, the way the data are represented and how the program is translated into machine instructions. Although precise estimates of the execution time of a program must take such factors into account, useful information can be obtained by analysing the time of the underlying algorithm. The time needed to execute an algorithm is a function of the input. We are primarily concerned with estimating the time of an algorithm rather than computing its exact time as long as we count some fundamental, dominating steps of an algorithm, we can obtain a useful measure of time. 1.X The Big O-Notation used in Measuring Complexity Big O Notation Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity. In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. Big O Notation (with a capital letter O not a zero) also called Landau's symbol is a symbolism used in complexity theory, computer science and mathematics to describe the asymptotic behaviour of functions. Basically, it tells you how fast a function grows or declines. Landau's symbol comes from the name of the German number theoretician Edmund Landau who invented the notation. The letter O is used because the rate of growth of a function is also called its order. For example, when analysing some algorithm, one might find that the time (or the number of steps) it takes to complete a problem of size n is given by T(n) = 4n2 - 2n + 2. If we ignore constants (which makes sense because those depend on the particular hardware the program is run on) and slower growing terms, we could say "T(n) grows at the order of n2" and write: T(n) = O(n2). Comparing growth of t(n) = 60n2 + 5n + 1 with 60n2 Here is a list of classes of functions that are commonly encountered when analysing algorithms. The slower growing functions are listed first. c is some arbitrary constant. Rate of Growth of Standard Functions Notation Name Example O(c) constant Determining if a binary number is even or odd; Using a constant-size lookup table; Calculating … O(logn) logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap O(n) linear Finding an item in an unsorted list or in an unsorted array; adding two n-bit integers by ripple carry; radix sort O(nlogn) linearithmic or loglinear Performing a fast Fourier transform; Fastest possible comparison sort; heapsort and merge sort O(n2) quadratic Multiplying two n-digit numbers by a simple algorithm; simple sorting algorithms, such as bubble sort, selection sort and insertion sort; (worst case) bound on some usually faster sorting algorithms such as quicksort, Shellsort, and tree sort O(nc) polynomial Tree-adjoining grammar parsing; maximum matching for bipartite graphs; finding the determinant with LU decomposition O(cn) exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search Note that O(nc) and O(cn) are very different. The latter grows much, much faster, no matter how big the constant c is. A function that grows faster than any power of n is called superpolynomial. One that grows slower than an exponential function of the form cn is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest algorithms known for integer factorisation. Also note that O(logn) is exactly the same as O(log(nc)). The logarithms differ only by a constant factor and the big O notation ignores that. Similarly, logs with different constant bases are equivalent. If a function f(n) is a sum of functions, one of which grows faster than the others, then the faster growing one determines the order of f(n). Common Big O Notations There are five common big O notations that provide a numerical basis for comparing the inherent efficiencies of two or more algorithms that perform the same task. They are as follows: O(log2n) slowest growth with increasing n O(n) O(nlog2n) O(n2) O(2n) fastest growth with increasing n Table 1.X Time to execute an algorithm if one step takes 1 microsecond to execute. lgn denotes log2n (the logarithm of n to base 2). Figure1.X The first 20 values of these five big O notations are given in Table 1.X. The graph is shown in Figure 1.X. Take note of their main differences as n increases from 1 to 10. It can be noted that n greater than 20 graphically O(2n) dwarfs all others. The scale of its increase is too great as compared to the rest. Efficiency of Algorithms This is concerned with finding most effective or competent algorithm when you have two or more algorithms doing the task. Three important efficiency criteria are as follows: Use of storage space Use of computer time Programming effort This is covered in the next topics by using the following pairs of algorithms: Fibonacci Sequence (iteration vs recursion) Searching (sequential vs binary) Sorting (bubble vs quick) 2 Techniques for Algorithms Design 2.1 Recursion A recursive function is one that calls itself. This powerful technique produces repetition without using loops (e.g. while loops or for loops). Thus it can produce substantial results from very little code. Recursion allows elegantly simple solutions to difficult problems but it can also be misused, producing ineffective code. Recursive code is usually produced from recursive algorithms. The complexity analysis of a recursive algorithm depends on the solubility of its recurrence relation. The general technique is to let T(n) be the number of steps required to carry out the algorithm on the problem of size n. The recursive part of the algorithm translates into a recurrence relation on T(n) Fibonacci Sequence The Fibonacci Sequence can be calculated both by iteration and by recursion. Both iteration and recursion involve repetition. Iteration uses standard loop structures while recursion uses repetitive method calls. Therefore, it is a good idea to study these two procedures using the Fibonacci Sequence. It shows the long-term effect of using a recursive method as opposed to a standard iterative one when calculations increase and get larger. 2.1.1 Iterative Method A sequence is a set of numbers occurring in order. An Italian mathematician Leonardo Fibonacci discovered the Fibonacci sequence in the early thirteenth century. It has two base terms which are 0 and 1 (not binary digits). Thereafter each successive term is the sum of the previous two terms. The first terms of a Fibonacci sequence are as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … mathematically it can be represented by: fi = fi-2 + fi-1 where fi is the present value or term, fi-1 is the predecessor and fi-2 is the predecessor of fi-1. The Fibonacci sequence can be calculated very easily by using the standard repetition control structures. This is known as iteration. The following formula can be used in a standard loop: f(i) = f(i-2) + f(i-1) where i is the loop control variable starting at 2 (0,1 being given) after the above present value is calculated i should be increased by 1 which means the previous f(i-1) becomes f(i-2) and the previous f(i) becomes f(i-1) then the next f(i) is calculated as above. Example: if currently i = 5 it means f(5) = f(3) + f(4) if i increases to 6 then f(6) = f(4) + f(5) i.e. the previous f(i-1) becomes f(i-2) and the previous f(i) becomes f(i-1) f(6) can now be calculated. 2.1.2 Algorithm get the number of the term required, N initialise the array fibonacci initialise fibonacci(0) to 0 initialise fibonacci(1) to 1 repeatedly set fibonacci(i) to fibonacci(i-2) + fibonacci(i-1) until i reaches the number of term required display the term 2.1.3 Tests Statistics and Results Table 2.1 Iterative Method Fibonacci Sequence term 1 2 3 4 5 10 15 20 25 30 35 40 No. of Calculations performed 1 2 3 4 5 10 15 20 25 30 35 40 Table 2.1 shows the statistics for calculations when the program was run with increasing data. The results indicate that the ratio of calculations to the term required is 1:1. Only 1 calculation is performed for each and every term before you get to the term required. Each and every iteration is responsible for a single calculation. If you want to calculate term number 10, it will mean 10 steps or calculations. That is n steps are required to be executed in order to calculate term number n. Thus, Fibonacci sequence by iteration is an O(n) algorithm. This type of algorithm is said to be of linear order. 2.1.4 Recursive Method The first Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Each number after the second is the sum of the preceding numbers. This is naturally recursive definition: Fn={█(0,if n=0@1,if n=1 @Fn-1+Fn-2,if n>1)┤ The first 15 values of the Fibonacci sequence are shown in the Table. The first two values, F0 and F1, are defined by the first two parts of the definition. F0=0 (for n=0) and F1=1 (for n=1). These two parts form the basis of the recursion. All the other values are defined by the recursive part of the definition: For n=2, F2=Fn=Fn-1+Fn-2=F(2)-1+F(2)-2=F1+F0=1+0=1 For n=3, F3=Fn=Fn-1+Fn-2=F(3)-1+F(3)-2=F2+F1=1+1=2 For n=4, F4=Fn=Fn-1+Fn-2=F(4)-1+F(4)-2=F3+F2=2+1=3 For n=5, F5=Fn=Fn-1+Fn-2=F(5)-1+F(5)-2=F4+F3=3+2=5 For n=6, F6=Fn=Fn-1+Fn-2=F(6)-1+F(6)-2=F5+F4=5+3=8 For n=7, F7=Fn=Fn-1+Fn-2=F(7)-1+F(7)-2=F6+F5=8+5=13 Another explanation: Fibonacci Sequence The Fibonacci sequence can also be calculated by using recursion. Recursion is a process whereby a method calls itself or else method A calls method B which in turn calls method A. The Fibonacci sequence can be defined recursively as follows: fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(n) = fibonacci(n-2) + fibonacci(n-1) Example: Calculation of f(5) will involve the following recursive calls: 2.1.5 Algorithm get the number of the term required, N initialise the fibonacci method repeatedly call the fibonacci method if N = 0 or N = 1 then return 0 or 1 respectively otherwise return fibonacci(N-2) + fibonacci(N-1) until the base is reached display the term 2.1.6 Tests Statistics and Results Table 2.2 Recursive Method Fibonacci Sequence term 1 2 3 4 5 10 15 20 25 No. of Calculations performed 1 3 5 9 15 177 1,973 21,891 242,785 Recursive Method - continuation Fibonacci Sequence term 30 35 40 No. of Calculations performed 2,692,537 29,860,703 331,160,281 Table 2.2 shows the statistics for calculations when the program was tested with increasing data. The results indicate an extreme increase in calculations as the data get larger and larger. This is like that because recursive calls have to get to the base of each and every term involved in the process. The difference in speed was noted once N exceeded 37 since there are now more than 100,000,000 calculations performed. Table 2.2 shows that Fibonacci(5) requires 15 calculations which is 24 – 1. That is roughly 2n steps are required to be executed in order to calculate term number n. Thus, Fibonacci sequence by recursion is an O(2n) algorithm. This type of algorithm is said to be of exponential order. Since Fibonacci sequence by recursion is O(2n) it means (2n/2n+1) is always equal to ½. Note the following: no. of calculations performed to get term 20 = 21,891 no. of calculations performed to get term 21 = 35,421 which means the increase between terms 20 & 21 is 13,530 no. of calculations performed to get term 22 = 57,313 which means the increase between terms 21 & 22 is 21,892 if you divide 21,892 by 13,530 the result is 1.618034… a constant that was noted starting with term 20 as shown. 2.1.7 Comparison of the Statistics The most important thing to note is that both programs produce the same terms of the Fibonacci sequence. The iterative program out-performs the recursive program in manipulating the Fibonacci sequence. The iterative program does very few calculations as compared with the recursive program. From the statistics it would appear the iterative program to be a superior program to the recursive program. Table 2.3 Performance of the two Methods (Efficiency of Algorithms) n Iterative Method O(n) Recursive Method O(2n) 5 5 32 10 10 1,024 20 20 1,048,576 30 30 1,073,741,824 40 40 1,099,511,627,776 50 50 1,125,899,906,842,620 An analysis of Table 2.3 proves that Fibonacci sequence by iteration is far much quicker than Fibonacci sequence by recursion. It can easily be noted that the iterative method is of O(n) whilst the recursive method is of O(2n). For example if n = 20 and assuming 1 calculation takes 1 microsecond. The iterative method will take 20 microseconds whilst the recursive method will take just a little over 1 second (what a big difference). 2.1.8 The Factorial Function The factorial function is defined mathematically by n!={█(1,if n=0@n(n-1)!,if n>0)┤ This is a recursive definition because the factorial “recurs” on the right side of the equation. The function is defined in terms of itself. The first 10 values of the factorial function are shown in Table 4.X. The first value, 0!, is defined by the upper half of the definition: 0! = (for n = 0). All the rest of the values are defined by the lower half of the definition: For n = 1, 1! = n! = n(n – 1)! = 1(1 – 1)! = 1(0)! = 1(1) = 1 For n = 2, 2! = n! = n(n – 1)! = 2(2 – 1)! = 2(1)! = 2(1) = 2 For n = 3, 3! = n! = n(n – 1)! = 3(3 – 1)! = 3(2)! = 3(2) = 6 For n = 4, 4! = n! = n(n – 1)! = 4(4 – 1)! = 4(3)! = 4(6) = 24 For n = 5, 5! = n! = n(n – 1)! = 5(5 – 1)! = 5(4)! = 5(24) = 120 The recursive factorial function runs in O(n) time. To work correctly, every recursive function must have a basis and a recursive part. The basis is what stops the recursion. The recursive part is where the function calls itself. 2.1.9 Binomial Coefficients The binomial coefficients are the coefficients that result from the expansion of a binomial expression of the form (x + 1)n. Example (x +1)6 = x6 + 6x5 + 15x4 + 20x3 + 15x2 + 6x + 1 The seven coefficients generated are 1, 6, 15, 20, 15, 6 and 1. Blaise Pascal discovered this recursive relationship among binomial coefficients. By arranging them in a triangle, he found that each interior number is the sum of the numbers directly above it. For example, 15 = 5 + 10. Let c(n,k) denote the coefficient in row number n and column number k (counting from 0). For example, c(6,2) = 15. Then Pascal’s recurrence relation can be expressed as c(n,k) = c(n-1), k-1) + c(n-1, k), for 0 < k < n For example, when n = 6 and k = 2, c(6,2) = c(5,1) + c(5,2) The binomial coefficients are the same as the combination numbers used in combinatorial mathematics. For example: c(n,k) or nCk = which is n choose k as shown: “8 choose 3” is = 8x7x6 = 56 1x2x3 2.2 Divide and Conquer This is covered in the next topics by using the following algorithms: Merge sort Quick sort 2.3 Balancing ??? XXX 2.4 Greedy Algorithms A greedy algorithm works by choosing the best possible answer in each step and then moving on to the next step until it reaches the end, without regard for the overall solution. It only hopes that the path it takes is the globally optimum one, but as proven time and again, this method does not often come up with a globally optimum solution. In fact, it is entirely possible that the most optimal short-term solutions lead to the worst possible global outcome. In other ways a greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimisation, greedy algorithms optimally solve combinatorial problems having the properties of matroids and give constant-factor approximations to optimisation problems with the submodular structure. Also think of it as taking a lot of shortcuts in a manufacturing business: in the short term large amounts are saved in manufacturing cost, but this eventually leads to downfall since quality is compromised, resulting in product returns and low sales as customers become acquainted with the “cheap” product. This is not always the case, there are a lot of applications where the greedy algorithm works best to find or approximate the globally optimum solution such as in constructing a Huffman tree or a decision learning tree. For example: Take the path with the largest sum overall. A greedy algorithm would take the blue path, as a result of short sightedness, rather than the orange path, which yields the largest sum. In general, greedy algorithms have five components: A candidate set, from which a solution is created A selection function, which chooses the best candidate to be added to the solution A feasibility function, that is used to determine if a candidate can be used to contribute to a solution An objective function, which assigns a value to a solution, or a partial solution and A solution function, which will indicate when we have discovered a complete solution Greedy algorithms produce good solutions on some mathematical problems but not on others. We can make whatever choice seems best at the moment and then solve the sub-problems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the sub-problem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage's algorithmic path to the solution. Travelling Salesman Problem The Travelling salesman problem is related to the problem of finding a Hamiltonian cycle in a graph. The problem is: Given a weighted graph G, find a minimum-length Hamiltonian cycle in G. If we think of the vertices in a weighted graph as cities and the edges weights as distances, the travelling salesman problem is to find a shortest route in which the salesperson can visit each city one time, starting and ending at the same city. There are two Travelling Salesman Problems: In the classical problem you must visit each vertex only once before returning to the start. In the practical problem you must visit each vertex at least once before returning to the start. Example 1 TSP Create a table of least distances for the network below. We need to look carefully for the shortest route between each pair of vertices. This may not always be the direct route, so you need to do some careful arithmetic. The top row shows the shortest routes starting at vertex A. Look at routes from A. There are direct routes from AB and AC and you can see these are the shortest routes. Using inspection you complete the table to show the routes AD and AE. You need to check AE carefully. Using ACE the route is 31. Using ABDE the route is 33. Therefore, so you record 31 as the value. This enables you to complete the top row of the table. You can use this to fill in the first column Since this not a directed network, the shortest distance from A to D is the same as the shortest distance from D to A. In this topic directed networks will not be examined. Finally when you complete all the entries giving this complete table of least distances: Therefore, the Travelling Salesman Problem is as follows: ABDECA. Example 2 TSP The network shows the distances, in Km, between the central sorting office at S and six post offices A, B, C, D, E and F. The table shows a partially complete table of least distances. Complete the table of least distances for the network above, stating your shortest route for each of the entries. 2.5 Recurrence Equations* Explanation 1 In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given; each further term of the sequence or array is defined as a function of the preceding terms. A recurrence relation describes each term in a sequence as a function of the previous term – i.e. un+1 = f(un) Along with the first term of the sequence, this allows you to generate the sequence term by term Both arithmetic sequences and geometric sequences can be defined using recurrence relations However, you can also define sequences that are neither arithmetic nor geometric For arithmetic or geometric sequences defined by recurrence relations, you can sum the terms using the arithmetic series and geometric series formulae. To sum up the terms of other sequences, you may have to think about the series and find a clever trick! Explanation 2 A recurrence relation relates the nth term of a sequence to its predecessors. These relations are related to recursive algorithms. A recurrence relation for a sequence a0, a1, a2, … is a formula (equation) that relates each term an to certain terms of its predecessors a0, a1, …, an − 1. The initial conditions for such a recurrence relation specify the values of a0, a1, a2, …, an − 1. For example, recursive formula for the sequence 3, 8, 13, 18, 23 is a1 = 3, an = an − 1 + 5, 2 ≤ n < ∞. Here, a1 = 3 is the initial condition. Similarly, the infinite sequence 3, 7, 11, 15, 19, 23, … can be defined by the recursive formula a1 = 3, an = an − 1 + 4, 2 ≤ n < ∞. Example 1 A ternary string is a sequence of digits where each digit can either be 0, 1 or 2 (base 3). There are 6 different ternary strings of length 2 which do not contain consecutive 0s. These are 10, 11, 12, 20, 21, 22. Given that tn represents the number of ternary strings of length n with no consecutive 0s. Therefore, as shown above t2 = 6. Find t3 and t4. Explain why tn satisfies the recurrence relation tn = 2tn-1 + 2tn-2. Find the number of different ternary strings of length 15 which do not contain consecutive 0s. Example 2 A population of bacteria has an initial size 200. After one hour, the population has reached 220. The population grows in such a way that the rate of growth doubles each hour. Write a recurrence relation to describe the number of bacteria, bn, after n hours. 3 Searching Searching is a common computer process that can be done in various ways. The Table below shows Time Complexity of Searching Algorithms: Algorithm Worst Sequential (Linear) Search O(n) Binary Search O(logn) 3.1 Sequential Search Sequential search (also known as linear search) means looking for a particular item within a given linear list, item by item until either the item is found or else you have reached the end of the list. Sequential searching is a common procedure especially if one is interested in accessing each and every item in the list. The following narration shows how sequential search works, given the following list of 7 numbers in an array A: 1 2 3 4 5 6 7 1900 7411 9102 3702 6733 9905 1111 If you are looking for the value 1900 in the list, you would compare 1900 with each and every value in the list until you find 1900, otherwise you have reached the end of the array. In this case 1900 would be found at position 1. The normal comparison that is used is to test for equality between the key and A(i). The key is compared with A(i), that is the given value is compared with each of the values in turn. In this case the key is 1900. If you are looking for 9905 in the list, you would do a similar procedure as given above. In this case 9905 would be located at position 6. If you are looking for 737 in the list, you would follow a similar procedure as shown. In this case 737 is not available in the list. When you reach the end of the list it means whatever you are looking for is not available within the given list. As you can notice sequential search can work both on ordered and unordered data since the searching is based on item by item. 3.1.1 Algorithm initialise the length of the list, N initialise the array A(N)and its elements initialise i get the key repeatedly compare the key to A(i) if the key = A(i) then number is available and stop increase i by 1 until i >= N display the number and its position else display an error 3.1.2 Tests Statistics and Results Table 3.1 Sequential Search Average Search Length calculations Length of Array 1 2 3 4 5 6 7 8 9 10 20 50 Average Search Length 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 10.5 25.5 Sequential Search - continuation Average Search Length calculations Length of Array 100 128 200 256 300 400 500 512 Average Search Length 50.5 64.5 100.5 128.5 150.5 200.5 250.5 256.5 Table 3.1 shows the statistics for average search length (ASL) when the sequential search program was tested with increasing data. The results indicate that the average search length is increasing by ½ for any two consecutive keys. The average search length can also be calculated using: = + when n is the number of items to be searched. When the array is doubled the average search length remains the same.*** The sequential search works very well for small arrays or unsorted arrays, however for large arrays it is inefficient. In the best case, sequential search scans only one value to locate a value which is the first value. In the worst case, sequential search scans all n values to locate an item. Thus it requires n steps to execute this procedure. On average, sequential search requires steps to locate an item. However recall that in big O notation, we ignore constant factors as well as lower order terms. Thus, sequential search is an O(n) algorithm. This algorithm is said to be of linear order. 3.2 Binary search Binary search is the process of examining the middle value of an array to see which half contains the desired value. The middle value of this half is then examined to see which half of the half contains the value in question. This halving process is continued until the value is located or it is determined that the value is not in the list. In order to use the binary search the list must be already sorted. Given the same list, array A as for sequential search, only that this time it has been ordered: 1 2 3 4 5 6 7 1111 1900 3702 6733 7411 9105 9905 Consider that you are looking for 1900, the steps are as follows: divide the length of the array by 2 to find the middle point; the middle point in this case = 3 compare 1900 with A(3) which is 3702 since 1900 is less than A(3) or 3702 then it means 1900 can be found in the lower half; upper limit is adjusted to (middle point – 1) and similarly steps 1 and 2 are therefore repeated now 1900 is greater than A(1) or 1111 then it means 1900 can be found in the upper half; lower limit is adjusted to (middle point + 1) and similarly steps 1 and 2 are again repeated now 1900 = A(2) or 1900 therefore the value has been located. Diagrammatically these steps can be summed to: 1 2 3 1111 1900 3702 after step 1 1 2 1111 1900 after step 3 2 1900 after step 4 3.2.1 Algorithm initialise the length of list, N initialise the array A(N)and its elements get the key set the lower limit to 1 set the upper limit to N initialise the middle point while lower limit <= upper limit set middle point to (lower limit + upper limit)/2 compare A(middle point) to the key if A(middle point) = key then the number is available and stop if A(middle point < key the set lower limit to middle point + 1 otherwise set upper limit to middle point – 1 display the number and its position else display an error 3.2.2 Tests Statistics and Results Table 3.2 Binary Search Average Search Length calculations Length of Array 1 2 3 4 5 6 7 8 9 10 11 12 20 50 Average Search Length 1 2 2 2 3 3 3 3 3 3 3 4 4 5 Binary Search - continuation Average Search Length calculations Length of Array 100 128 200 256 300 400 500 512 Average Search Length 6 7 7 8 8 8 8 9 Table 3.2 shows the statistics for average search length when the binary search program was run with increasing data. The results indicate that when the array is doubled the average search length increases just by 1.*** The algorithm locates the middle array element and compares it to the search key. If they are equal, the value is available in the list. If the search key is less than the middle array element, then the first half of the array is searched; otherwise the second half of the array is searched. The search continues until the search key is equal to the middle element of the sub-array or until the sub-array consists of one element that is not equal to the search key (i.e. the search key is not found). In the best case, binary search locates the item at the middle of the array in one step. In the worst case, binary search eliminates half of the remaining array components on each iteration. Thus the worst case of iterations is equal to the number of times n must be divided by 2 to eliminate all but one value. This number can easily be computed taking the logarithm, base 2 of n (written as log2n). Thus, binary search is an O(log2n) algorithm. This algorithm is said to be of logarithmic order. 3.3 Comparison of the two Searches Comparison of the Statistics The most important thing to note is that both programs can search and locate using the same search key. Sequential search can be used in place of binary search and vice versa. Only that binary search works on sorted lists only. Therefore sequential search is just an alternative to binary search. Binary search may be chosen in preference to sequential search when the list is long as well as sorted. Choose sequential search if you are interested in each and every item in the list. Table 3.3 Performance of the two Searches (Efficiency of Algorithms) N Sequential Search O(n) Binary Search O(log2n) 10 10 3 100 100 7 1,000 1,000 10 10,000 10,000 13 100,000 100,000 17 1,000,000 1,000,000 20 An analysis of Table 3.3 proves that binary search is far much quicker than sequential search. It can easily be noted that the sequential search method is of O(n) whilst the binary search method is of O(log2n). As you can see even for a list of 1,000,000 values, binary search has an average search length of only 20 whilst sequential search has an average search length of 500,000.5. Binary search is definitely the best choice for searching long lists because of its very low average search length (ASL). In the worst case scenario, searching an array of 1024 elements will take only 10 accesses using binary search. Repeatedly dividing 1024 by 2 (because after each access we are able to eliminate half of the array) yields the values 512, 256, 128, 64, 32, 16, 8, 4, 2 and 1. The number 1024 (210) is divided by 2 only 10 times to get the value 1. Dividing by 2 is equivalent to one comparison in the binary search algorithm. This a tremendous increase in performance (efficiency) over the sequential search that requires comparing the search key to an average of half the elements in the array. The maximum number of comparisons needed for the binary search of any sorted array is the exponent of the first power of 2 greater than the number of elements in the array whilst sequential search requires n comparisons. For example, if the list contains 1,000,000 values then 1,048,576 (220) i.e. 20 will give you the maximum comparisons for binary search. Summary: Differences between Sequential Search and Binary Search A sequential search scans one item at a time, without jumping to any item. In contrast, binary search cuts down your search to half as soon as you find the middle of a sorted list. In sequential search, the worst case complexity is O(n), where binary search making O(logn) comparisons. Time taken to search elements keep increasing as the number of elements is increased when searching through sequential process. But binary search compresses the searching period by dividing the whole array into two half. Sequential search does the sequential (consecutive) access whereas Binary search access data randomly. Input data needs to be sorted in Binary Search and not in Sequential Search. In sequential search, performance is done by equality comparisons. In binary search, performance is done by ordering comparisons. Binary search is better and quite faster than sequential search. Sequential search uses sequential approach. But, binary search implements divide and conquer approach. Sequential search is quick and easy to use, but there is no need for any ordered elements. Where binary search algorithm is tricky, and elements are necessarily arranged in order. The best case time in sequential search is for the first element that is O(1). And the other side O(1) is the middle element in binary search. Sequential search can be implemented in an array as well as in linked list, but binary search can't be implemented directly on linked list. Binary search is efficient for the larger array. If the amount of data is small, then sequential search is preferable because this searching process is fast when data is small. 4 Sorting Sorting is the re-arrangement of elements of an array in either ascending or descending order. For this exercise elements are re-arranged in ascending order that is from the smallest natural number to the largest. 4.1 Insertion Sort* In an insertion sort, the first element in the array is considered as sorted, even if it is an unsorted array. In an insertion sort, each element in the array is checked with the previous elements, resulting in a growing sorted output list. With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted. There are many advantages associated with an insertion sort. It is simple to implement and is quite efficient for small sets of data, especially if it is substantially sorted. It has low overhead and can sort the list as it receives data. Another advantage associated with insertion sort is the fact that it needs only a constant amount of memory space for the whole operation. It is more efficient than other similar algorithms such as bubble sort or selection sort. Insertion sort algorithm performs sorting by transferring one element at a time to the partially sorted array. An important feature of this algorithm is that it has a low overhead. Consider the following example. 20 100 3 25 6 95 45 55 We consider 20 is in the partially sorted array. Consider 100. It is greater than 20. 20 and 100 are in the partially sorted array. Now, consider 3. As it is less than 20, we can place it in the correct position. Now 3, 20 and 100 are in the partially sorted array. 3 20 100 25 6 95 45 55 Now, let’s consider 25. It is less than 100 but greater than 20, so we can place it in the correct position. 3, 20, 25, 100 are now in the partially sorted array. 3 20 25 100 6 95 45 55 Let’s consider 6. It is greater than 3 but less than 20. So, we can place it in the correct position. 3, 6, 20, 25, 100 are in the partially sorted array. 3 6 20 25 100 95 45 55 Let’s consider 95. It is greater than 25 but less than 100. We can locate that element in the correct position. 3 6 20 25 95 100 45 55 Now, consider 45. It is greater than 25 but less than 95. So, we can place it in the correct position. 3, 6, 20, 25, 45, 95, 100 are in the partially sorted array. 3 6 20 25 45 95 100 55 Next, consider 55. It is greater than 45 but less than 95. Therefore, we can place it in the correct position. 3 6 20 25 45 55 95 100 Now, we can see that all the elements are sorted. Algorithm: Insertion Sort (A) { for j=i to A.length key = A[i]; // insert A[i] into sorted sequence A[1,2,3,..,i-1] j= i-1; while (j>0 and A[j]>key) A[j+1] = A[j] j= j-1 A[j+1] = key } Exercise Use insertion sort to sort the following numbers. Clearly show your working. 6 5 3 1 8 7 2 4 4.2 Selection Sort* The Selection Sort is similar to the bubble sort. It makes n-1 passes through a sequence of n elements each time moving the largest of the remaining unsorted elements into its correct position. It is more efficient than the bubble sort because it doesn’t move any elements in the process of finding the largest. It makes only one swap on each pass after it has found the largest. It is called the selection sort because on each pass it selects the largest of the remaining unsorted elements and puts it in its correct position. Selection sort performs sorting by selecting the smallest element from the remaining elements and placing it at the correct position. Consider the following example. 20 100 3 25 6 95 45 55 Here, the lowest element is 3. Therefore, we can exchange it with the element in the first position (which is 20). 3 100 20 25 6 95 45 55 The lowest element out of the remaining elements is 6. We can exchange it with the element in the second position (which is 100). 3 6 20 25 100 95 45 55 The smallest element out of the remaining elements is 20. It is already in the 3rd position. Thus, there is no need for moving the elements. Next, the smallest element out of the remaining is 25. It also is in the 4th position, and there is no need for moving the elements. Now the minimum element out of the remaining is 45. We can exchange it with the element in the 5th position (which is 100). 3 6 20 25 45 95 100 55 The minimum element out of the remaining numbers is 55. Therefore, we can exchange it with the element in the 6th position which is 95. 3 6 20 25 45 55 100 95 Now, the lowest element out of the remaining is 95. We can exchange it with the element in the 7th position, which is 100. 3 6 20 25 45 55 95 100 The remaining element is 100 and it is in the correct position. Now, we can see that the elements are sorted. Algorithm: void Selection Sort (int a[], int n) { int i,j, temp, min; for (i=0; i<n-1; i++) { min = i; for (j=i+1; j<n; j++) if (a[j] < a[min]) { min = j; } temp = a[i]; a[i] = a[min]; a[min] = temp; } } 4.3 Bubble Sort The Bubble Sort makes n-1passes through a sequence of n elements. Each pass moves through the array from left to right, comparing adjacent elements and swapping each pair that is out of order. This gradually moves the larger elements to the right. It is called bubble sort because if the elements are visualised in a vertical column then each pass appears to “bubble up” the next largest element by bouncing it off smaller elements much like the rising bubble in a carbonated beverage. Bubble sort starts at the beginning of the array and compares two consecutive elements of the array. If they are in correct order, the next pair of elements is then compared. If they are not in the correct order, the elements are swapped and the next pair is compared. When this has been done for the entire array many times over the correct element will occupy the last position. Beginning with the left side of the array each time, successive passes are made through the array until it is sorted. Here is an illustration using array A: 1 2 3 4 5 2100 500 900 800 1700 Assuming we want the largest number to bubble to the right, then during pass 1, the process will be as follows: 2100 500 900 800 1700 500 2100 900 800 1700 500 900 2100 800 1700 500 900 800 2100 1700 500 900 800 1700 2100 In total there will be n – 1 (i.e. 4 in this case) passes before the entire array is sorted. Another explanation: Bubble Sort Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. Example: First Pass: (51428) –> (15428), Algorithm compares the first two elements and swaps since 5>1. (15428) –> (14528), Swap since 5>4 (14528) –> (14258), Swap since 5>2 (14258) –> (14258), These elements are already in order 8>5, algorithm does not swap them. Second Pass: (14258) –> (14258) (14258) –> (12458), Swap since 4>2 (12458) –> (12458) (12458) –> (12458) The array is already sorted but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: (12458) –> (12458) (12458) –> (12458) (12458) –> (12458) (12458) –> (12458) 4.3.1 Algorithm initialise the number of elements, N initialise the array A(N) and its elements set i to 0 set j to 1 repeatedly repeatedly if A(j-1) > A(j) then swap A(i) and A(j) increase j by 1 until j >= N increase i by 1 until i >= (N-1) display the sorted list Alternatively: Algorithm: Bubble Sort (int a[], n) { int swapped, i, j; for (i=0; i<n; i++) { swapped = 0; for (j=0; j<n-i-1; j++) { if (a[j] > a[j+1]) { swap (a[j], a[j+1]); swapped = 1; } } If (swapped == 0) break; } } 4.3.2 Tests Statistics and Results Table 4.1 Bubble Sort Numbers of Comparisons and Exchanges Array length 10 20 30 40 50 100 200 300 400 No. of Comparisons 81 361 841 1,521 2,401 9,801 39,601 89,401 159,201 No. of Exchanges 32 104 232 378 720 2,202 9,199 22,292 40,752 Bubble Sort - continuation Numbers of Comparisons and Exchanges Array length 500 600 700 800 900 1,000 No. of Comparisons 249,001 358,801 488,601 638,401 808,201 998,001 No. of Exchanges 59,618 86,550 118,701 156,392 192,535 241,740 Table 4.1 shows the statistics for comparisons and exchanges when the program was run with increasing data set sizes. The results indicate that there are more comparisons than exchanges (depends on the data). Roughly the number of comparisons is 4 times greater than the number of exchanges. Obviously there are fewer exchanges than comparisons because not all comparisons will result into exchanges being made. The number of exchanges depend on the original list whilst the number of comparisons will remain the same for any list of the same number of elements. There could be n – 1 passes each having n – 1 comparisons Therefore the total number of comparisons is calculated as follows = (n – 1)(n – 1) = n2 – 2n + 1 i.e. when n = 100; number of comparisons = 1002 – (2 * 100) + 1 = 9801 (the same as the result in Table 4.1) When n is very large, the n2 term greatly overwhelms the other terms (- 2n + 1). Thus the bubble sort is an O(n2) algorithm. This algorithm is said to be of quadratic order. The best performance of a bubble sort is when the list already sorted. The worst performance is when the list is sorted with all items in decreasing order. 4.3.3 Enhanced Algorithms The basic bubble sort can be enhanced to improve its performance. It is just a matter of improving the sorting structure. All the enhanced codes include among others the following three improvements: if the array is already sorted then the sort section should be discontinued, i.e. no exchanges are done during the first pass. if a number has occupied its correct position then there is no need to include it in further comparisons. This will shorten the later passes so that they are not of length n. when the array becomes sorted then the sort section should be discontinued, since no exchanges are done in subsequent passes. 4.4 Shell Sort XXX 4.5 Heap Sort XXX 4.6 Quick Sort Quick sort is one of the fastest sorting techniques. It uses recursion and is based on the idea of separating a list of numbers into two parts. One part contains numbers smaller than some number in the list; the other part contains numbers larger than this number. If an unsorted array A contains: 1 2 3 4 5 2100 500 900 800 1700 left pivot right selecting the element in the middle, A(3) = 900. This process then puts all values smaller than 900 to the left side and all values larger than 900 to the right side. The first subdividing produces: 800 500 900 2100 1700 pivot Now, each sub-list is subdivided in the same manner until all sub-lists are in order. The array is then sorted. 4.6.1 Algorithm initialise the number of elements initialise the array A(N) and its elements initialise i, j and pivot repeatedly scan with i from the left until A(i) > pivot scan with j from the right until A(i) < pivot swap A(i) and A(j) move i one step to the right move j one step to the left Until i and j overlap quicksort the left side quicksort the right side display the sorted list Alternatively: Algorithm: Quick sort partition (A, p, r) { x= A[r] i= p-1 for (j= p:r-1) { if (A[j] <= x) { i= i+1 exchange A[i] with A[j] } } exchange A[i+1] with A[r] return i+1 } 4.6.2 Tests Statistics and Results Table 4.2 Quick Sort Numbers of Comparisons and Exchanges Array length 10 20 30 40 50 100 200 300 400 No. of Comparisons 32 62 96 138 186 410 912 1,458 2,088 No. of Exchanges 16 28 45 62 85 191 428 686 998 Quick Sort continuation Numbers of Comparisons and Exchanges Array length 500 600 700 800 900 1,000 No. of Comparisons 2,680 3,236 3,826 4,466 5,062 5,786 No. of Exchanges 1,264 1,537 1,815 2,122 2,398 2,717 Table 4.2 shows the statistics for comparisons and exchanges when the program was run with increasing data set sizes. The results indicate that there are more comparisons than exchanges. Roughly the number of comparisons is 2 times greater than the number of exchanges. There are fewer exchanges than comparisons because not all comparisons will result into exchanges being made. The number of exchanges depends on the original list. Each partitioning requires one pass through the array and so is an O(n) algorithm. If the splitting of values is close to being midpoint values, there will be about log2 n levels of recursive calls. Therefore quick sort is an O(nlog2n) algorithm. This algorithm is said to be of logarithmic order. The worst performance of quick sort is when the list is already sorted since it becomes O(n2) i.e. not suitable for sorted or part-sorted data. Its best performance is when items are distributed randomly about the list, in which case partitions split the list into equal-sized lists, i.e. it always places the pivot item at the middle element of the list. In this case levels of the recursion will be relatively small. 4.6.3 Comparison of Bubble Sort and Quick Sort Comparison of the Statistics Table 4.3 Performance of the two Sorts (Efficiency of Algorithms) N Bubble Sort O(n2) Quick Sort O(nlog2n) 10 100 36 100 10,000 664 1,000 1,000,000 9,996 10,000 100,000,000 132,877 100,000 10,000,000,000 1,660,964 1,000,000 1,000,000,000,000 19,931,569 The most important thing to note is that both programs produce the same results though at extremely different run times. The quick sort program out-performs the bubble sort program. The quick sort program does very few comparisons and exchanges as compared with the bubble sort program. From the statistics it would appear the quick sort program to be a superior program to the bubble sort program. An analysis of Table 4.3 shows that quick sort is far much faster than bubble sort. It can easily be noted that the bubble sort is of O(n2) whilst the quick sort is of O(nlog2n). For example if n = 1,000 bubble sort will require approximately 1,000,000 comparisons whilst quick sort will require nearly 9,996 (compare this with the actually statistics). Sorts of O(nlog2n) are very complex, the parts of the algorithm that surrounds the comparison take longer to execute whilst sorts of O(n2) are very simple. 4.7 Radix Sort The Radix Sort assumes that the sequence's element type is a lexicographic array of constant size, that is, either a character string type or an integer type. Example: Sorting Books by Their ISBNs Every book published since the 1970s has been assigned a unique international standard book number (ISBN). These are usually printed at the bottom of the back cover of the book. For example, the ISBN for this book is 0071476989. (ISBNs are usually hyphenated, like 0-07-147698-9, to distinguish the four separate fields that make up the code). Algorithm: The Radix Sort Precondition: s = {s0 ... sn+1} is a sequence of n integers or character strings with radix r and width w). Postcondition: The sequence s is sorted numerically or lexicographically). Repeat step 2 for d = 0 up to w-1. Apply a stable sorting algorithm to the sequence s sorting only on digit number d. A sorting algorithm is said to be stable if it preserves the relative order of elements with equal keys. For example, the insertion sort is stable but not the heap sort. Example: Sorting ISBNs with the Radix Sort The diagram shows a sequence of 12 ISBNs and the first four iterations of the radix sort applied to it. Tracing the Radix Sort Note how the stability is needed to conserve the work done by previous iterations. For example, after the first iteration, 8838650527 precedes 0830636528 because 7<8. Both of these keys have the same value 2 in their second least significant digit (digit number d=1). Theorem: The Radix Sort runs in O(n) time The algorithm has WIDTH iterations and processes all n elements on each iteration three times. Thus, the running time is proportional to WIDTH*n and is a constant. Although O(n) is theoretically better than O(nlogn), the radix sort is rarely faster than the O(nlogn) sorting algorithms (merge sort, quick sort and heap sort). This because it has a lot of overhead extracting digits and copying arrays. 4.8 Merge Sort The Merge Sort applies the divide-and-conquer strategy to sort a sequence. First it subdivides the sequence into subsequences of singletons. Then it successively merges the subsequences pairwise until a single sequence is re-formed. Each merge preserves order, so each merged subsequence is sorted. When the final merge is finished, the complete sequence is sorted. Although it can be implemented iteratively, the merge sort is naturally recursive: split the sequence in two, sort each half and then merge them back together preserving their order. The basis occurs when the subsequence contains only a single element. Theorem: The Merge Sort runs in O(nlogn) time In general, the merge sort works by repeatedly dividing the array in half until the pieces are .singletons and then it merges the pieces pairwise until a single piece remains. This illustrated in the diagram. The number of iterations in the first part equals the number of times n can be halved: that is logn-1. In terms of the number and sizes of the pieces, the second part of the process reverses the first. So the second part also has logn-1 steps. So the entire algorithm has O(logn) steps. Each step compares all n elements. So the total number of comparisons is O(nlogn). Diagram of Merge Sort By using the divide-and-conquer strategy, the merge sort obtains an O(nlogn) runtime which is a significant improvement over the O(n2) times for other sort algorithms. The strategy is: Split the sequence into two subsequences. Sort each subsequence separately. Merge the two subsequences back together. The merge sort does the first step in the simplest balanced way possible: It splits the sequence at its middle. If the first step is done in other ways, we obtain different sorting algorithms. The divide-and-conquer strategy is also used in the binary search. Algorithm: merge sort (A, p, q, r) { n1= q-p+1 n2= r-q Let L[1:n+1] and R[1:n2+1] be new arrays for (i=1:n1) L[i]= A[p+i-1] for (j=1:n2) R[j]= A[q+j] L[n1 + 1]= infinity R[n2 + 1]= infinity i=1, j=1 for (k=p:r) { if (L[i] <= R[j]) A[k] = L[i] i= i+1 else A[k] = R[j] j= j+1 } } Another explanation: Divide and Conquer Algorithm Like Greedy and Dynamic Programming, Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps: Divide: Break the given problem into subproblems of same type. Conquer: Recursively solve these subproblems. Combine: Appropriately combine the answers. The following are some standard algorithms that are Divide and Conquer algorithms. Binary Search is a searching algorithm. In each step, the algorithm compares the input element x with the value of the middle element in array. If the values match, return the index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else recurs for right side of middle element. Quick Sort is a sorting algorithm. The algorithm picks a pivot element, rearranges the array elements in such a way that all elements smaller than the picked pivot element move to left side of pivot, and all greater elements move to right side. Finally, the algorithm recursively sorts the subarrays on left and right of pivot element. Merge Sort is also a sorting algorithm. The algorithm divides the array in two halves, recursively sorts them and finally merges the two sorted halves. Summary: In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. 4.8.1 Quick Sort versus Merge Sort Basis for Comparison Quick Sort Merge Sort 1.Partition of elements in the array In case of quick sort, the array is parted into any ratio. There is no compulsion of dividing the array of elements into equal parts in quick sort. In the merge sort, the array is parted into just 2 halves (i.e. n/2). 2.Worst case complexity The worst case complexity of quick sort is O(n2) as there is need of lot of comparisons in the worst condition. In merge sort, worst case and average case has same complexities O(nlogn). 3.Usage with datasets The quick sort cannot work well with large datasets. Merge sort can work well on any type of data sets irrespective of its size (either large or small). 4.Additional storage space requirement The quick sort is in place as it doesn’t require any additional storage. Merge sort is not in place because it requires additional memory space to store the auxiliary arrays. 5.Efficiency Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets. Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets. 6.Sorting method The quick sort is internal sorting method where the data is sorted in main memory. The merge sort is external sorting method in which the data that is to be sorted cannot be accommodated in the memory and needed auxiliary memory for sorting. 7.Stability Quick sort is unstable in this scenario. But it can be made stable using some changes in code. Merge sort is stable as two elements with equal value appear in the same order in sorted output as they were in the input unsorted array. 8.Preferred for Quick sort is preferred for arrays. Merge sort is preferred for linked lists. 9.Locality of reference Quicksort exhibits good cache locality and this makes quicksort faster than merge sort (in many cases like in virtual memory environment). Merge sort exhibits poor cache locality and this makes it slower than quicksort. 4.9 Bucket Sort The Bucket Sort is a distribution sort. It distributes the elements into "buckets" according to some coarse grain criterion and then applies another sorting algorithm to each bucket. It is similar to quick sort in that all the elements in bucket i are greater than or equal to all the elements in bucket i-1 and less than or equal to all elements in bucket i+1. Whereas quick sort partitions the sequence into two buckets, the bucket sort partitions the sequence into n buckets. Algorithm: The Bucket Sort Precondition: s = {s0 ... sn+1} is a sequence of n ordinal values with known minimum value min and maximum value max). Postcondition: The sequence s is sorted). Initialise an array of n buckets (collections). Repeat step 3 for each si in the sequence. Insert si into bucket j where j=rn, r=(si-min)/(max+1-min). Sort each bucket. Repeat step 6 for j from 0 to n-1. Add the elements of bucket j sequentially back into s. Example: Sorting US Social Security Numbers with the Bucket Sort Suppose you have 1000 nine-digit identification numbers. Set up 1000 arrays of type int and then distribute the numbers using j=rn, r=(si-min)/(max+1)=(si-0)/(109+1-0)=si/109. So, for example, the identification number 666666666 would be inserted into bucket number where j=rn=(666666666/109)(103)=666.666666=666. Similarly, identification number j 123456789 would be inserted into bucket number 123 and identification number 666543210 would be inserted into bucket 666 as shown in the figure. Then each bucket would be sorted. Note that the number of elements in each bucket will average 1, so the sorting algorithm will not affect the running time. Finally, the elements are copied back into s, starting with bucket number 0.ac Tracing the Bucket Sort Theorem: The bucket sort runs in O(n) time. The algorithm has three parallel lops, each iterating n times. The last loop has an inner loop but it averages only one iteration. The minimum() and maximum() methods require n steps each. Hence the number of steps executed is proportional to 5n Like the radix sort, the O(n) bucket sort is in practice much slower than the O(nlogn) sorting algorithms because of the substantial overheads costs. 4.10 Complexity of Sorting Algorithms In order to compare algorithms we must have some criteria to measure the efficiency of our algorithms. Suppose M is an algorithm and suppose n is the size of the output data. The time and space used by the algorithm are the two main measures for the efficiency of M. The time is measured by counting the number of “key operations” which in sorting and searching algorithm are number of comparisons. Normally the complexity of an algorithm is the function that gives the running time of the waste case in terms of the input size. The Table below shows Time Complexity of Sorting Algorithms: No. Algorithm Best Average Worst 1 Selection Sort Ω(n2) θ(n2) O(n2) 2 Bubble Sort Ω(n) θ(n2) O(n2) 3 Insertion Sort Ω(n) θ(n2) O(n2) X Shell Sort O(n3/2) 4 Heap Sort Ω(nlogn) θ(nlogn) O(nlogn) 5 Quick Sort Ω(nlogn) θ(nlogn) O(n2) 6 Merge Sort Ω(nlogn) θ(nlogn) O(nlogn) 7 Bucket Sort Ω(n+k) θ(n+k) O(n2) 8 Radix Sort Ω(nk) θ(nk) O(nk) 5 Algorithms on linked lists (simple, double, circular), sets, trees (traversal, balanced trees, B-trees), graphs (depth/breadth first search, minimum spanning tree, shortest path) Stacks and Queues Stacks and Queues are both special-purpose lists that restrict how the application can access data. This is done so that the structures can optimize themselves for speed. Both data structures are very simple, can be implemented with both linked-lists and vectors, and are used in many different programming applications. Stacks A Stack is a data type that only allows users to access the newest member of the list. It is analogous to a stack of paper, where you add and remove paper from the top, but never look at the papers below it. Another explanation: A stack is a collection that implements the last-in-first-out (LIFO) protocol. This means that the only accessible object in the collection is the last one that was inserted. A stack of books is a good analogy. You can’t take a book from the stack without first removing the books that are stacked on top of it. Stack Operations The fundamental operations of a stack are: Add an element onto the top of the stack. Access the current element on the top of the stack. Remove the current element on the top of the stack. These three operations are usually called push, peek and pop, respectively. All operations on a stack happen in constant time because no matter what the stack is always working with the top-most value and the stack always knows exactly where that is. This is the main reason why Stacks are so amazingly fast. Queues A Queue is a data structure where you can only access the oldest item in the list. It is analogous to a line in the grocery store, where many people may be in the line, but the person in the front gets serviced first. Another explanation: A queue is a collection that implements the first-in-first-out (FIFO) protocol. This means that the only accessible object in the collection is the first one that was inserted. The most common example of a queue is a waiting line. Queue Operations The fundamental operations of a queue are: Add an element to the back of the queue. Access the current element at the front of the queue. Remove the current element at the front of the queue. Some authors use enqueue and dequeue for add and remove operations. Queues like Stacks are very fast because all of the operations are simple and constant-time. 5.1 Linked List In computer science, a Linked List is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists. A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list. Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis. The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation. Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal. Another Explanation: Linked Lists and Pointers Suppose a brokerage firm maintains a file in which each record contains a customer’s name and salesman. The file contains the following data: Customer Adams Brown Clark Drew Evans Farmer Geller Hill Infeld Salesman Smith Ray Ray Jones Smith Jones Ray Smith Ray There are two basic operations that one would want to perform of the data: Operation A: Given the name of a customer, find his salesman. Operation B: Given the name of a salesman, find the list of his customers. There are a number of ways the data may be stored in the computer and the ease with which one can perform the operations A and B on the data. The file can be stored in the computer by an array with two rows (or columns) of nine names. Since the customers are listed alphabetically one could easily perform Operation A. However, in order to perform Operation B one must search through the entire array. The main drawback of such representation is that there may be a waste of a lot of memory (as was discussed in Databases). The data can be stored very efficiently by using linked lists and pointers. Next is a schematic diagram of a linked list with six nodes. Each node is divided into two parts: the first part contains the information of the element (e.g. NAME, ADDRESS, …), and the second part the link field or nextpointer field, contains the address of the next node in the list. This pointer field is indicated by an arrow drawn from one node to the next node in the list. Furthermore, the pointer field of the last node contains an invalid address called a null pointer which indicates the end of the list. Link List with 6 Nodes One main way of storing the original data as shown in the next figure uses linked lists. Observe that there are separate (sorted alphabetically) arrays for the customers and salesmen. Also, there is a pointer array SLSM parallel to CUSTOMER which gives the location of the salesman of a customer; hence operation A can be performed very easily and quickly. Furthermore, the list of customers of each salesman is linked as discussed above. Specifically, there is a pointer array START parallel to SALESMAN which points to the first customer of a salesman and there is an array NEXT which points to the location of the next customer in the salesman’s list or (or contains a 0 to indicate the end of the list). This process is indicated by the arrows for the salesman Ray. Operation B can be performed easily and quickly; that is one does not need to search through the list of all customers in order to obtain the list of customers of a given salesman. Its algorithm in a form of pseudocode is as follows. Algorithm The name of the salesman is read and the list of his customers is printed. Step 1 Read XXX Step 2 Find K such that SALESMAN[K] = XXX [Use binary search] Step 3 Set PTR := START[K] [Initialise pointer PTR] Step 4 Repeat while PTR = NULL Print CUSTOMER[PTR] Set PTR := NEXT[PTR] [Update PTR] Step 5 Exit Characteristics of a Linked List As mentioned above, a node in a linked list must have a data field and either one or two links. This allows the linked list to grow or shrink in constant O(1) time, as all that needs be done to insert or delete a node is change a few links. This is much better than the time for inserting or deleting an element in an array. However, the linked list requires linear O(N) time to find or access a node, because there is no simple formula as listed above for the array to give the memory location of the node. One must traverse all links from the beginning until the requested node is reached. If nodes are to be inserted at the beginning or end of a linked list, the time is O(1), since references or pointers, depending on the language, can be maintained to the head and tail nodes. If a node should be inserted in the middle or at some arbitrary position, the running time is not actually O(1), as the operation to get to the position in the list is O(N). 5.2 Sets XXX 5.3 Trees (traversals, balanced trees, B-trees) Tree (data structure) A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root. Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure it is usually represented and worked with separately by node (rather than as a set of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any). Preliminary Definition Not a tree: two non-connected parts, A→B and C→D→E. There is more than one root. Not a tree: undirected cycle 1-2-4-3. 4 has more than one parent (inbound edge). Not a tree: cycle B→C→E→D→B. B has more than one parent (inbound edge). Not a tree: cycle A→A. A is the root but it also has a parent. Each linear list is trivially a tree A tree is a data structure made up of nodes or vertices and edges without having any cycle. The tree with no nodes is called the null or empty tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy. Theorem: Every Node in a Tree has a Unique Root Path The depth of a node in a tree is the length of its root path. Of course, the depth of the root in any tree is 0. A level in a tree is the set of all nodes at a given depth. The height of a tree is the greatest depth among all its nodes. The degree of a node is the number of its children Properties of a Tree The six nodes are A, B, C, E, F and H are all internal nodes. The other nine nodes are leaves. The path (LHCA) is a leaf-to-root path. Its length is 3. Node B has depth 1 and node M has depth 3. Level 2 consists of nodes E, F, G and H. The height of the tree is 3. Nodes A, C and H are all ancestors of node L Node K is a descendant of node C but not of node B. The subtree rooted at B consists of nodes B, E, I and J. B has degree 1, D has degree 0 and H has degree 4. The order of a tree is the maximum (highest) degree among all of its nodes. Subtrees Theorem: The number of nodes of a full tree of order d and height h is given by the following formula: n= dh+1-1 d-1 Ordered Trees Here is the recursive definition of an ordered tree: An ordered tree is either the empty set or a pair T=(r,S), where r is a node and S is a sequence of disjoint ordered trees, none of which contains r. The node r is called the root of the tree T and the elements of the sequence S are its subtrees. The sequence S of course may be empty in which case T is singleton. The restriction that none of the subtrees contain the root applies recursively: x cannot be in any subtree or any subtree of any subtree and so on. Note that this definition is the same as that for unordered trees except for the facts that the subtrees are in a sequence instead of a set and an ordered tree may be empty. Traversal Algorithms A traversal algorithm is a method for processing a data structure that applies a given operation to each element of the structure. For example, if the operation is to print the contents of the element, then the traversal would print every element in the structure. The process of applying the operation to an element is called visiting the element. So executing the traversal algorithm causes each element in the structure to be visited. The order in which the elements are visited depends on which traversal algorithm is used. There are three common algorithms for traversing a general tree. The Level Order Traversal algorithm visits the root, then visits each element on the first level, then visits each element on the second level, and so forth, each time visiting all the elements on one level before going down to the next level. If the tree is drawn in the usual manner with its root at the top and leaves near the bottom, then the level order pattern is the same left-to-right top-to-bottom pattern that you follow to read English text. The Level Order Traversal The level order traversal of the tree would visit the nodes in the following order: ABCDEFGHIJKLM. Algorithm: The Level Order Traversal of an Ordered Tree To traverse a non-empty ordered tree: Initialise the queue. Enqueue the root. Repeat steps 4-7 until the queue is empty. Dequeue node X from the queue. Visit X Enqueue all the children of X in order. The Preorder Traversal algorithm visits the root and then does a preorder traversal recursively to each subtree in order. The Preorder Traversal The preorder traversal of the tree would visit the nodes in the following order: ABEHIFCDGJKLM. Note the preorder traversal of a tree can be obtained by circumnavigating the tree, beginning at the root and visiting each node the first time it is encountered on the left. Algorithm: The Preorder Traversal of an Ordered Tree To traverse a non-empty ordered tree: Visit the root. Do a recursive preorder traversal of each subtree in order. The Preorder Traversal algorithm does a postorder traversal recursively to each subtree before visiting the root. The Postorder Traversal The postorder traversal of the tree would visit the nodes in the following order: HIEFBCJKLMGDA. Algorithm: The Postorder Traversal of an Ordered Tree To traverse a non-empty ordered tree: Do a recursive preorder traversal of each subtree in order. Visit the root. Note that the level order and preorder traversals always visit the root of each subtree before visiting its nodes. The postorder traversal always visits the root of each subtree last after visiting all of its other nodes. Also, the preorder always visits the right-most node last while the postorder traversal always visits the left-most node first. The preorder and postorder traversals are recursive. They also can be implemented iteratively using a stack. The level order traversal is implemented iteratively using a queue. Another Explanation of the three traversals of a binary tree T with root R: Preorder Process the root R. Traverse the left subtree of R in preorder. Traverse the right subtree of R in preorder. Inorder Traverse the left subtree of R in inorder. Process the root R. Traverse the right subtree of R in inorder. Postorder Traverse the left subtree of R in postorder. Traverse the right subtree of R in postorder. Process the root R. Binary Tree A labeled binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set. Some authors allow the binary tree to be the empty set as well. Other Definitions Recursive Definition A binary tree is either the empty set or a triple T = (x, L, R). Where x is a node and L and R are disjoint binary trees, neither of which contains x. Non-recursive Definition A binary tree is an ordered tree in which every internal node has degree 2. Unequal binary trees: Equal binary trees: Characteristics of a Binary Tree This figure shows a binary tree of size 10 and height 3. Node A is its root. The path from node H to node B has length 2. Node B is at level 1 and node H is at level 3. B is an ancestor of H and H is a descendant of B. The caged region is subtree of size 6 and height 2. Its root is node B. Counting Binary Trees Binary Trees of Size 3 These are four different binary tree of size n = 3 Binary Trees of Size 4 These are four different binary tree of size n = 4 Two have height 3 and the other two height 2. Full Binary Trees A binary tree is said to be full if all its leaves are at the same level and every interior node has two children. Example: The Full Binary Trees of Height 3 This tree is a full binary tree of height 3. Note that it has 15 nodes (7 interior nodes and 8 leaves). Theorem: The full binary tree of height h has l = 2h leaves and m = 2h-1 internal nodes. Corollary: The full binary tree of height h has a total of n = 2h+1-1 nodes. Complete Binary Trees A Complete Binary Tree is either a full binary tree or one that is full except for a segment of missing leaves on the right side of the bottom level. Example: Complete Binary Tree of Height 3 This figure shows a complete tree. It is shown together with the full binary tree from which it was obtained by adding five leaves on the right at level 3. Note: Complete binary trees are important because of the simple way in which they can be stored in an array. This achieved by assigning index numbers to the tree nodes by level as shown in the figure. The beauty in this natural mapping is the simple way that it allows the array indexes for the children and parent to be computed. Algorithm: The Natural Mapping of a Complete Binary Tree into an Array To navigate about a complete binary tree stored by its natural mapping in array: The parent of the node stored at location i is stored at location i/2. The left child of the node stored at location i is stored at location 2i. The right child of the node stored at location i is stored at location 2i+1. For example, node E is stored at index i=5 in the array; its parent node B is located at index i/2 = 5/2 = 2, its left child node J is stored at location 2i = 2.5 = 10 and its right child node K is stored at index 2i+1 = 2.5+1 = 11. The natural mapping of a complete binary tree Example: Incomplete Binary Tree This figure shows an incomplete binary tree. The natural mapping of its nodes into an array leaves some gaps as shown in the mapping figure. The natural mapping of an incomplete binary tree Binary Tree Traversal Algorithms The three traversal algorithms that are used for the general tree apply to binary trees as well: the level order traversal, preorder traversal and postorder traversal. In addition, binary trees support a fourth traversal algorithm: the inorder traversal. The four algorithms are given next. Algorithm: The Level Order Traversal of a Binary Tree To traverse a nonempty binary tree: Initialise the queue. Enqueue the root. Repeat steps 4-7 until the queue is empty. Dequeue node X from the queue. Visit X. Enqueue the left child of X if exists. Enqueue the right child of X if exists Example: The Level Order Traversal of a Binary Tree The figure shows how the level order traversal looks on the binary tree of height 3. The nodes are visited in the order: ABCDEFGHIJKLMNO. Algorithm: The Preorder Traversal of a Binary Tree To traverse a nonempty binary tree: Visit the root. If the left subtree is nonempty, do a preorder traversal on it. If the right subtree is nonempty, do a preorder traversal on it. The nodes are visited in the order: ABDHIEJKCFLMGNO. The figure shows how the preorder traversal of a binary tree can be obtained by circumnavigating the tree, beginning at the root and visiting each node the first time it is encountered on the left. Algorithm: The Postorder Traversal of a Binary Tree To traverse a nonempty binary tree: If the left subtree is nonempty, do a postorder traversal on it. If the right subtree is nonempty, do a postorder traversal on it. Visit the root. The nodes are visited in the order: HIDJKEBLMFNOGCA. The preorder traversal visits the root first while the postorder traversal visits the root last. This suggests a third alternative for binary tree: Visit the root in between the traversals of the subtrees. This is called Inorder Traversal. Algorithm: The Inorder Traversal of a Binary Tree To traverse a nonempty binary tree: If the left subtree is nonempty, do an inorder traversal on it. Visit the root. If the right subtree is nonempty, do an inorder traversal on it. The nodes are visited in the order: HDIBJEKALFMCNGO. 5.X Heaps A heap is a complete binary tree whose elements have keys that satisfy the following heap property: the keys along any path from root to leaf are descending (i.e., non-increasing). Example: A Heap The figure shows a heap. Note that the keys along each of its roots-to-leaf paths are descending: 77≥66≥44≥22 77≥66≥44≥41 77≥66≥60≥58 77≥66≥60≥25 77≥55≥33≥29 77≥55≥55 Heaps could represent family descendant trees because the heap property means that every parent is older than his/her children. Heaps are used to implement priority queues and the heap sort algorithm. The Natural Mapping Every complete binary tree has a natural mapping into an array (as described earlier). Example: Storing Heap in an Array The previous heap maps into an array as follows: For example, element 60 is at index i=5, its parent is element 66 at index i/2=2 and its children are elements 58 and 25 at index 2i=10 and 2i+1=11. Insertion into a Heap Elements are inserted into a heap next to its right-most leaf at the bottom level. Then the heap property is restored by percolating the new element up the tree until it is no longer ”older” (i.e., its key is greater) than its parent. On each iteration, the child is swapped with the parent. The next figure has the root-to-leaf path (88,66,44,51) is not descending because 44<51. Hence this tree does not have the heap property. An array with the heap property is partially ordered. That means most of the larger keys come before most of the smaller keys. More precisely, it means that every heap-path subarray is sorted in descending order. The figure shows key 75 would be inserted into the heap. The element 75 is added to the tree as a new last leaf. Then it is swapped with the its parent element 44 because 75>44. Then is swapped with its parent 66 because 77>66. Now the heap property has been restored because the new element 75 is less than its parent and greater than its children. Removal from a Heap The heap removal algorithm always removes the root element from the tree. This is done by moving the last leaf element into the root element and then restoring the heap property by percolating the new root element down the tree until it is no longer ”younger” (i.e., its key is less) than its children. On each iteration, the parent is swapped with the older of its two children. The figure shows how the root element 88 would be removed from a heap. The last leaf (key 44) is removed and copied into the root, replacing the previous root (key 88) which is removed. Then, to restore the heap property, the element 44 is swapped with the larger of its two children (77). That step is repeated until element 44 is no longer smaller than any of its children. In this case, the result is that 44 ends up as a leaf again. Note that the removal affects only the nodes along a single root-to-leaf path. Theorem: Insertions into and Removals from a heap run in O(logn) time. 5.X Binary Search Trees A Binary Search Tree is a binary tree whose elements include a key field of some ordinal type and which has this property: If k is the key value at any node, then k≥x for every key x in the node's left subtree and k≤y for every key y in the node's right subtree. This property is called the BST Property, guarantees that an inorder traversal of the binary search tree will produce the elements in increasing order. A Binary Search Tree The BST property is applied for each insertion into the tree: Algorithm: Inserting into a Binary Search Tree To insert an element with key value k into a binary search tree: If the tree is empty, insert the new element at the root. Then return. Let p locate the root. If k is less than the key stored at p and if the node at p has no left child, insert the new element as the left child of p. Then return. If k is less than the key stored at p and if the node at p has a left child, let p locate that left child of p. Then go back to step 3. If the node at p has no right child, insert the new element as the right child of p. Then return. Let p locate the right child of p. Then go back to step 3. Example: Inserting into a Binary Search Tree. Apply the previous algorithm Step 1 starts the iterator p at the root k. Since M is greater than K (i.e., it follows it lexicographically) and node K has a right child, the algorithm proceeds to step 6, resetting the iterator p to node P and then goes back to step 3. Next, since M is less than P (i.e., it proceeds it lexicographically) and node P has a left child, the algorithm proceeds to step 4, resetting the iterator p to none N and then goes back to step 3. Next, since M is also less than N but node N has no left child, the algorithm proceeds to step 5, inserts the new element as the left child of node N and then returns. Example: Building a Binary Search Tree The figure shows the binary search tree that is built by inserting the input sequence: 44,22,77,55,99,88,33 If a binary search tree is balanced, it allows for very efficient searching. As with the binary search, it takes O(logn) steps to find an element in a balanced binary tree. Exercise Build a binary search tree using the following nodes E, B, D, F, A, G and C AVL Trees AVL Tree can be defined as height balanced binary search tree in which each node is associated with a balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree. In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(logn) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. The imbalance problem can be avoided by imposing balance constraints on the nodes of the binary search tree. Defined as the balance number at any node of a tree to be the difference between the height of its left subtree and the height of its right subtree. An AVL tree is a binary search tree where the balance number at each node is either -1, 0 or 1. Example: Insertion into an AVL Tree Example: Building an AVL Tree Insertions of G, M, T, D and P into an empty AVL tree as shown in the figure. The first rotation occurs with the insertion of T. That increases the balance at the root to which violates the AVL constraint. The left rotation about the root x makes M become the parent of its prior parent G. Note how efficient the rotations are. By making only local changes to references and balance numbers, they restore the tree to nearly perfect balance. B- Trees A B- tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions and deletions in logarithmic time. The B- tree generalises the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B- tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems. A B- Tree of order m is an m-way search tree that satisfies the following extra conditions: The root has at least two children. All other internal nodes have at least m/2 children. All leaf nodes are at the same level. These conditions make the tree more balanced (and thus more efficient) and they simplify the insertion and deletion algorithms. A B- tree is a type of tree, or data structure that helps support various IT systems by allowing a range of dynamic child node numbers that can be changed over time. It uses a set of keys to divide these collections of nodes. B- trees are used as index for large data sets stored on disk. In a relational database, data are organised in separate sequences of records called tables. Each table could be stored as a sequential data file in which the records are numbered like elements of an array. Or the database system might access the records directly by their disk address. Either way, each record is directly accessible on disk via some addressing scheme. So once we have the record's disk address we can access it immediately (i.e., with a single disk read). So the "key" that is stored in the B- tree is actually a key/address pair containing the record's key value (e.g. US social Security number or Malawi Citizenship ID number for personnel records or an ISBN for books) together with its disk address. Example A: B- tree Example B: B- tree Algorithm: Searching in a B- tree To find a record with key k using a B- tree index of order m: If the tree is empty, return null Let x be the root. Repeat steps 4-6 until x is a leaf node. Apply the binary search to node x for the key ki where ki-1 <k≤ki (regarding k0=-∞ and k=∞). If ki=k, retrieve the record from disk and return it. Let x be the root of subtree Si. Return null. B+ Trees The B+ tree is a variation of B- tree: The B+ tree is a balanced binary search tree. It follows a multi-level index format. In the B+ tree, leaf nodes denote actual data pointers. B+ tree ensures that all leaf nodes remain at the same height. In the B+ tree, the leaf nodes are linked using a link list. Therefore, a B+ tree can support random access as well as sequential access. Structure of B+ Tree In the B+ tree, every leaf node is at equal distance from the root node. The B+ tree is of the order n where n is fixed for every B+ tree. It contains an internal node and leaf node. Internal node An internal node of the B+ tree can contain at least n/2 record pointers except the root node. At most, an internal node of the tree contains n pointers. Leaf node The leaf node of the B+ tree can contain at least n/2 record pointers and n/2 key values. At most, a leaf node contains n record pointer and n key values. Every leaf node of the B+ tree contains one block pointer P to point to next leaf node. Searching a record in B+ Tree Suppose we have to search 55 in the below B+ tree structure. First, we will fetch for the intermediary node which will direct to the leaf node that can contain a record for 55. So, in the intermediary node, we will find a branch between 50 and 75 nodes. Then at the end, we will be redirected to the third leaf node. Here DBMS will perform a sequential search to find 55. B+ Tree Insertion Suppose we want to insert a record 60 in the below structure. It will go to the 3rd leaf node after 55. It is a balanced tree, and a leaf node of this tree is already full, so we cannot insert 60 there. In this case, we have to split the leaf node, so that it can be inserted into tree without affecting the fill factor, balance and order. The 3rd leaf node has the values (50, 55, 60, 65, 70) and its current root node is 50. We will split the leaf node of the tree in the middle so that its balance is not altered. So we can group (50, 55) and (60, 65, 70) into 2 leaf nodes. If these two has to be leaf nodes, the intermediate node cannot branch from 50. It should have 60 added to it, and then we can have pointers to a new leaf node. This is how we can insert an entry when there is overflow. In a normal scenario, it is very easy to find the node where it fits and then place it in that leaf node. B+ Tree Deletion Suppose we want to delete 60 from the above example. In this case, we have to remove 60 from the intermediate node as well as from the 4th leaf node too. If we remove it from the intermediate node, then the tree will not satisfy the rule of the B+ tree. So we need to modify it to have a balanced tree. After deleting node 60 from above B+ tree and re-arranging the nodes, it will show as follows: Differences between B- tree and B+ tree B- Tree: B- Tree is known as a self-balancing tree as its nodes are sorted in the inorder traversal. In B- tree, a node can have more than two children. B- tree has a height of logM N (Where ‘M’ is the order of tree and N is the number of nodes). And the height is adjusted automatically at each update. In the B- tree data is sorted in a specific order, with the lowest value on the left and the highest value on the right. To insert the data or key in B- tree is more complicated than a binary tree. Some conditions must be held by the B- Tree: All the leaf nodes of the B- tree must be at the same level. Above the leaf nodes of the B- tree, there should be no empty suB- trees. B- tree’s height should lie as low as possible. B+ Tree: B+ tree eliminates the drawback B- tree used for indexing by storing data pointers only at the leaf nodes of the tree. Thus, the structure of leaf nodes of a B+ tree is quite different from the structure of internal nodes of the B tree. It may be noted here that, since data pointers are present only at the leaf nodes, the leaf nodes must necessarily store all the key values along with their corresponding data pointers to the disk file block, to access them. Moreover, the leaf nodes are linked to providing ordered access to the records. The leaf nodes, therefore form the first level of the index, with the internal nodes forming the other levels of a multilevel index. Some of the key values of the leaf nodes also appear in the internal nodes, to simply act as a medium to control the searching of a record. Let’s see the difference between B- tree and B+ tree: Basis of Comparison B- tree B+ tree Pointers All internal and leaf nodes have data pointers. Only leaf nodes have data pointers. Search Since all keys are not available at leaf, search often takes more time. All keys are at leaf nodes, hence search is faster and more accurate. Redundant Keys No duplicate of keys is maintained in the tree. Duplicate of keys are maintained and all nodes are present at the leaf. Insertion Insertion takes more time and it is not predictable sometimes. Insertion is easier and the results are always the same. Deletion Deletion of the internal node is very complex and the tree has to undergo a lot of transformations. Deletion of any node is easy because all node are found at leaf. Leaf Nodes Leaf nodes are not stored as structural linked list. Leaf nodes are stored as structural linked list. Access Sequential access to nodes is not possible. Sequential access is possible just like linked list. Height For a particular number nodes height is larger. Height is lesser than B tree for the same number of nodes. Application B- Trees used in Databases, Search engines. B+ Trees used in Multilevel Indexing, Database indexing. Number of Nodes Number of nodes at any intermediary level ‘l’ is 2l. Each intermediary node can have n/2 to n children. 5.4 Graphs (depth/breadth first search, minimum spanning tree, shortest path) Graph (abstract data type) A directed graph with six vertices (blue circles) and seven edges (blue arrows). A graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics; specifically, the field of graph theory. A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.). Graph Data Structure Vertex − Each node of the graph is represented as a vertex. Edge − Edge represents a path between two vertices or a line between two vertices. Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. Path − Path represents a sequence of edges between the two vertices. Directed Graphs A simple directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them. Definition In formal terms, a directed graph is an ordered pair G = (V, A) where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arrows, directed edges (sometimes simply edges with the corresponding set named E instead of A), directed arcs, or directed lines. It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called edges, arcs, or lines. On the other hand, the aforementioned definition allows a directed graph to have loops (that is, arrows that connect nodes with themselves), but some authors consider a narrower definition that doesn't allow directed graphs to have loops. More specifically, directed graphs without loops are addressed as simple directed graphs, while directed graphs with loops are addressed as loop-digraphs. Directed graphs are graphs in which the edges are one-way. Such graphs are frequently more useful in various dynamic systems such as digital computers or flow systems. However, this added feature makes it more difficult to determine certain properties of the graph. That is, processing such graphs may be similar to travelling in a city with many one-way streets. A directed graph G or diagraph (or simply graph) consists of two things: A set V whose elements are called vertices, nodes or points. A set E of ordered pairs (u,v) of vertices called arcs or directed edges or simply edges. We will write G(V,E) when we want to emphasise the two parts of G. We will also write V(G) and E(G) to denote, respectively, the set of vertices and the set of edges of a graph G. Suppose e = (u,v) is a directed edge in a graph G. Then the following terminology is used: e begins at u and ends at v. u is the origin or initial point of e and v is the destination or terminal point of e. v is a successor of u. u is adjacent to v and v is adjacent from u. If u = v, then e is called a loop. Example Consider the directed graph G in the next diagram. It consists of four vertices, A,B,C,D that is, V(G) = {A,B,C,D} and the seven following edges: E(G) = {e1,e2,…,e7} = {(A,D),(B,A),(B,A),(D,B),(B,C),(D,C),(B,B)} The edges e2 and e3 are said to be parallel since they both begin at B and end at A. The edge e7 is a loop since it begins and ends at B. Paths Let G be directed graph. The concepts of path, simply path, trail and cycle carry over from non-directed graphs to the directed graph G except that the directions of the edges must agree with of the path. Specially: A (directed) path P in G is an alternating sequence of vertices and directed edges, say, P=(v0,e1,v1,e2,v2,…..,en,vn) such that each edge ei begins at vi-1 and ends at vi. If there is no ambiguity, we denote P by its sequence of vertices or its sequence of edges. The length of the path P is n, its number of edges. A simple path is a path with distinct vertices. A trail is a path with distinct edges. A closed path has the same first and last vertices. A spanning path contains all the vertices of G. A cycle (or circuit) is a closed path with distinct vertices (except the first and last). A semipath is the same as a path except the edge ei may begin at vi-1 or vi and end at the other vertex. Semitrails and semisimple paths are analogously defined. A vertex v is reachable from a vertex u if there is a path from u to v. If v is reachable from u then (by eliminating redundant edges) there must be a simple path from u to v. Example The following are the qualities of the directed graph G in the next figure. The vertex set V has four vertices and the edge set E has seven (directed) edges as follows: V={X,Y,Z,W} and E={(X,Y),(X,Z),(X,W),(Z,Y),(Z,W),(W,Y)} There are three simple paths from X to Z which are (X,Z),(X,W,Z) and (X,Y,W,Z). There is only simple path from Y to Z which is (Y,W,Z). There is only cycle in G which is (Y,W,Z,Y). G is unilaterally connected since (X,Y,W,Z) is a spanning path. G is not strongly connected since there is no closed spanning path. Weighted Graphs A Weighted Graph is a graph whose vertices or edges have been assigned weights; more specifically, a vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges. In many applications, each edge of a graph has an associated numerical value, called a weight. Usually, the edge weights are non-negative integers. Weighted graphs may be either directed or undirected. Graph Traversal Graph Traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal. Unlike tree traversal, graph traversal may require that some vertices be visited more than once, since it is not necessarily known before transitioning to a vertex that it has already been explored. As graphs become very dense, this redundancy becomes more prevalent, causing computation time to increase; as graphs become more sparse, the opposite holds true. Thus, it is usually necessary to remember which vertices have already been explored by the algorithm, so that vertices are revisited as infrequently as possible (or in the worst case, to prevent the traversal from continuing indefinitely). This may be accomplished by associating each vertex of the graph with a "colour" or "visitation" state during the traversal, which is then checked and updated as the algorithm visits each vertex. If the vertex has already been visited, it is ignored and the path is pursued no further; otherwise, the algorithm checks/updates the vertex and continues down its current path. Several special cases of graphs imply the visitation of other vertices in their structure, and thus do not require that visitation be explicitly recorded during the traversal. An important example of this is a tree: during a traversal it may be assumed that all "ancestor" vertices of the current vertex (and others depending on the algorithm) have already been visited. Both the depth-first and breadth-first graph searches are adaptations of tree-based algorithms, distinguished primarily by the lack of a structurally determined "root" vertex and the addition of a data structure to record the traversal's visitation state. Graph Traversal Algorithms Graph traversal is the problem of visiting all the vertices of a graph in some systematic order. There are mainly two ways to traverse a graph. Breadth First Search Depth First Search Breadth First Search Breadth First Search (BFS) starts at starting level-0 vertex X of the graph G. Then we visit all the vertices that are the neighbours of X. After visiting, we mark the vertices as "visited", and place them into level-1. Then we start from the level-1 vertices and apply the same method on every level-1 vertex and so on. The BFS traversal terminates when every vertex of the graph has been visited. BFS Algorithm The concept is to visit all the neighbour vertices before visiting other neighbour vertices of neighbour vertices. Initialize status of all nodes as “Ready”. Put source vertex in a queue and change its status to “Waiting”. Repeat the following two steps until queue is empty − Remove the first vertex from the queue and mark it as “Visited”. Add to the rear of queue all neighbours of the removed vertex whose status is “Ready”. Mark their status as “Waiting”. Problem Let us take a graph (Source vertex is A) and apply the BFS algorithm to find out the traversal order. Solution Initialize status of all vertices to “Ready”. Put A in queue and change its status to “Waiting”. Remove A from queue, mark it as “Visited”. Add A’s neighbours in “Ready” state B, D and E to end of queue and mark them as “Waiting”. Remove B from queue, mark it as “Visited”, put its “Ready” neighbour C at end of queue and mark C as “Waiting”. Remove D from queue and mark it as “Visited”. It has no neighbour in “Ready” state. Remove E from queue and mark it as “Visited”. It has no neighbour in “Ready” state. Remove C from queue and mark it as “Visited”. It has no neighbour in “Ready” state. Queue is empty so stop. So the traversal order is − A→B→D→E→CA→B→D→E→C The alternate orders of traversal are − A→B→E→D→CA→B→E→D→C Or, A→D→B→E→CA→D→B→E→C Or, A→E→B→D→CA→E→B→D→C Or, A→B→E→D→CA→B→E→D→C Or, A→D→E→B→CA→D→E→B→C Application of BFS Finding the shortest path Minimum spanning tree for un-weighted graph GPS navigation system Detecting cycles in an undirected graph Finding all nodes within one connected component Complexity Analysis Let G(V,E) be a graph with |V| number of vertices and |E| number of edges. If breadth first search algorithm visits every vertex in the graph and checks every edge, then its time complexity would be: O(|V|+|E|).O(|E|) It may vary between O(1) and O(|V2|) Depth First Search Depth First Search (DFS) algorithm starts from a vertex V, then it traverses to its adjacent vertex (say X) that has not been visited before and mark as "visited" and goes on with the adjacent vertex of X and so on. If at any vertex, it encounters that all the adjacent vertices are visited, then it backtracks until it finds the first vertex having an adjacent vertex that has not been traversed before. Then, it traverses that vertex, continues with its adjacent vertices until it traverses all visited vertices and has to backtrack again. In this way, it will traverse all the vertices reachable from the initial vertex V. DFS Algorithm The concept is to visit all the neighbour vertices of a neighbour vertex before visiting the other neighbour vertices. Initialize status of all nodes as “Ready” Put source vertex in a stack and change its status to “Waiting” Repeat the following two steps until stack is empty − Pop the top vertex from the stack and mark it as “Visited” Push onto the top of the stack all neighbours of the removed vertex whose status is “Ready”. Mark their status as “Waiting”. Problem Let us take a graph (Source vertex is A) and apply the DFS algorithm to find out the traversal order. Solution Initialize status of all vertices to “Ready”. Push A in stack and change its status to “Waiting”. Pop A and mark it as “Visited”. Push A’s neighbours in “Ready” state E, D and B to top of stack and mark them as “Waiting”. Pop B from stack, mark it as “Visited”, push its “Ready” neighbour C onto stack. Pop C from stack and mark it as “Visited”. It has no “Ready” neighbour. Pop D from stack and mark it as “Visited”. It has no “Ready” neighbour. Pop E from stack and mark it as “Visited”. It has no “Ready” neighbour. Stack is empty. So stop. So the traversal order is − A→B→C→D→EA→B→C→D→E The alternate orders of traversal are − A→E→B→C→DA→E→B→C→D Or, A→B→E→C→DA→B→E→C→D Or, A→D→E→B→CA→D→E→B→C Or, A→D→C→E→BA→D→C→E→B Or, A→D→C→B→EA→D→C→B→E Complexity Analysis Let G(V,E) be a graph with |V| number of vertices and |E| number of edges. If DFS algorithm visits every vertex in the graph and checks every edge, then the time complexity is: ⊝(|V|+|E|) Applications Detecting cycle in a graph To find topological sorting To test if a graph is bipartite Finding connected components Finding the bridges of a graph Finding bi-connectivity in graphs Solving the Knight’s Tour problem Solving puzzles with only one solution XXX=== Shortest Path Problem (6, 4, 5, 1) and (6, 4, 3, 2, 1) are both paths between vertices 6 and 1 Shortest path (ACEDF) between vertices A and F in the weighted directed graph In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment. Dijkstra's Algorithm (an example of Greedy Algorithm) Dijkstra's algorithm to find the shortest path between a and b. Pick the unvisited vertex with the lowest distance, calculate the distance through it to each unvisited neighbour and update the neighbour's distance if smaller. Mark visited (set to red) when done with neighbours. Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a digraph, which may represent, for example, road networks. The algorithm uses a priority queue, initialising it with all the vertices and then dequeueing one vertex on each iteration. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road (for simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A widely used application of shortest path algorithm is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and Open Shortest Path First (OSPF). It is also employed as a subroutine in other algorithms such as Johnson's. The Dijkstra algorithm uses labels that are positive integers or real numbers, which are totally ordered. It can be generalised to use any labels that are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing. This generalisation is called the Generic Dijkstra shortest-path algorithm. Dijkstra's original algorithm does not use a min-priority queue and runs in time O(V2). (where V is the number of nodes). Explanation1: Dijkstra's Algorithm Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step. Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current. For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbour B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value. When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3. When planning a route, it is actually not necessary to wait until the destination node is "visited" as above: the algorithm can stop once the destination node has the smallest tentative distance among all "unvisited" nodes (and thus could be selected as the next "current"). Explanation2: Dijkstra's Algorithm Here's another description of the algorithm: Mark your selected initial node with a current distance of 0 and the rest with infinity. Set the non-visited node with the smallest current distance as the current node C. For each neighbour N of your current node C: add the current distance of C with the weight of the edge connecting C-N. If it's smaller than the current distance of N, set it as the new current distance of N. Mark the current node C as visited. If there are non-visited nodes, go to step 2. 7.4 Minimum Spanning Trees A planar graph and its minimum spanning tree. Each edge is labelled with its weight, which here is roughly proportional to its length. A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are quite a few use cases for minimum spanning trees. One example would be a telecommunications company trying to lay cable in a new neighbourhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable. Applications Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids (which they were first invented for). They are invoked as subroutines in algorithms for other problems, including the Christofides algorithm for approximating the traveling salesman problem, approximating the multi-terminal minimum cut problem (which is equivalent in the single-terminal case to the maximum flow problem) and approximating the minimum-cost weighted perfect matching. Algorithm A: Minimum Spanning Tree The input is a connected weighted graph G with n vertices Step1: Arrange the edges of graph G in the order of decreasing weights. Step2: Proceeding sequentially, delete each edge that does not disconnect the graph until n-1 edges remain. Step3: Exit. Algorithm B (Kruskal): Minimum Spanning Tree The input is a connected weighted graph G with n vertices Step1: Arrange the edges of G in order of increasing weights. Step2: Starting only with the vertices of G and proceeding sequentially, add each edge which does not result in a cycle until n-1 edges are added. Step3: Exit. Example: Using Algorithm A Edge HK HJ AK BK CE DE GJ BJ CJ JK EJ AD EG Weight 18 10 9 9 9 9 9 9 8 8 7 6 5 Delete? X X X X X X X X X X Edge BD EF FH AB GH BC CD FG Weight 4 4 4 3 3 2 2 1 Delete? X X Shortest Path: between A and H = ABJH =3+9+10 =22 Or = ABCEGH =3+2+9+5+3=22 between A and G = ABCEG =3+2+9+5 =19 compiled by: Clifford Ghambi Lilongwe December 2021