One in which no algorithm can be constructed that always leads to a correct yes-or-no answer

Here is an update based on our 12/29/15 meeting. --MF

• LO 2.3.1 Use models and simulations to represent phenomena. [P3]
  • EK 2.3.1A Models and simulations are simplified representations of more complex objects or phenomena.
  • EK 2.3.1B Models may use different abstractions or levels of abstraction depending on the objects or phenomena being posed.
  • EK 2.3.1C Models often omit unnecessary features of the objects or phenomena that are being modeled.
  • EK 2.3.1D Simulations mimic real-world events without the cost or danger of building and testing the phenomena in the real world.
• LO 2.3.2 Use models and simulations to formulate, refine, and test hypotheses. [P3]
  • EK 2.3.2A Models and simulations facilitate the formulation and refinement of hypotheses related to the objects or phenomena under considerations.
  • EK 2.3.2B Hypotheses are formulated to explain the objects or phenomena being modeled.
  • EK 2.3.2C Hypotheses are refined by examining the insights that models and simulations provide in the objects or phenomena.
  • EK 2.3.2D The results of simulations may generate new knowledge and new hypotheses related to the phenomena being modeled.
  • EK 2.3.2E Simulations allow hypotheses to be tested without the constraints of the real world.
  • EK 2.3.2F Simulations can facilitate extensive and rapid testing of models.
  • EK 2.3.2G The time required for simulations is impacted by the level of detail and quality of the models and the software and hardware used for the simulation.
  • EK 2.3.2H Rapid and extensive testing allows models to be changed to accurately reflect the objects or phenomena being modeled.
• LO 3.1.2 Collaborate when processing information to gain insight and knowledge. [P6]
  • EK 3.1.2A Collaboration is an important part of solving data-driven problems.
  • EK 3.1.2B Collaboration facilitates solving computational problems by applying multiple perspectives, experiences, and skill sets.
  • EK 3.1.2C Communication between participants working on data-driven problems gives rise to enhanced insights and knowledge.
  • EK 3.1.2D Collaboration in developing hypotheses and questions, and in testing hypotheses and answering questions, about data helps participants gain insight and knowledge.
  • EK 3.1.2E Collaborating face-to-face and using online collaborative tools can facilitate processing information to gain insight and knowledge.
  • EK 3.1.2F Investigating large data sets collaboratively can lead to insight and knowledge not obtained when working alone.
• LO 4.2.1 Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]
  • EXCLUSION STATEMENT (for LO 4.2.1): Any discussion of nondeterministic polynomial (NP) is beyond the scope of this course and the AP Exam.
  • EK 4.2.1A Many problems can be solved in a reasonable time.
  • EK 4.2.1B Reasonable time means that as the input size grows, the number of steps the algorithm takes is proportional to the square (or cube, fourth power, fifth power, etc.) of the size of the input.
  • EK 4.2.1C Some problems cannot be solved in a reasonable time, even for small input sizes.
  • EK 4.2.1D Some problems can be solved but not in a reasonable time. In these cases, heuristic approaches may be helpful to find solutions in reasonable time.
• LO 4.2.2 Explain the difference between solvable and unsolvable problems in computer science. [P1]
  • EXCLUSION STATEMENT (for LO 4.2.2): Determining whether a given problem is solvable or unsolvable is beyond the scope of this course and the AP Exam.
  • EK 4.2.2A A heuristic is a technique that may allow us to find an approximate solution when typical methods fail to find an exact solution.
  • EK 4.2.2B Heuristics may be helpful for finding an approximate solution more quickly when exact methods are too slow.
    • EXCLUSION STATEMENT (for EK 4.2.2B): Specific heuristic solutions are beyond the scope of this course and the AP Exam.
  • EK 4.2.2C Some optimization problems such as "find the best" or "find the smallest" cannot be solved in a reasonable time but approximations to the optimal solution can.
  • EK 4.2.2D Some problems cannot be solved using any algorithm.
