Section 8.6
Randomness
Algorithm Efficiency
Undecidable Problems
Learning Goals
Students will write and evaluate expressions to generate possible values and determine possible results (AAP-3.E)
Students will understand the applications of randomness in music
Students will learn how to implement musical randomness in a complementary way
Students will explain the difference between algorithms that run in reasonable time and those that do not (AAP-4.A)
Students will explain the existence of undecidable problems in computer science (AAP-4.B)
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.
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 path 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.
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-4.A.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.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.
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.
Objectives and Description
The objective of this lesson is to introduce students to the concept of randomness, both in computer science and in music, in order to give them an additional tool for composing their songs for the unit task. Students will apply shuffleString() to randomize drum beats and learn about composition techniques that can be used to incorporate randomized elements into their songs more cleanly. They will also be given an overview of the pseudocode for random number generation used in the AP exam.
Activities
Activity 8.6.1 (10 minutes)
Students will flip a real or virtual coin 16 times. Each result will correspond to a character to be added to a string
Heads will correspond to 0
Tails will correspond to -
This string will be used as a beat string in the following script
Allow time for students to listen to their peers’ scripts and compare with their own
Activity 8.6.2 (40 minutes)
Students will create their own pseudo-randomized drum beat using the shuffleString() function
Include 2-3 tracks that use regular beat strings.
Recommended that students use hi-hat and kick for these.
Include at least 1 track that uses shuffleString() to randomize the drum beat.
Recommended that students use the snare for this.
Add 2-3 sounds with fitMedia()
More practice/exploration time for students
Encourage students to try sounds/genres they have not used before.
Have a few students share their scripts with you and play them for the class. Run and re-randomize the drum beats several times to see how changes in the drum beat affect how the melodic components of the song interact with it.
Activity 8.6.3 (30 minutes)
Navigate to AP Classroom and watch 3.17: Daily Video 1, "Algorithmic Efficiency."
Have students take out a sheet of paper to calculate the efficiency time for the four algorithms at 11:04 in the video. One of them will be unreasonable. The video will show the answer when you start it again.
Pause the video again at 12:05. This time students will choose two algorithms that run in a reasonable amount of time. This is similar to what students will see on the AP Exam where they have to choose two answers.
Have students explain the difference between algorithms that run in a reasonable time and those that do not.
Explain that 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.
Activity 8.6.4 (15 Minutes)
Watch "The Halting Problem: The Unsolvable Problem" by lydia. The key takeaways:
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?”).
An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.
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.
Have students explain the existence of undecidable problems in computer science.
Resources
8.6.1: Coin Flip Activity Template Script (Student Resource)
8.6.3: AP Classroom 3.17: Daily Video 1, "Algorithmic Efficiency" (Student and Teacher Resource)