DAA_Day0 (2).pptx for the presentation of the daa

Daa

1. Design And Analysis Of Algorithms CSE-230 #LifeKoKaroLift

2. Course : DESIGN AND ANALYSIS OF ALGORITHMS Lecture On :  Algorithm Analysis Instructor : Er. Anshika Gupta

3. 23/05/19 Footer Practice in teams of 4 students Industry expert mentoring to learn better Get personalised feedback for improvements Poll 1 3 On a scale of 1-5, Data Structures?

4. 23/05/19 Footer Practice in teams of 4 students Industry expert mentoring to learn better Get personalised feedback for improvements Poll 2 4 On a scale of 1-5, how familiar are you with Algorithms?

5. Today’s Agenda Data Science Certification Program Course Details Course Assessment Model   What is Algorithm Characteristics of an algorithm Efficient Algorithms Parameters of Analysis Growth Order of Algorithms Time & Space Complexity Asymptotic Notations Cases of Analysis Complexity Functions

6. L    T     P   –    3   0   2      [Three lectures/week] References 1. Introduction To The Design & Analysis Of Algorithms By Anany Levitin, Pearson 2. Algorithm Design by Jon Kleinberg And Eva Tardos, Pearson Course Details

7. Marks break up Attendance                                                          05  CA ( Best 2 out of 3 CA)                      25 MTE 20 ETP (Platform Based Coding + Viva)                  50  Total                                                                    100  Course Assessment Model

8.     Course Outcomes Describe the basic techniques of analyzing the algorithms using asymptotic notations. Determine how to computer the complexity of algorithms. Understand the algorithms of various sorting techniques.

9.  Course Outcomes Illustrate the use of divide and conquer technique by using quick sort and merge sort algorithms. Explain greedy technique to solve the problems in an optimized way Discuss the optimized dynamic programming technique with relevant examples

10. PO1  Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals, and an engineering specialization to the solution of complex engineering problems.  PO2  Problem analysis: Identify, formulate, research literature, and analyze complex engineering problems reaching substantiated conclusions using first principles of mathematics, natural sciences, and engineering sciences.  PO3  Design/development of solutions: Design solutions for complex engineering problems and design system components or processes that meet the specified needs with appropriate consideration for the public health and safety, and the cultural, societal, and environmental considerations.  Program Outcomes

11. PO4  Conduct investigations of complex problems: Use research-based knowledge and research methods including design of experiments, analysis and interpretation of data, and synthesis of the information to provide valid conclusions.   PO5  Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern engineering and IT tools including prediction and modeling to complex engineering activities with an understanding of the limitations.  PO6  The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to the professional engineering practice.   Program Outcomes

12. PO7  Environment and sustainability::Understand the impact of the professional engineering solutions in societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable development.  PO8  Ethics::Apply ethical principles and commit to professional ethics and responsibilities and norms of the engineering practice.  PO9  Individual and team work::Function effectively as an individual, and as a member or leader in diverse teams, and in multidisciplinary settings. Program Outcomes

13. PO10  Communication::Communicate effectively on complex engineering activities with the engineering community and with society at large, such as, being able to comprehend and write effective reports and design documentation, make effective presentations, and give and receive clear instructions.  PO11  Project management and finance::Demonstrate knowledge and understanding of the engineering, management principles and apply the same to one’s own work, as a member or a leader in a team, manage projects efficiently in respective disciplines and multidisciplinary environments after consideration of economic and financial factors.  PO12  Life-long learning::Recognize the need for, and have the preparation and ability to engage in independent and life-long learning in the broadest context of technological change.  Program Outcomes

14. Unit I: Algorithm Analysis Examining the efficiency of algorithms through parameters such as complexity functions, asymptotic notations, and Big O functions. Balancing the trade-off between the time and space requirements of an algorithm to optimize overall performance.. Evaluating and comparing the execution times of different algorithms to understand their efficiency in solving specific problems. Fibonacci Sequence: A series of numbers where each number is the sum of the two preceding ones. Recursion Course Contents