• LO 4.2.3 Explain the existence of undecidable problems in computer science. [P1]
  • EK 4.2.3A An undecidable problem may have instances that have an algorithmic solution, but there is not algorithmic solution that solves all instances of the problem.
  • EK 4.2.3B A decidable problem is one in which an algorithm can be constructed to answer "yes" or "no" for all inputs (e.g., "is the number even?").
  • EK 4.2.3C An undecidable problem is one in which no algorithm can be constructed that always leads to a correct yes-or-no answer.
    • EXCLUSION STATEMENT (for EK 4.2.3C): Determining whether a given problem is undecidable is beyond the scope of this course and the AP Exam.
• LO 4.2.4 Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]
  • EK 4.2.4A Determining an algorithm's efficiency is done by reasoning formally or mathematically about the algorithm.
  • EK 4.2.4B Empirical analysis of an algorithm is done by implementing the algorithm and running it on different inputs.
  • EK 4.2.4C The correctness of an algorithm is determined by reasoning formally or mathematically about the algorithm, not by testing an implementation of the algorithm.
    • EXCLUSION STATEMENT (for EK 4.2.4C): Formally proving program correctness is beyond the scope of this course and the AP Exam.
  • EK 4.2.4D Different correct algorithms for the same problem can have different efficiencies.
  • EK 4.2.4E Sometimes, more efficient algorithms are more complex.
  • EK 4.2.4F Finding an efficient algorithm for a problem can help solve larger instances of the problem.
  • EK 4.2.4G Efficiency includes both execution time and memory usage.
    • EXCLUSION STATEMENT (for EK 4.2.4G): Formal analysis of algorithms (Big-O) and formal reasoning using mathematics formulas are beyond the scope of this course and the AP Exam.
  • EK 4.2.4H Linear search can be used when searching for an item in any list; binary search can be used only when the list is sorted.
• • EK 5.2.1J Simple algorithms can solve a large set of problems when automated.
  • EK 5.2.1K Improvements in algorithms, hardware, and software increase the kinds of problems and the size of problems solvable by programming.
  • EK 5.3.1M Application program interfaces (APIs) and libraries simplify complex programming tasks.
  • EK 5.3.1N Documentation for an API/library is an important aspect of programming.
  • EK 5.3.1O APIs connect software components, allowing them to communicate.
• LO 7.1.2 Explain how people participate in a problem-solving process that scales. [P4]
  • EK 7.1.2A Distributed solutions must scale to solve some problems.
  • EK 7.1.2B Science has been impacted by using scale and "citizen science" to solve scientific problems using home computers in scientific research.
  • EK 7.1.2C Human computation harnesses contributions from many humans to solve problems related to digital data and the Web.
  • EK 7.1.2D Human capabilities are enhanced by digitally enabled collaboration.
  • EK 7.1.2E Some online services use the contributions of many people to benefit both individuals and society.
  • EK 7.1.2F Crowdsourcing offers new models for collaboration, such as connected people with jobs and businesses with funding.
  • EK 7.1.2G The move from desktop computers to a proliferation of always-on mobile computers is leading to new applications.
• LO 7.2.1 Explain how computing has impacted innovations in other fields. [P1]
  • EK 7.2.1A Machine learning and data mining have enabled innovation in medicine, business, and science.
  • EK 7.2.1B Scientific computing has enabled innovation in science and business.
  • EK 7.2.1C Computing enables innovation by providing the ability to access and share information.
  • EK 7.2.1D Open access and Creative Commons have enabled broad access to digital information.
  • EK 7.2.1E Open and curated scientific databases have benefited scientific researchers.
  • EK 7.2.1F Moore's law has encouraged industries that use computers to effectively plan future research and development based on anticipated increases in computing power.
  • EK 7.2.1G Advances in computing as an enabling technology have generated and increased the creativity in other fields.