Can Computers Solve Every Problem?
Summary
Material
- Day 28 PowerPoint deck
- Computer Problem Solving handout
- Computer Problem Solving handout in Word
- Resource Links (for teacher, but can be shared with students if you prefer)
Instructional Activities and Classroom Assessments
- Introduction Simulations (15 minutes)
- Jigsaw Activity (35 minutes)
- Reflection/Homework
Learning Objectives
- AAP-3.F For simulations:
- a. Explain how computers can be used to represent real-world phenomena or outcomes.
- b. Compare simulations with real-world contexts.
- AAP-4.A For determining the efficiency of an algorithm:
- a. Explain the difference between algorithms that run in reasonable time and those that do not.
- b. Identify situations where a heuristic solution may be more appropriate. 1.D
- AAP-4.B Explain the existence of undecidable problems in computer science. 1.A
Essential Knowledge
- AAP-3.F.1 Simulations are abstractions of more complex objects or phenomena for a specific purpose.
- AAP-3.F.2 A simulation is a representation that uses varying sets of values to reflect the changing state of a phenomenon.
- AAP-3.F.3 Simulations often mimic real-world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraints of the real world.
- AAP-3.F.4 The process of developing an abstract simulation involves removing specific details or simplifying functionality.
- AAP-3.F.5 Simulations can contain bias derived from the choices of real-world elements that were included or excluded.
- AAP-3.F.6 Simulations are most useful when real-world events are impractical for experiments (e.g., too big, too small, too fast, too slow, too expensive, and too dangerous).
- AAP-3.F.7 Simulations facilitate the formulation and refinement of hypotheses related to the objects or phenomena under consideration.
- AAP-3.F.8 Random number generators can be used to simulate the variability that exists in the real world.
- AAP-4.A.1 A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2, 3, 1, 7) is an instance of the problem.
- AAP-4.A.2 A decision problem is a problem with a yes/no answer (e.g. is there a path from A to B?). An optimization problem is a problem with the goal of finding the "best" solution among many (e.g., what is the shortest part from A to B?)
- AAP-4.A.3 Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input. EXCLUSION STATEMENT (EK AAP-4.A.): Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.
- AAP-4.A.4 An algorithm's efficiency is determined through formal or mathematical reasoning.
- AAP-4.A.5 An algorithm's efficiency can be informally measured by determining the number of times a statement or group of statements executes.
- AAP-A.4.6 Different correct algorithms for the same problem can have different efficiencies.
- AAP-4.A.7 Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
- AAP-4.A.8 Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.
- AAP-4.A.9 A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.
- AAP-4.B.1 A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., “Is the number even?”).
- AAP-4.B.2 An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes or-no answer.
X EXCLUSION STATEMENT (EK AAP-4.B.2): Determining whether a given problem is undecidable is outside the scope of this course and the AP Exam. - AAP-4.B.3 An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.
DetaILS
1. Can Computers Solve Every Problem introduction (15 minutes)
- Discuss simulations and how have simulations helped in solving problems.
- Discuss the different types of problems solved algorithmically.
- Explain the concepts related to the efficiency of solving problems.
- Explain what Heuristic algorithms are.
- Distinguish between decidable vs. undecidable problems.
2. Jigsaw (35 minutes)
- Place students in groups of three.
- One person in each group will research:
- Simulations
- Heuristic algorithms
- Undecidable problem
- Encourage students to add the summaries of their research on their group's Computer Problem Solving page.
- Each group member will share their finding with the class.
3. Reflection/Homework
If you run out of time, you may also assign this as individual homework. Students should complete their reflection in their OneNote.
- NYU has a course on heuristic problem solving. The professor's goal is to develop ominheurusts. What does that mean to you?