Algorithm 1 Lecture Notes PDF

ALGORITHM 1 Mahsa Ziraksima ACIBADEM UNIVERSITY Fall 2024 About Class Weeks Lecture 1. Introduction to Algorithms 2. Analyzing Algorithms 3. Analyzing Algorithms, Recursion 4. Search Algorithms 5. Search Algorithms 6. Sorting Algorithms 7. Mi...

ALGORITHM 1 Mahsa Ziraksima ACIBADEM UNIVERSITY Fall 2024 About Class Weeks Lecture 1. Introduction to Algorithms 2. Analyzing Algorithms 3. Analyzing Algorithms, Recursion 4. Search Algorithms 5. Search Algorithms 6. Sorting Algorithms 7. Midterm I (during class) 8. Sorting Algorithms 9. Linked Lists 10. Stacks, Queues 11. Trees, Binary Trees, Binary Search Trees 12. Midterm II (during class) 13. Binary Search Trees 14. Binary Heaps About Class REFERENCES Main Textbook The Self-Taught Computer Scientist The beginner’s guide to data structures & algorithms by Cory Althoff. Wiley, 2022. An unofficial link to the textbook https://books-library.net/files/books-library.net-11301817Az7X6.pdf Supplementary Reading Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 2006. https://book.huihoo.com/pdf/algorithms/ Algorithms by Sedgewick and Wayne. 4th edition. SUMMARY Algorithms Data structures  Aims **Google Search** – What happens when we type a query into Google o the system doesn’t just match keywords; o it uses complex algorithms to rank billions of web pages based on relevance and quality. This involves techniques such as PageRank, which assesses the importance of pages based on links, and machine learning algorithms that help improve search results over time. – How this affects their daily? – Behind the scenes, algorithms are constantly at work to deliver the most relevant and useful information makes it relatable – Understanding algorithms is crucial for understanding technology that shapes our world. – What happen if Google didn’t use algorithms effectively?” algorithmic efficiency plays an important role in technology.  Aims What method or algorithm to use for solving a problem? what method to use for storing the information as data structures? why one algorithm may be better than another? How to compare two algorithms to analyze them? Aims Aims Aims  What Is an Algorithm Steps for solving a problem: – Model the problem. – Find an algorithm to solve it. – See if it is fast enough? Does it fit in memory? – If not, figure out a way to address it. – Iterate until satisfied.  What Is an Algorithm An algorithm is a sequence of steps that solves a problem. – Find prime numbers – Search – Sort  What Is an Algorithm Definite, effective, and finite process that receives input and produces output based on this input. Donald Knuth Definiteness means that the steps are clear, concise, and unambiguous. Effectiveness means that you can perform each operation precisely to solve the problem. Finiteness means that the algorithm stops after a finite number of steps. Correctness means that the algorithm should always produce the same output for a given input, and this output should be the correct answer to the problem the algorithm solves. Most, but not all, algorithms fulfill these requirements.  Example Fibonacci numbers: – how many rabbits a single pair can produce after a year: Considering that rabbits never die, and every month each adult pair produces a pair of baby rabbits who mature the next month. The sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233  Example Fibonacci numbers: – Recursive algorithm has exponential time complexity. O(2𝑛 ) – Iterative algorithm has linear time complexity. O(N)  Analyzing Algorithms There is often more than one algorithm we can use to solve a problem. We want to analyze algorithms to: – Predict their performance. – Be able to compare them. – Provide guarantees. Which one is the best? – Simplest – Fastest – Smallest – Run Time the amount of time it takes your computer to execute an algorithm  Run Time What factors affect the program’s run time? – available processing power the computer you are running the program – computer’s processing power – programming language – Run Time Run Time Run Time Run Time  Analyzing Algorithms There is often more than one algorithm we can use to solve a problem. Which one is the best? – Simplest – Fastest – Smallest – Run Time All these factors are affected by so many different variables, thus are not an effective way to compare two algorithms. computer scientists compare algorithms by looking at the number of steps they require.  Analyzing Algorithms Finding the number of steps in an algorithm is not very helpful, because, you can’t always reliably count the number of steps in an algorithm. conditional statements A computer scientist wants to know is how an algorithm performs when n gets bigger. As n gets larger, one part of the equation will overshadow the rest of the equation to the point that everything else becomes irrelevant. Big O notation describes an algorithm’s time or space requirements  Analyzing Algorithms Classifications for order of magnitude or time complexity – Constant time O(1) – Logarithmic time O(log n) – Linear time O(n) – Log-linear time O(n log n) – Quadratic time O(n**2) – Cubic time O(n**3) – Exponential time O(c**n) Analyzing Algorithms  Time Complexity Types of time complexity analyses: – best-case complexity how it performs with ideal input – worst-case complexity how it performs in the worst possible scenario – average-case complexity how it performs on average When comparing algorithms, we look at the average-case complexity. In deeper analysis, we can also compare their best-case and worst-case complexities.  Space Complexity Resource usage is very important. The amount of memory space your algorithm needs includes: – Fixed space amount of memory your program requires – data structure space amount of memory your program needs to store the data set – Temporary space amount of memory your algorithm needs for intermediary processing Why Is This Important?  RECURSION Mahsa Ziraksima ACIBADEM UNIVERSITY Fall 2024 SUMMARY Iterative algorithm Recursive algorithm  ITERATIVE ALGORITHMS It solves problems by repeating steps over and over, typically using a loop.  RECURSIVE ALGORITHMS It is a method of problem-solving where you solve smaller instances of the problem until you arrive at a solution.  RECURSIVE ALGORITHMS Recursive algorithms rely on functions that call themselves. Any problem you can solve with an iterative algorithm, you can also solve with a recursive one. Base case: a condition that ends a recursive algorithm to stop it from continuing forever. The three laws of recursion: – A recursive algorithm must call itself recursively. – A recursive algorithm must have a base case. – A recursive algorithm must change its state and move toward the base case.  RECURSIVE ALGORITHMS Factorial: 3! = 3 * 2 * 1 recursivefactorial(3) 3×2×1 6 return 3 × recursivefactorial(2) return 3 × 2 × 1 6 return 2 × recursivefactorial(1) return 2 × 1 2 return 1 1