Introduction to Algorithms, Steps, Complexity

Introduction to Algorithms, Steps, Time Complexity

1. Introduction  to  Design  and  Analysis  of  Algorithms (DAA) Course Overview  and  Introduction  to  Algorithms 04/09/24

2. Welcome to the course! This course will provide a comprehensive understanding of algorithm design and analysis. We will learn about different types of algorithms, their efficiency, and applications. By the end of the course, you will be equipped to design and analyse algorithms for various problems. 04/09/24

3. What is an Algorithm? An algorithm is  a  step-by-step procedure or formula for solving  a  problem. It consists of  a  sequence of finite instructions  to  accomplish  a  specific task. Algorithms are fundamental  to  computer science and programming. 04/09/24

4. Algorithm definitions An algorithm is an ordered set of unambiguous executable steps, defining a terminating process. 04/09/24

5. Key Characteristics of algorithms Finite - An algorithm must have a clear starting and ending point. Precise -  Each step in the algorithm is clearly defined and unambiguous. Effective -  The algorithm can be executed within a reasonable time frame with available resources. Input/Output -  It takes inputs and produces outputs, processing information to achieve a desired outcome. 04/09/24

6. Everyday Applications of Algorithms Algorithms are part of our daily lives. Search Engines -  Algorithms sort and display the most relevant search results. GPS Navigation -  Algorithms calculate the fastest route and estimate travel time. E-commerce -  Algorithms recommend products based on browsing history. 04/09/24

7. Algorithms in Industry Algorithms play a crucial role in various industries: Finance -  Algorithms analyse market trends and manage investments. Healthcare -  Algorithms assist in diagnosis and treatment planning. E-commerce -  Algorithms optimize supply chain and inventory management. 04/09/24

8. Why Study Algorithms? Algorithms are the backbone of software development and technology. They enable computers to process data, make decisions, and solve problems. Understanding algorithms helps in developing efficient and effective software solutions. 04/09/24

9. Algorithm: Making a Cup of Tea Start Begin with a clean kettle and a cup. Boil Water Fill the kettle with water and turn it on to boil. Prepare the Cup Place a tea bag in the cup. Pour Water Once the water boils, pour it into the cup over the tea bag. Steep the Tea Let the tea steep for 3-5 minutes, depending on desired strength. Remove Tea Bag Take out the tea bag and discard it. Add Condiments Add sugar, milk, or lemon if desired. End The tea is ready to drink. Characteristics Demonstrated: Finite:  The process has a clear start and end. Precise:  Each step is specific (e.g., "boil water," "steep for 3-5 minutes"). Effective:  Assuming we have a kettle and tea, this can be done efficiently. Input/Output:  Input (water, tea bag), Output (cup of tea). 04/09/24

10. Algorithm: Adding Two Numbers You want to add two numbers, 3 and 5, to get the sum. Start Take two numbers: 3 and 5. Add the Numbers Perform the addition: 3 + 5. Output the Result The sum is 8. End The process is complete. Characteristics Demonstrated: Finite:  The addition has a clear start and end. Precise:  The operation (addition) is straightforward. Effective:  The addition is performed immediately. Input/Output:  Input (numbers 3 and 5), Output (sum 8). 04/09/24

11. Algorithm: Sorting a List of Numbers Problem:  Sort a list of numbers: [5, 2, 9, 1, 5, 6]. Start Begin with the list: [5, 2, 9, 1, 5, 6]. Compare Adjacent Elements Compare the first two elements (5 and 2). If the first is greater than the second, swap them. Repeat for the Next Pair Move to the next pair (now 5 and 9) and repeat step 2. Continue this process to the end of the list. End of Pass After reaching the end of the list, if any swaps were made, repeat the entire process. If no swaps were made, the list is sorted. Output the Sorted List Once no more swaps are needed, output the sorted list. End The sorting process is complete. 04/09/24

12. Algorithm: Sorting a List of Numbers Characteristics Demonstrated: Finite:  The algorithm ends once the list is sorted. Precise:  Each comparison and swap is clearly defined. Effective:  It works, although not the most efficient for large lists (introduces concept of efficiency). 04/09/24

13. Multiple Algorithms for a Single Problem A single problem can often be solved by more than one algorithm. Each algorithm may differ in approach, efficiency, and complexity.  Understanding various algorithms helps in choosing the best one based on specific needs and constraints. 04/09/24