15. Unit II: Searching & Sorting I Fundamentals of searching algorithms and their significance. Understanding linear search and implementing it using Java. Analyzing the time complexity associated with linear search. Exploring the concept of divide and conquer as a fundamental algorithmic paradigm. Understanding binary search and implementing it using Java. Analyzing the time complexity associated with binary search. Course Contents

16. Unit III: Searching & Sorting II Learning about the bubble sort algorithm and implementing it in Java. Analyzing the time complexity of the bubble sort algorithm. Understanding the selection sort algorithm and implementing it in Java. Analyzing the time complexity associated with the selection sort algorithm. Learning about the insertion sort algorithm and implementing it in Java. Analyzing the time complexity associated with the insertion sort algorithm. Comparing the characteristics and performance of insertion sort and selection sort algorithms. Course Contents

17. Unit IV: Searching & Sorting III Understanding the merge sort algorithm and implementing it in Java. Analyzing the time complexity of the merge sort algorithm. Learning about the quick sort algorithm and implementing it in Java. Demonstrating the quick sort algorithm using a card game and addressing common doubts related to its implementation. Evaluating and contrasting various sorting algorithms to understand their strengths and weaknesses. Applying sorting algorithms to solve a sample problem related to leaderboard management. Course Contents

18. Unit V: Greedy Algorithms Understanding the concept and application of greedy algorithms. Evaluating the strengths and limitations of using greedy algorithms in problem-solving. Applying greedy algorithms to address scheduling problems efficiently. Utilizing greedy algorithms to solve problems related to graph depth Addressing the knapsack problem using greedy algorithmic approaches. Solving the fractional knapsack problem using greedy algorithms. Applying greedy algorithms to real-world industry problems and providing practical demonstrations of their effectiveness. Course Contents

19. Unit VI: Dynamic Programming Understanding the fundamentals of dynamic programming and its application. Introducing the coin exchange problem as a case study for dynamic programming. Employing the tabulation method in dynamic programming for efficient problem-solving. Writing pseudocode as a high-level description of the dynamic programming solution. Implementing the dynamic programming solution for the coin exchange problem in Java. Course Contents

20. Unit VI: Dynamic Programming Exploring techniques to optimize space complexity in dynamic programming solutions. Applying dynamic programming to optimize the computation of the Fibonacci sequence. Engaging in practical exercises to reinforce understanding and application of dynamic programming concepts. Introducing the edit distance problem as an application of dynamic programming. Implementing dynamic programming to solve the edit distance problem. Applying dynamic programming to the development of a spellchecker. Course Contents

21. Unit VI: Dynamic Programming Utilizing dynamic programming to solve the problem of finding the longest increasing subsequence in a sequence of numbers. Course Contents

22. BURNING questions in mind…  What is an Algorithm?  How to analyze performance of software/programs? How important is to design an efficient algorithm?  How to identify the best approach? The hitch ...

23. Introduction to Algorithms Algorithms are a part of our day-to-day life. A simple example is when you call the elevator by the press of a single button. But what happens if multiple floors press the button at the same time?

24. What is an Algorithm? An algorithm is a sequence of finite, unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time & space .

25. Characteristics of Algorithms Not all procedures can be called an algorithm. An algorithm should have the following characteristics − Unambiguous − Algorithm should be clear and unambiguous . Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. Input − An algorithm should have 0 or more well-defined inputs. Output − An algorithm should have 1 or more well-defined outputs and should match the desired output.

26. Characteristics of Algorithms (contd.) Finiteness − Algorithms must terminate after a finite number of steps . Feasibility − Should be feasible with the available resources. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code

27. Why are Algorithms Important? Every computer program is made of Algorithms & Data Structures. So, understanding them becomes important. Algorithms provide a systematic way to solve problems and perform tasks in the most resource-efficient manner. Once an algorithm is developed and proven effective, it can be reused in various contexts without the need to redesign the entire solution. This promotes code reusability and helps in building modular and scalable software systems.

