Algorithms and Data Structures 2 - Introduction PDF

Structures 2 Algorithms and Data Structures 2 1 - Introduction Dr Michele Sevegnani School of Computing Science University of Glasgow [email protected] O...

Structures 2 Algorithms and Data Structures 2 1 - Introduction Dr Michele Sevegnani School of Computing Science University of Glasgow [email protected] Outline Admin − Course structure − Materials − Contents − Assessment − Context: prerequisites and relation with other courses Foundations − What is an algorithm? − What is a data structure? − Why studying algorithms is an essential aspect of the CS curriculum − A first example: array sorting ADS 2, 2024 2 Course structure 11 lectures − Each lecture will be given twice each week − Lecture 1: Tuesdays at 11 is in Main Building 255 Humanity LT − Lecture 2: Thursdays at 11 is in Main Building 220AB Hunter Halls 1-hour weekly labs at various times with different tutors − Start week 2 (week beginning 15th January) − Labs are in BO 706 or the Kelvin Building Lab 320 (to be confirmed) − Attendance will be monitored ADS 2, 2024 3 Materials Lecture slides − Available on Moodle at the beginning of each week Video lectures − Available on Moodle Lab sheets − Via Moodle Course text − Goodrich, Michael T., Roberto Tamassia, and Michael H. Goldwasser. Data structures and algorithms in Java. John Wiley & Sons, 2014 Other suggested texts − Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009 − Sedgewick, Robert. Algorithms in Java, Parts 1–4 (Fundamental Algorithms, Data Structures, Sorting, Searching). Addison Wesley, 2002 ADS 2, 2024 4 Contents Week Topics Week Topics 1 Introduction 6 Trees Analysis techniques Binary search trees Recursive algorithms 7 Balanced trees 2 9 Maps 3 Sorting algorithms Hash tables Analysis of recursive algorithms 10 4 11 Dynamic programming Greedy algorithms 5 Linked lists Abstract Data Types May be subject to minor changes ADS 2, 2024 5 Assessment Final exam − Counts for 80% − We will go over past exams during the revision classes Two assessed coursework assignments − Count for 20% (10% each) − Build on work carried out during tutorials ADS 2, 2024 6 Context First course in Algorithms and Data structures for students with experience with programming in Java Introduces new concepts such as − Data structures − ADTs (abstract data types) − Algorithms − Pseudocode − Complexity analysis (to study algorithms’ performance) Prerequisites: knowledge of the basics of Java and basic calculus Main concepts will be revised before use ADS 2, 2024 7 Context Object-Oriented Software Engineering (OOSE2) − Will use some of the data structures and algorithms we introduce Algorithmics I and Algorithmics II − Extends the algorithms side, assumes knowledge of the data structures and complexity analysis learned in this course Project work in Levels 3 and/or 4 Basic algorithms and data structures are important in many other courses − Network routing protocols − Operating systems scheduling algorithms − Information retrieval − … ADS 2, 2024 8  Foundations ADS 2, 2024 9 What is an algorithm? An algorithm is a step-by-step procedure for solving a problem in a finite amount of time − Alternatively: a well-defined computational procedure that takes some value (or set of values), as input and produces some value (or set of values), as output (Cormen) Some examples − Sorting − String matching − Finding the greatest common divisor of two numbers (Euclid’s algorithm) An algorithm can be specified in many ways − Natural language (English) − Computer program (implementation) using e.g. Java or pseudocode − Hardware design ADS 2, 2024 10 Practical applications Internet − Routing protocols (finding good routes on which the data will travel) − Indexing for search engines − Public-key cryptography − Data compression Biology − DNA analysis Optimisation problems and AI Navigation − Shortest route − Path finding The interview process in most tech companies often involves questions on algorithms! ADS 2, 2024 11 What is a data structure? A data structure is a method to store and organise data in order to facilitate access and modifications Most algorithms involve the creation of data structures to organise the data involved in the computations Examples − Arrays − Linked lists − Stack − Binary trees − … No single data structure works well for all purposes Important to know limitations and strengths of several of them ADS 2, 2024 12 Example: array sorting Input: an array A of integers (with indices between 0 and n-1) Output: a permutation of the input such that A ≤ A ≤ … ≤ A[n-1] Description of the algorithm as a program written in pseudocode INSERTION-SORT(A) for j := 1 to n-1 key := A[j] i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 13 Operation of INSERTION-SORT 5 2 4 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=1 key = 2 key := A[j] i=0 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 14 Operation of INSERTION-SORT 5 5 4 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=1 key = 2 key := A[j] i = -1 Exit while loop i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 15 Operation of INSERTION-SORT 2 5 4 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=1 key = 2 key := A[j] i = -1 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 16 Operation of INSERTION-SORT 2 5 4 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=2 key = 4 key := A[j] i=1 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 17 Operation of INSERTION-SORT 2 5 5 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=2 key = 4 key := A[j] i=0 Exit while loop i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 18 Operation of INSERTION-SORT 2 4 5 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=2 key = 4 key := A[j] i=0 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 19 Operation of INSERTION-SORT 2 4 5 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=3 key = 6 key := A[j] i=2 Exit while loop i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 20 Operation of INSERTION-SORT 2 4 5 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=3 key = 6 key := A[j] i=2 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 21 Operation of INSERTION-SORT 2 4 5 6 1 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=4 key = 1 key := A[j] i=3 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 22 Operation of INSERTION-SORT 2 4 5 6 6 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=4 key = 1 key := A[j] i=2 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 23 Operation of INSERTION-SORT 2 4 5 5 6 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=4 key = 1 key := A[j] i=1 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 24 Operation of INSERTION-SORT 2 4 4 5 6 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=4 key = 1 key := A[j] i=0 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 25 Operation of INSERTION-SORT 2 2 4 5 6 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=4 key = 1 key := A[j] i = -1 Exit while loop i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 26 Operation of INSERTION-SORT 1 2 4 5 6 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=4 key = 1 key := A[j] i = -1 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 27 Operation of INSERTION-SORT 1 2 4 5 6 3 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=5 key = 3 key := A[j] i=4 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 28 Operation of INSERTION-SORT 1 2 4 5 6 6 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=5 key = 3 key := A[j] i=3 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 29 Operation of INSERTION-SORT 1 2 4 5 5 6 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=5 key = 3 key := A[j] i=2 i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 30 Operation of INSERTION-SORT 1 2 4 4 5 6 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=5 key = 3 key := A[j] i=1 Exit while loop i := j-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 31 Operation of INSERTION-SORT 1 2 3 4 5 6 indices 0 1 2 3 4 5 INSERTION-SORT(A) n=6 for j := 1 to n-1 j=5 key = 3 key := A[j] i=1 i := j-1 while i ≥ 0 and A[i] > key Termination A[i+1] := A[i] i := i-1 A[i+1] := key ADS 2, 2024 32 Properties of INSERTION-SORT Efficient algorithm for sorting a small number of elements − We will prove this formally in the next lectures Stable: it does not change the relative order of elements with equal keys − Exercise: check this fact In-place: it only requires a constant amount of additional memory space − Besides the space for input array A, it only stores variables i,j and key ADS 2, 2024 33 Algorithm analysis Correctness: an algorithm is correct if for every input instance it halts with the correct output − We say that a correct algorithms solves a given computational problem The running time of an algorithm typically grows with the input size − For huge instances, we want to develop methods to use time and space as efficiently as possible Algorithm analysis allows us to predict the resources that the algorithm requires In the next classes, we will study the mathematical tools we need to carry out this kind of analysis ADS 2, 2024 34 Summary What is an algorithm? Definition of data structure A first example: INSERTION-SORT Properties − Stable − In-place Pseudocode Algorithm analysis ADS 2, 2024 35