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 .

2 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 .. 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.

3 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 .. Recursive Algorithms .. 387 Binary Search Searching with arrays or lists.

4 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.

5 Basic operations on binary heap trees .. Inserting a new heap tree node .. Deleting a heap tree node .. Building a new heap tree from scratch .. 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 .

6 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 .. A simple Hash Table in operation .. Strategies for dealing with collisions.

7 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.

8 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. 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.

9 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)

10 , 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 . 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 .