28. Parameters Of Algorithm Efficiency We need to ask these 2 questions: What is an efficient algorithm? What metric is used to determine it?

29. Parameters Of Algorithmic Efficiency What about searching for a particular book from a pile of books arranged alphabetically? Suppose we wish to find the book “How to overcome the fear of coding?” Should we start looking from the beginning of the alphabet, i.e. letter “A”? Or should we start looking directly from the letter “H”? Which searching ALGORITHM seems to be more EFFICIENT? Which searching ALGORITHM seems to be more EFFICIENT?

30. Parameters Of Algorithmic Efficiency What if you have to swap all the books of the two shelves now? One way is to start loading all the books of the top shelf into an empty shelf and then transfer all lower shelf books to the upper one and then fill the lower shelf books with the books initially transferred from the top shelf. Can you think of another way?

31. Parameters Of Algorithmic Efficiency Should we try swapping one book from each shelf with each other till all the books are swapped? Which swapping ALGORITHM seems to be more EFFICIENT? What if there is no empty shelf available?

32. Parameters Of Algorithm Efficiency We generally use 2 performance metrics to determine the efficiency of an algorithm: Running time : no. of steps taken by algorithm Memory space : amount of space required to run the algorithm The time taken and the memory space required to execute an algorithm are calculated as the functions of the input size . Since you typically do not know the input size beforehand, you simply use the variable ‘n’ to represent the potential input size of the algorithm. We tend to consider the worst case, i.e. the specific case in which the instruction set is executed a maximum number of times.

33. Parameters for Algorithm Efficiency How do you calculate the time taken to execute an algorithm? Each instruction in an algorithm takes a specific amount of time to execute, and a certain instruction set is executed for more than once, i.e., the instruction set inside a 'for' or 'while' loop. To analyze an algorithm, you must calculate the number of times for which an instruction set is executed with respect to the input size (n) rather than the exact time values. This is because the time taken to execute an algorithm depends on various external factors such as processor speed, compiler, etc. because these external factors can vary from computer to computer.

34. Growth Functions Definition: Growth functions describe how a quantity changes as its input increases. Widely used in various domains to analyze and understand the behavior of algorithms, systems, and processes. Growth functions are crucial for understanding the scalability and efficiency of algorithms and systems. Wise selection based on the problem at hand is vital for optimal performance.

35. Time Complexity of an Algorithm Time Complexity is a programming term that quantifies the amount of time it takes a sequence of code or an algorithm to process or execute in proportion to size and cost of input. It does not look at an algorithm’s overall execution time but rather provides data on variation in execution time when the number of operations in an algorithm increases or decreases .

36. Aymptotic Notations for Time/Space Complexity Asymptotic analysis is a method used in computer science and mathematics to describe the behavior of algorithms and functions as their input size approaches infinity . It focuses on how the performance of an algorithm or the growth rate of a function changes with large input sizes . The key asymptotic notations used in this analysis are: Big O (O) Omega (Ω) Theta (Θ)

37. Aymptotic Notations for Time/Space Complexity Big O Big O refers to the order of growth of a function; essentially, the growth of any complexity function for large input size(n) values depends on the most significant term of the function. So, less significant terms are dropped from the function to calculate the Big O.

38. Aymptotic Notations for Time/Space Complexity Big Omega Big Omega indicates the lower bound of the running time of an algorithm. In the earlier scenario of opening a lock, if you were able to undo the lock on your first attempt itself, then the first attempt will be the lower bound. In any other case, the number of attempts to unlock will be greater than the lower bound. When calculating Big Omega, the time complexity function of an algorithm is greater than or equal to the lower bound.

39. Aymptotic Notations for Time/Space Complexity Big Theta Big Theta represents an in-between case, bounded both above (upper bound) and below (lower bound) the running time of an algorithm.

