L1 - Introduction to Algorithms.pdf

CP312 Algorithm Design and Analysis I LECTURE 1: INTRODUCTION TO ALGORITHMS 1 Main questions What are algorithms? Why is the study of algorithms worthwhile? How do we analyze and design algorithms? 2 What are algorithms? Definition: An algorithm is a well-defined procedure consisting of a sequence o...

CP312 Algorithm Design and Analysis I LECTURE 1: INTRODUCTION TO ALGORITHMS 1 Main questions What are algorithms? Why is the study of algorithms worthwhile? How do we analyze and design algorithms? 2 What are algorithms? Definition: An algorithm is a well-defined procedure consisting of a sequence of computational steps that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is a tool designed to solve a particular computational problem. Examples? ◦ ◦ ◦ ◦ Sorting elements Finding the median value in a list Finding the shortest path from A to B Finding the optimal way to shop in a supermarket 3 Example: Sorting Problem: Sort a sequence of numbers in non-decreasing order Input: A sequence of numbers 𝜋 = 𝑎1 , … , 𝑎𝑛 Output: A permutation 𝜋 ′ = 𝑎1′ , … , 𝑎𝑛′ of 𝜋 such that 𝑎1′ ≤ 𝑎2′ ≤ ⋯ ≤ 𝑎𝑛′ An algorithm for the sorting problem is a sequence of computational steps with the above input/output specifications. Ex: 8, 10, 1, 6, 2, 7, 3 ⇒ (1, 2,3,6,7,8,10) 4 Example: Majority Problem: Find the element in a list that occurs the most number of times Input: A multi-set of numbers 𝑆 = 𝑎1 , … , 𝑎𝑛 Output: A number 𝑥 such that number of #𝑥 ∈ 𝑆 > (#𝑦 ∈ 𝑆) for any 𝑦≠𝑥 An algorithm for the majority problem is a sequence of computational steps with the above input/output specifications. Ex: 1, 7, 7, 1, 7, 7, 4 ⇒ 7 5 Example: Majority We will always start with the naïve approach ◦ Naïve: The simplest (not necessarily most efficient) approach that you know for sure will give you the correct answer. What is the naïve approach for the majority problem? 1. 2. 3. List the number of unique elements 𝑥1 , 𝑥2 , … , 𝑥𝑚 in 𝑆 For each 𝑥𝑖 iterate over the entire list: Count the number of 𝑥𝑖 in 𝑆 Output 𝑥𝑖 with the highest count How fast is this algorithm – in terms of the number of items in the list? 6 Example: Majority Questions you need to answer: Better ◦ Can you do better than naïve? ◦ How fast can the algorithm be? ◦ Is there a theoretical lower bound? (e.g., you can prove that it cannot be done better than 𝑛2 ) Worse 7 Other real-life examples Big Data: How do we manage, search, and manipulate large volumes of data on the internet? And what is the best way to do it? Networking: How do we route and find the shortest path for packets on the network while causing minimal congestion? Image Processing: How do we edit, restore, filter, analyze, and classify images? Security: How do we secure our data in storage and in transit? And what is the best way to do it? And many more… (e.g. Electronic commerce, resource allocation, etc.) 8 Why is the study of algorithms worthwhile? Functionality Correctness Running-time ◦ Scalability Space/Memory Elegance and Simplicity Reliability 9 How do we analyze and design algorithms? Analysis: We will focus on techniques to analyze the correctness and running-time of algorithms. Design: We will look at various techniques that will help in designing algorithms, developed to solve particular computational problems. 10