Lecture Notes for Data Structures and Algorithms

1 Lecture Notes forData Structures and AlgorithmsRevised each year by John BullinariaSchool of Computer ScienceUniversity of BirminghamBirmingham, UKVersion of 27 March 2019 These Notes are currently revised each year by John Bullinaria. They include sections based onnotes originally written by Mart n Escard o and revised by Manfred Kerber. All are membersof the School of Computer Science, University of Birmingham, School of Computer Science, University of Birmingham, UK, 20181 Contents1 Algorithms as opposed to programs .. Fundamental questions about Algorithms .. data Structures , abstract data types, design patterns .. Textbooks and web-resources .. Overview ..82 Arrays, Iteration, Arrays .. Loops and Iteration .. Invariants .. 103 Lists, Recursion, Stacks, Linked Lists.

2 Recursion .. Stacks .. Queues .. Doubly Linked Lists .. Advantage of Abstract data Types .. 204 Requirements for searching .. Specification of the search problem .. A simple algorithm: Linear Search .. A more efficient algorithm: Binary Search .. 235 Efficiency and Time versus space complexity .. Worst versus average complexity .. Concrete measures for performance .. Big-O notation for complexity class .. Formal definition of complexity classes .. 296 General specification of trees .. Quad-trees .. Binary trees .. Primitive operations on binary trees .. The height of a binary tree .. The size of a binary tree .. Implementation of trees.

3 Recursive Algorithms .. 387 Binary Search Searching with arrays or lists .. Search keys .. Binary search trees .. Building binary search trees .. Searching a binary search tree .. Time complexity of insertion and search .. Deleting nodes from a binary search tree .. Checking whether a binary tree is a binary search tree .. Sorting using binary search trees .. Balancing binary search trees .. Self-balancing AVL trees .. B-trees .. 498 Priority Queues and Heap Trees stored in arrays .. Priority queues and binary heap trees .. Basic operations on binary heap trees .. Inserting a new heap tree node .. Deleting a heap tree node .. Building a new heap tree from scratch.

4 Merging binary heap trees .. Binomial heaps .. Fibonacci heaps .. Comparison of heap time complexities .. 629 The problem of sorting .. Common sorting strategies .. How many comparisons must it take? .. Bubble Sort .. Insertion Sort .. Selection Sort .. Comparison ofO(n2) sorting Algorithms .. Sorting algorithm stability .. Treesort .. Heapsort .. Divide and conquer Algorithms .. Quicksort .. Mergesort .. Summary of comparison-based sorting Algorithms .. Non-comparison-based sorts .. Bin, Bucket, Radix Sorts .. 8310 Hash Storing data .. The Table abstract data type .. Implementations of the table data structure .. Hash Tables .. Collision likelihoods and load factors for hash tables.

5 A simple Hash Table in operation .. Strategies for dealing with collisions .. Linear Probing .. Double Hashing .. good hash functions .. of hash tables .. 9611 Graph terminology .. Implementing graphs .. Relations between graphs .. Planarity .. Traversals systematically visiting all vertices .. Shortest paths Dijkstra s algorithm .. Shortest paths Floyd s algorithm .. Minimal spanning trees .. Travelling Salesmen and Vehicle Routing .. 11712 Epilogue118A Some Useful Binomial formulae .. Powers and roots .. Logarithms .. Sums .. Fibonacci numbers .. 1214 Chapter 1 IntroductionThese Lecture Notes cover the key ideas involved in designingalgorithms. We shall see howthey depend on the design of suitabledata Structures , and how some Structures and algorithmsare moreefficientthan others for the same task.

6 We will concentrate on a few basic tasks,such as storing, sorting and searching data , that underlie much of computer science, but thetechniques discussed will be applicable much more will start by studying some key data Structures , such as arrays, lists, queues, stacksand trees, and then move on to explore their use in a range of different searching and sortingalgorithms. This leads on to the consideration of approaches for more efficient storage ofdata in hash tables. Finally, we will look at graph based representations and cover the kindsof Algorithms needed to work efficiently with them. Throughout, we will investigate thecomputational efficiency of the Algorithms we develop, and gain intuitions about the pros andcons of the various potential approaches for each will not restrict ourselves to implementing the various data Structures and algorithmsin particular computer programming languages ( , java ,C,OCaml), but specify them insimplepseudocodethat can easily be implemented in any appropriate Algorithms as opposed to programsAnalgorithmfor a particular task can be defined as a finite sequence of instructions, eachof which has a clear meaning and can be performed with a finite amount of effort in a finitelength of time.

7 As such, analgorithmmust be precise enough to be understood byhumanbeings. However, in order to beexecutedby acomputer, we will generally need aprogramthatis written in a rigorous formal language; and since computers are quite inflexible comparedto the human mind, programs usually need to contain more details than Algorithms . Here weshall ignore most of those programming details and concentrate on the design of algorithmsrather than task ofimplementingthe discussed Algorithms as computer programs is important,of course, but these Notes will concentrate on the theoretical aspects and leave the practicalprogramming aspects to be studied elsewhere. Having said that, we will often find it usefulto write down segments of actual programs in order to clarify and test certain theoreticalaspects of Algorithms and their data Structures .

8 It is also worth bearing in mind the distinctionbetween different programming paradigms:Imperative Programmingdescribes computation interms of instructions that change the program/ data state, whereasDeclarative Programming5specifies what the program should accomplish without describing how to do it. These noteswill primarily be concerned with developing Algorithms that map easily onto the imperativeprogramming can obviously be described in plain English, and we will sometimes do , for computer scientists it is usually easier and clearer to use something that comessomewhere in between formatted English and computer program code, but is not runnablebecause certain details are omitted. This is calledpseudocode, which comes in a variety offorms. Often these Notes will present segments of pseudocode that are very similar to thelanguages we are mainly interested in, namely the overlap ofCandJava, with the advantagethat they can easily be inserted into runnable Fundamental questions about algorithmsGiven an algorithm to solve a particular problem, we are naturally led to ask:1.

9 What is it supposed to do?2. Does it really do what it is supposed to do?3. How efficiently does it do it?The technical terms normally used for these three aspects are:1. Performance details of these three aspects will usually be rather problem formalize the crucial details of the problem that the algorithmis intended to solve. Sometimes that will be based on a particular representation of theassociated data , and sometimes it will be presented more abstractly. Typically, it will have tospecify how the inputs and outputs of the algorithm are related, though there is no generalrequirement that the specification is complete or simple problems, it is often easy to see that a particular algorithm will always work, that it satisfies its specification. However, for more complicated specifications and/oralgorithms, the fact that an algorithm satisfies its specification may not be obvious at this case, we need to spend some effortverifyingwhether the algorithm is indeed general, testing on a few particular inputs can be enough to show that the algorithm isincorrect.

10 However, since the number of different potential inputs for most Algorithms isinfinite in theory, and huge in practice, more than just testing on particular cases is neededto be sure that the algorithm satisfies its specification. We needcorrectness proofs. Althoughwe will discuss proofs in these Notes , and useful relevant ideas likeinvariants, we will usuallyonly do so in a rather informal manner (though, of course, we will attempt to be rigorous).The reason is that we want to concentrate on the data Structures and Algorithms . Formalverification techniques are complex and will normally be left till after the basic ideas of thesenotes have been , theefficiencyorperformanceof an algorithm relates to theresourcesrequiredby it, such as how quickly it will run, or how much computer memory it will use.