40. Algorithm Analysis: Cases There are three cases in the analysis of an algorithm, which are as follows: Best case Average case Worst Case The lower bound on the time taken by an algorithm is the best case . The number of instructions that get executed in the best case is constant. The upper bound of the time taken by an algorithm is the worst case . For most of the times, the worst-case time complexity of an algorithm is used for the algorithm analysis because the worst-case time complexity guarantees the upper bound of the time that the algorithm takes, i.e., the maximum time taken by the algorithm.

41. Algorithm Analysis: Cases Best Case When the element to be searched is present at the first position 1 7 4 9 2 8 6 3 5 How many iterations will it take if we search for 1?

42. Algorithm Analysis: Cases Worst Case When the element to be searched is present at the last position When the element to be searched is not present How many iterations will it take if we search for 5? Is it equal to the number of iterations taken to search 0 in the array? 1 7 4 9 2 8 6 3 5

43. Algorithm Analysis: Cases Average Case Consider all possible different types of input data and calculate the time taken for all those inputs Find the arithmetic mean of all times. The obtained value is the time taken in the average case.  Can you find the exact value of the average number of iterations? If the array size is N, can you find a general formula for the average number of iterations using this algorithm? 1 7 4 9 2 8 6 3 5

44. Algorithm Analysis: Cases Average of time taken by the algorithm for all the inputs is the average case.

45. Algorithm Analysis: Cases So what actually IS the difference between Best , Average & Worst Case Time Complexity? Best case refers to the best-case scenario wherein the resources or the time required to perform a given operation is the least. For example, given a simple list and we need to find an whether an element exist inside that list, the best case would occur when the element is found right in the first iteration itself, i.e. in the first shot!

46. Algorithm Analysis: Cases Using the worst-case scenario often gives you the safest guarantee within which the algorithm may work. For example, when designing an algorithm, the safest bet would be to assume that the worst happens and thereby worst-case time analysis comes into picture here. For example, while searching for an element in a very long list of numbers, the worst case would be to assume that the element does not exist inside the list at all and that the procedure needs to check each and every element of that long list to finally conclude that the element does not exist!

47. Algorithm Analysis: Cases While the worst-case scenario is mostly highly useful to determine the performance of an algorithm, it often gives us an overly pessimistic performance overview of an algorithm. A more realistic estimate of the performance of an algorithm would be to use the average case time complexity i.e. to calculate how an algorithm performs on an average.

48. Complexity Functions Consider the following code: public void findDuplicates(int[] id) { System.out.println("Duplicate student id : "); for (int i = 0; i < id.length; i++) { for (int j = i+1; j < id.length; j++){ if (id[i] == id[j]) { System.out.print(id[i] + " "); break; } } }

49. Complexity Functions This instruction set is executed once. Assume that this instruction set takes a constant time of c1 to execute. The outer loop iterates n (array size) times. In the worst case, the inner loop instruction set is executed n - (i + 1) times for each outer loop iteration. In total, it performs n(n-1)/2 steps. Assume that it takes a constant time of c2 to check the if condition and print the duplicate data.

50. Complexity Functions Therefore, the total time taken to execute algorithm 1 for an input size n is as follows: Total time taken to execute algorithm = Time taken for the step 1 + Time taken for step 2 T(n)=c1+c2∗n(n−1)/2 Here, T(n) represents the time complexity; it is the total time taken to execute an algorithm as a function of the input size (n). The time complexity function gives you an idea of how long an algorithm takes to process the output.

51. 23/05/19 Footer Practice in teams of 4 students Industry expert mentoring to learn better Get personalised feedback for improvements Poll 3 3 What is the total number of times for which the inner loop(j) instruction set is executed in the given algorithm?

52. Any Questions?

53. Key Takeaway Course Overview Introduction to Algorithms Asymptotic Notations Data Science Certification Program

54. Thank You! #LifeKoKaroLift