algorithm design.pptx

Algorithm Design

1. algorithm design

2. activity Choose 5 random numbers from 1-9. The numbers should not be arranged consecutively.

3. What are the classifications of design approaches? What are the classifications of other classifications? Where does this bubble sorting fall into? Why do you think it is sorting algorithm? How does this bubble sorting helps you in solving? Why is it important to know bubble sorting method?

4. What is computational thinking? What are the elements of computational thinking? What is algorithm?

5. Classroom norms Treat everyone with respect. Listen to others. Do your best to be successful.

6. 123, arrange me! Arrange the procedures properly. Use numbers (1,2,3,4,5, …) only.

7. 123, arrange me! Group 1: Washing clothes Group 2: Fixing a broken table Group 3: Going to school Group 4: Brushing your teeth Group 5: Washing dishes

8. 123, arrange me! What are the procedures you arranged? Does following procedures necessary? What do es following procedures do in our daily life? What do you think is our topic for today?

9. Checking of activity

10. Learning objectives At the end of the lesson the students are able to: Determine and explain the classifications of algorithm design; Illustrate the categories of implementation method and design method through venn diagram, fishbone, diagram, table, and example algorithms; and Appreciate the importance of solving problems in our daily activities.

11. Activity time!

12. The class will be divided into 5 (five) groups. You will i dentify the classifications of Implementation Method and Design Method. Group 1: make a Venn Diagram of Design Method Group 2: fill in the Table of description in Implementation Method Group 3: make a fishbone diagram of Design Method Group 4 : give example algorithms of Implementation Method Group 5: explain the importance of Implementation Method and Design Method. The classifications will be shown via PowerPoint Presentation. 10 minutes to do the activity. Presentation of the output will follow.

13. Rubric for the activity

14. Greedy method At each step, decision is made to choose the local optimum, without thinking about the future consequences Example: Fractional Knapsack and Activity Selection

15. Branch and bound This technique is very useful in solving combinatorial optimization problem that have  multiple solutions  and we are interested in find the most optimum solution. In this approach, the entire solution space is represented in the form of a state space tree.   Example:  Job sequencing and Travelling salesman problem.

16. Recursion or iteration Recursive algorithm is an algorithm which calls itself again and again until a base condition is achieved. Iterative algorithm use loops and/or data structures like stacks, qeues to solv e any problem. Every recursive solution can be implemented as an iterative solution and vice versa.

17. Serial or parallel or distributed algorithms Serial algorithms, one instruction is executed at a time. Parallel algorithms are those in which we divide the problem into subproblems and execute them on different processors. Distributed algorithms are parallel algorithms that are distributed on different machines.

18. Dynamic programming This strategy is similar to divide and conquer, the difference is that whenever we have recursive function calls with the same result, instead of calling them again we try to store the result in a data structure in the form of a table and retrieve the results from the table. Example: 0-1Knapsack and subset-sum problem

19. linear programming there are inequalities in terms of inputs and maximizing or minimizing some linear functions of inputs.  Example:  Maximum flow or Directed Graph

20. Reduction (transform ang conquer) In this method, we solve a difficult problem by transforming it into a known problem for which we have an optimal solution. Basically, the goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithms. 

21. Divide and conquer This strategy involves dividing the problem into sub-problem, recursively solving them, ang then recombining them for the final answer. Example: Merge sort and Quicksort

22. backtracking This technique is very useful in solving combinatorial problems that have  a single unique solution . Where we have to find the correct combination of steps that lead to fulfilment of the task.   Example:  N-queens problem

23. Exact or approximate Exact algorithm are algorithms that are capable of finding an optimal solution for any problem are known. Approximate algorithms are the type of algorithms that find the result as an average outcome of sub outcomes to a problem.

24. Checking of output

25. analysis

26. Based on the activity… How did you find the activity? What did you feel while doing the activity? How did you come up with the result of your activity? What is the importance of teamwork/cooperation in group activity? What are the topics shown on your activity? What is algorithm?

27. What do you think are the classifications for Implementation Method? What are the classifications for Design method? Which of the following classifications greatly impacts you as a student? Which of these classifications can you apply in your daily life? How can we apply algorithm in our daily life? Why is it important to follow procedures?

28. abstraction

29. What is algorithm? a procedure to solve a particular problem in a finite number of steps for a finite-sized input.

30. Classifications of algorithms: Implementation Method Design Method Design Approaches Other Classifications

31. Importance of algorithms: Organization Problem solving Performance comparison Reusability Research

32. organization A lgorithms can be very complex and by classifying them, it becomes easier to organize, understand, and compare different algorithms.

33. Problem solving Different problems require different algorithms, and by having a classification, it can help identify the best algorithm for a particular problem.

34. Performance comparison By classifying algorithms, it is possible to compare their performance in terms of time and space complexity, making it easier to choose the best algorithm for a particular use case.

35. reusability By classifying algorithms, it becomes easier to re-use existing algorithms for similar problems, thereby reducing development time and improving efficiency.

36. research Classifying algorithms is essential for research and development in computer science, as it helps to identify new algorithms and improve existing ones.

37. implementation method: Recursion or Iteration Exact or Approximate Serial or Parallel or Distributed Algorithms