14. Find the Sum of the First n Natural Numbers Natural Numbers : 1, 2, 3, 4, ... Goal : Calculate the sum S of the first n natural numbers. 04/09/24

15. Method 1: Iterative Approach How It Works : Start with a sum of 0. Add each number from 1 to n to the sum. Continue until you reach n. To find the sum of the first 5 natural numbers: Start with sum = 0. Add 1: sum = 1. Add 2: sum = 3. Add 3: sum = 6. Add 4: sum = 10. Add 5: sum = 15. Result: 15. Pros : Simple to understand and implement. Cons : Takes more time for large n (O(n) time complexity). 04/09/24

16. Method 2: Mathematical Formula How It Works : Use the formula for the sum of the first n natural numbers:  S=n×(n+1)/2 Example : To find the sum of the first 5 natural numbers: Use the formula: S=5×(5+1)/2=5×6/2=15 Result: 15. Pros : Very fast (O(1) time complexity) and doesn’t require iteration. Cons : Requires knowledge of the formula. 04/09/24

17. Importance of Efficient Algorithms Speed : Efficient algorithms run faster, especially as input sizes grow. Resource Usage : Saves computing resources like memory and power. Scalability : Handles large datasets or complex problems without crashing. 04/09/24

18. The Need for Algorithm Analysis Predict Performance : Understand how an algorithm performs as inputs grow. Optimize Solutions : Find ways to improve existing algorithms. Choose the Best Approach : Select the right algorithm for the problem. 04/09/24

19. What is Algorithm Analysis? Definition : Algorithm analysis is the process of determining the efficiency of an algorithm in terms of time and space. Purpose : Helps to predict the behaviour of algorithms with different inputs, and guides the choice of the best algorithm for a problem. 04/09/24

20. Algorithm Analysis Time Complexity : Measures the time an algorithm takes to run as a function of the input size. Notations : O(n), O(log n), O(n²), etc. Space Complexity : Measures how much memory an algorithm uses as the input size grows. Example : An algorithm that uses an additional array has higher space complexity. 04/09/24

21. Cost Comparison: Time vs. Space Hardware Advancements : Memory (RAM) is relatively cheap and plentiful, but time (speed) cannot be easily bought. Example : Upgrading hardware can increase space, but not necessarily improve algorithm speed. Impact on Performance : A slight increase in space complexity is often acceptable if it significantly reduces time complexity. Example : Using a hash table (more space) for faster lookups compared to a list. 04/09/24

22. When Time Complexity Matters Most Real-Time Systems : Systems that must respond quickly (e.g., video games, financial trading platforms) prioritize speed. Example : In gaming, lag caused by slow algorithms can ruin the experience. Big Data Applications : Handling large datasets efficiently is crucial. Example : Data processing in companies like Google or Facebook, where seconds of delay can mean millions of dollars lost. 04/09/24

23. When Space Complexity Takes Priority Memory-Constrained Environments : In embedded systems or mobile devices, space is limited. Example : Software for IoT devices with very limited RAM. Cloud Storage : Storing data in the cloud can be costly, so efficient space usage is important to reduce costs. 04/09/24

24. Balancing Time and Space Complexity Trade-Offs : Sometimes, a balance must be found between time and space complexity. Example : Algorithms like dynamic programming use extra space ( memoization ) to reduce time complexity. Context Matters : The importance of time vs. space complexity depends on the specific application and constraints. Example : In some scenarios, saving memory is more critical, but in most modern applications, speed takes precedence. 04/09/24

25. The Primacy of Time Complexity Focus on Time : In most cases, optimizing time complexity has a greater impact on performance. Consider the Context : Always analyse both time and space, but prioritize time in most general-purpose applications. Efficiency Matters : Efficient algorithms improve user experience, scalability, and overall system performance. 04/09/24

26. Time Complexity of a Simple Loop Problem : Print numbers from 1 to  n . Code: def print_numbers (n): for i in range(1, n+1): print( i ) 04/09/24

27. Time Complexity of a Simple Loop Time Complexity : Step 1 : Identify the basic operation: print( i ). Step 2 : Determine how many times the basic operation is executed. The for loop runs n times. Time Complexity : Since the loop runs n times, the time complexity is  O(n) . Space Complexity : Step 1 : Identify the space used by variables. The function uses a single integer variable  i  and input n. Step 2 : Since the space used is independent of n and does not grow with input size, the space complexity is  O(1) . 04/09/24

28. Thank You  04/09/24