38. Recursion or iteration Recursive algorithm is an algorithm which calls itself again and again until a base condition is achieved. Iterative algorithm use loops and/or data structures like stacks, qeues to solv e any problem. Every recursive solution can be implemented as an iterative solution and vice versa.

39. Exact or approximate Exact algorithm are algorithms that are capable of finding an optimal solution for any problem are known. Approximate algorithms are the type of algorithms that find the result as an average outcome of sub outcomes to a problem.

40. Serial or parallel or distributed algorithms Serial algorithms, one instruction is executed at a time. Parallel algorithms are those in which we divide the problem into subproblems and execute them on different processors. Distributed algorithms are parallel algorithms that are distributed on different machines.

41. design method Greedy Method Divide and Conquer Dynamic Programming Linear Programming Reduction (Transform and Conquer) Backtracking Branch and Bound

42. Greedy method At each step, decision is made to choose the local optimum, without thinking about the future consequences Example: Fractional Knapsack and Activity Selection

43. Divide and conquer This strategy involves dividing the problem into sub-problem, recursively solving them, ang then recombining them for the final answer. Example: Merge sort and Quicksort

44. Dynamic programming This strategy is similar to divide and conquer, the difference is that whenever we have recursive function calls with the same result, instead of calling them again we try to store the result in a data structure in the form of a table and retrieve the results from the table. Thus, the overall time complexity is reduced. “Dynamic” means we dynamically decide, whether to call a function or retrieve values from the table.  Example: 0-1Knapsack and subset-sum problem

45. linear programming there are inequalities in terms of inputs and maximizing or minimizing some linear functions of inputs.  Example:  Maximum flow or Directed Graph

46. Reduction (transform ang conquer) In this method, we solve a difficult problem by transforming it into a known problem for which we have an optimal solution. Basically, the goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithms.  Example:  Selection algorithm for finding the median in a list involves first sorting the list and then finding out the middle element in the sorted list. These techniques are also called  transform and conquer.

47. backtracking This technique is very useful in solving combinatorial problems that have  a single unique solution . Where we have to find the correct combination of steps that lead to fulfillment of the task.  Such problems have multiple stages and there are multiple options at each stage. This approach is based on exploring each available option at every stage one-by-one. While exploring an option if a point is reached that doesn’t seem to lead to the solution, the program control backtracks one step, and starts exploring the next option. In this way, the program explores all possible course of actions and finds the route that leads to the solution.   Example:  N-queens problem

48. Branch and bound This technique is very useful in solving combinatorial optimization problem that have  multiple solutions  and we are interested in find the most optimum solution. In this approach, the entire solution space is represented in the form of a state space tree. As the program progresses each state combination is explored, and the previous solution is replaced by new one if it is not the optimal than the current solution.  Example:  Job sequencing and Travelling salesman problem.

49. Formative practice Based on your understanding, arrange the classroom norms according to the most important to the least. Treat everyone with respect. Listen to others. Do you best to be successful.

50. application

51. Based on what you have learned, choose an activity and create a procedure for: Making a breakfast Doing Laundry Planning Your Day Packing for a Trip

52. Rubric for the activity 5 (Exceeds Expectation) 4 (Meets Expectation) 3 (Below Expectations) 1 (Not Acceptable) Appropriate use of words So clear and complete Correct words Some notations are incorrect and has misspelled words Incorrect words Flow of process presented So simple and clear. The design is understandable to all intended readers Clear and complete Incomplete or not well designed Unclear or poorly designed

53. Directions: Read the questions carefully and write the letter only. Do this in your activity notebook. Evaluation

54. Which design method involvesbreaking a problem into smaller sub-problems that can be solved recursively? Divide and Conquer Dynamic Programming Backtraking Greedy

55. 2. Which design method involves building solutions incrementally by making decisions at each step that optimize the overall objective? Divide and Conquer Dynamic Programming Backtraking Greedy

56. 3. Which design method involves exploring all possible solutions to a problem by constructing a tree of possibilities? Divide and Conquer Dynamic Programming Backtraking Greedy

57. 4. Which design method involves breaking a problem into smaller sub-problems and storing solutions to avoid repeated calculations? Divide and Conquer Dynamic Programming Backtraking Greedy

58. 5. Which design method is used for finding the shortest path between nodes in a graph? Divide and Conquer Dynamic Programming Backtraking Greedy

59. 6. What classification of implementation method calls itself again and again until a base condition is achieved? Exact or approximate Recursion or iteration Serial or parallel Branch and bound

60. 7. What algorithm that allows one instruction is executed at a time? Distributed Parallel Serial Recursion

61. 8. What algorithm divides the problem into subproblems and execute them on different processors? Distributed Parallel Serial Recursion

62. 9. What classification of implementation method that algorithms are capable of finding an optimal solution for any problem. Exact Recursion Serial Parallel

63. 10. What algorithm is it if the parallel algorithms are distributed on different machines? Distributed Parallel Serial Recursion

64. assignment

65. Identify the classifications of the following: Design Approaches Other Classifications

66. Competitive Landscape

67. Digital Communications

68. Thank You [email protected]