Summary

Big Data has been defined in many different ways. Easy access to large sets of data and the ability to analyze large data sets changes how people make decisions. Students will explore how Big Data can be used to solve real-world problems in their community. After watching a video that explains how Big Data is different from how we have analyzed and used data in the past, students will explore Big Data techniques in online simulations. Students will identify appropriate data source(s) and formulate solvable questions.

Outcomes

• Students will explain how analyzing Big Data is different from the way ordinary data is analyzed.

• Students will describe how computers can make predictions and answer questions through the use of Big Data, storage of data, and processing data.

• Students will synthesize the relationship(s) between causation and correlation.

Overview

Session 1- What is Big Data?

• Getting Started (10 min) - Journal

• Guided Activities (30 min) – Reading and Video

• Wrap Up (10 min) – Group Review

• Homework

Session 2 – Where can big data be used?

• Getting Started (5 min) - Journal

• Guided Activities (15 min) – Processing Big Data

• Independent Activities (25 min) – Online Research

• Wrap Up (5 min) – Exit Slip

• How can computing extend traditional forms of human expression and experience?
• How are vastly different kinds of data, physical phenomena, and mathematical concepts represented on a computer?
• How can computation be employed to help people process data and information to gain insight and knowledge?
• How can computation be employed to facilitate exploration and discovery when working with data?
• What opportunities do large data sets provide for solving problems and creating knowledge?

Reading assignment and video clips for Session 1: 

• Mind-guessing game: http://en.akinator.com/ 
• Random number generator (for choosing students to present): http://www.random.org/ 
• Reading assignment: http://www.foreignaffairs.com/articles/139104/kenneth-neil-cukier-and-viktor-mayer-schoenberger/the-rise-of-big-data
• Moneyball Statistics clip: https://www.youtube.com/watch?v=rMObWsKaIls
   (2:47 mins)
• 3 V's clip: https://www.youtube.com/watch?v=7D1CQ_LOizA 

Possibly useful resource(s) for data collection:

• http://www.gapminder.org/
  
• http://r-dir.com/reference/datasets.html
  
• https://dreamtolearn.com/doc/2HDNJH3XJU6CVGKZ7SDM4MCSW
  
• https://www.kaggle.com (requires an account - but is free)
• http://catalog.data.gov/dataset

Big Data Concepts:

• https://youtube.com/watch?v=RG8R1iXEyPc (16:04 mins) from CS-P Alabama is good background for a teacher to learn more about big data.

Sample data sets (both acquired from http://catalog.data.gov/dataset) :

• FailedBanklist.csv
• Consumer_Complaints.csv

Session 1 - What is Big Data?

Getting Started (10 min) - Journal

Journal: How can a computer gather data from people ? (Think-Pair-Share)

Remind students of the mind guessing game: http://en.akinator.com/ or 20 questions http://www.20q.net/ 

Discuss: How can the computer learn from people when playing one of these games? How many different answers do you think it could possibly know? 

Teacher note: students are not expected to actually play this game during class.

• Students should document in their journal the answer to this question: How does this game store all of the possible answers?
• Ask 3 students to share their answers. (Possible strategies to select a random student: random.com, or pick a random student name stick from a cup.)
• This activity should lead into today’s lesson on how large amounts of data are stored and then accessed as needed in a system.

Guided Activities (30 min) - Reading & Video

Read The Rise of Big Data in chunks: An Introduction to “Big Data” (20 mins) Reading can be found at: http://www.foreignaffairs.com/articles/139104/kenneth-neil-cukier-and-viktor-mayer-schoenberger/the-rise-of-big-data

Break students into groups or pairs and jigsaw the seven units of the reading. Each group is to summarize their section in a tweet sized comment (not more than 140 characters).

Share tweets with the class.

Explain to students that big data is impacting every area of life. By using more data and processing power we can make better decisions. As an illustration, show a clip from the movie Moneyball: (3 mins) https://www.youtube.com/watch?v=rMObWsKaIls
After students watch, they create a journal entries explaining at least two ways data was used to better manage the baseball team. Partners discuss journal entries. Share at least one observation with table groups and then share at least one observation from each group with the class.

Show the first 3-5 minutes of this clip. (It becomes a bit dry, so just show the amount that is appropriate for your students to get the idea): https://www.youtube.com/watch?v=7D1CQ_LOizA

• What are the 3 V's? List some details about each V.

• (at 4:40) What is Hadoop and how is it used?

• Identify appropriate data source and form questions

• Extract data source into format supported by underlying tools

• Normalize data (remove redundancies, irrelevant details)

• Import data into tool

• Perform analysis

• Visualize results

Some other concepts to point out to students if there is time:

Some examples of how big data is used:

• Netflix and Amazon use it to improve user recommendations

• Dominos used it to determine that more people order pizza when it is raining so they now base some of their ad campaigns around weather patterns

• Help police predict when and where crimes will appear

Some examples of how big data was inappropriately used:

• In 2012 Target store's “outing” a teenager’s pregnancy

• In 2012 Google spent 22.5 million on a settlement over allegations that they secretly tracked user’s web surfing

• In 2012 Facebook spent 20 million to settle a lawsuit that alleged that they used user pictures without the user’s knowledge to endorse products that they “liked”

• In 2013 the revelation of the NSA using big data for national security concerns

Wrap Up (10 min) – Group Review

• Place students in groups of 4 where the first student is A, the next is B, etc. Each group creates a single sheet of paper with the letters across the bottom and the numbers 1 - 5 to demonstrate the level of understanding of each concept. Students should plot their understanding for each respective concept (see list below) on the graph. (The file "BigDataSampleDotGraph" in the lesson resources folder shows an example.)
• Collect this graph as a level of student’s understanding of the concepts in the video.
• Review each concept using the notes below.
  • Big data is kind of like drinking water from a fire hose. It's too much to process for a small pipeline…
• A. The three “Vs”: Volume, Variety, and Velocity
• B. Big Data processing steps:

• C. Tools for processing big data:

• Microsoft Excel (or some type of spreadsheet tool - i.e. Calc is another one)
• Hadoop - a well known big data tool, provided by Apache, requires extensive programming knowledge to set up and use
• SAS - provides a more intuitive interface and better graphical representations of data
• Google Prediction API - takes advantage of machine learning to extract meaning from data
• BitDeli - lightweight, easier to use version of Hadoop
• D. Very few restrictions on use of big data
• Companies collect large amounts of data on their customers
• Can be sold to other companies
• Can be sold to the government
• Can be used to “de-anonymize” someone

Homework

Students are to pick three topics they want to research that use big data. It is preferred that these topics relate to something learned this year in the course (e.g., the need for IPv6). Tomorrow, as the students enter class, they will sign up on a list with their chosen topic. Since the students will have three options, it is likely they will get one of their selected topics to research.

Session 2 - Where can Big Data be used?

Getting Started (5 min) - Journal

Journal: Think about you daily and weekly activities. What types of data are being stored about you?

Remind students to think about what they do online, in stores, while in a car, etc.

Guided Activities (10 min) – Processing Big Data

Review the steps to processing Big Data:

1. Identify appropriate data source and form questions
2. Extract data source into format supported by underlying tools
3. Normalize data (remove redundancies, irrelevant details)
4. Import data into tool
5. Perform analysis
6. Visualize results

As a class, walk through these steps using the two files in the lesson resources folder (FailedBanklist.csv & Consumer_Complaints.csv)

Step 1.

Demonstrate how files such as these can be obtained at http://catalog.data.gov/dataset

Formulate questions such as:
Are there any banks that are on both the complaint list and the failed banklist?
Can we make some deductions about banks that may be on both lists? If so, what deductions can we make?

Step 2.

Extract data source into format supported by underlying tools

Open one of these files in Notepad (or some simple editing program such as Notepad++) and demonstrate how the actual data itself is separated by commas, thus the file name “csv” for comma separated value.

Open both files in Microsoft Excel. Complete a find for the bank name “Banco Popular de Puerto Rico” on both lists. You may want to first sort the data by bank name to find this bank or you can use CTRL + F to find the bank name (see screenshots below).

Step 3.

Normalize data (remove redundancies, irrelevant details)

In this step, there is technically no need to remove redundancies or irrelevant details but you can show the students how you could remove data or limit the data to a particular data set. For example, if were to want to look at only the banks from Maryland, you can use the filter tool to only view those banks from MD.

Step 4.

Import data into tool

Right now the file type is as a csv file. By resaving the file as a .xlsx file it becomes a true spreadsheet file. 

Step 5.

Perform analysis

We have determined that the bank “Banco Popular de Puerto Rico” is on both lists. Now ask the students “Why is this bank on both lists?” Note: On the Failed Bank list the Banco Popular de Puerto Rico is actually an acquiring institution. By looking more closely at the dates of the acquisition of the failed bank “Westernbank Puerto Rico” one can formulate some possible deductions that maybe the reason “Banco Popular de Puerto Rico” is on the complaint list is because they had recently taken over a failed bank. It could be possible that some of these complaints were related to this recent acquisition.

Step 6. 

Visualize Results

Explain to students that they will learn more about visualize their results in Unit 6. They can complete graph visualization in excel. Show them the website: http://www.gapminder.org/. Explain that even though a visualization in excel is not interactive like http://www.gapminder.org/, they can complete some form of visualizing their data by using a spreadsheet. Note: http://www.gapminder.org/ is VERY attention grabbing. Only briefly show the students what they can do with it (see how data changes over time, look at many different data sets, and download data in different forms - including csv and xlsx formats).

Independent Activity (30 min) – Online Research

Students should research their selected topics from homework. Some possible websites for finding data are listed above under “Possible good resource(s) for data collection.”

Students are to get your approval for a topic and then use the Big Data Sets Worksheet in the Lesson Resource Folder to find big data sets that are related to the approved topic. 

Wrap Up (5 min) – Exit Slip

Students are to review using http://www.gapminder.org/ looking specifically at life expectancy. Students will write one question after “playing” the timeline of life expectancy using gapminder on an exit slip before leaving class. For example, one may write “Why is the life expectancy of countries such as Denmark, Sweden, & Norway typically higher than other countries throughout most of the timeline?”

Students are to submit a document stating their topic for research using Big Data. This document should answer the questions:

Topic:
How is Big Data used to solve or remedy the topic?
Link(s) used to find Big Data? (i.e. data.gov, etc)

How has the transformation of data storage affected how data itself is used? 

Answer: Storage and processing of large digital data enables us to analyze large data sets quickly rather than small sampling sizes as used before. 

How can a computer use Big Data to make predictions? 

Answer: Computers can use smart algorithms, powerful processors, and clever software to make inferences and predictions for solvable questions.

Pre-Lesson Preparation

• Teachers will need to have a piece of paper with a unique number on it for all but one student in the class.
• Students will need access to the datasets and Python skeleton code in the Lesson Resources folder.
• Teachers will need to print out the "Search Comparison Worksheet" for each student.

Summary

Students investigate data organization, simulate linear and binary searches, and write pseudocode and Python for linear and binary search methods.

Outcomes

• Students will demonstrate how combining data sources and classifying data are part processing data
• Students will describe challenges to structuring large data sets for analysis
• Students will identify how the order of data influences which methods are appropriate for searching the data.
• Students will describe standard search algorithms in pseudocode and in Python.
• Students will Compare different algorithms for efficiency when searching for an item.

Overview

Session 1

1. Getting Started (5 min) - Journal
2. Class Discussion and Activities (25 min) - Introduction to linear and binary search algorithms
3. Coding Linear Search (20 min)

Session 2

1. Getting Started (5 min) - Think-Pair-Share 
2. Coding Activity (30 min) - Write pseudocode and implement binary search
3. Compare Searches (15 min) - Fill out worksheet to compare search algorithms

Source

Phone book presentation adapted from a lesson taught by Dr. Rheingans in CMSC 201 at the University of Maryland, Baltimore County

• MP1: Make sense of problems and persevere in solving them.
• MP2: Reason abstractly and quantitatively.
• MP6: Attend to precision.
• MP7: Look for and make use of structure.

• F-BF.1-2: Build a function that models a relationship between two quantities

• RST 12.3 - Precisely follow a complex multistep procedure

• 2. Developing and using models
• 3. Planning and carrying out investigations
• 5. Using mathematics and computational thinking

Students will:

• Demonstrate how combining data sources and classifying data are part processing data
• Describe challenges to structuring large data sets for analysis
• Be able to identify how the order of data influences which methods are appropriate for searching the data.
• Be able to describe standard search algorithms in pseudocode and in Python.
• Compare different algorithms for efficiency when searching for an item.

• How does abstraction help us in writing programs, creating computational artifacts and solving problems?
• How can computational models and simulations help generate new understanding and knowledge?
• How can computation be employed to help people process data and information to gain insight and knowledge?
• What considerations and trade-offs arise in the computational manipulation of data?
• What opportunities do large data sets provide for solving problems and creating knowledge?
• How are algorithms implemented and executed on computers and computational devices?
• What kinds of problems are easy, what kinds are difficult, and what kinds are impossible to solve algorithmically?
• How are algorithms evaluated?
• How do computer programs implement algorithms?
• How does abstraction make the development of computer programs possible?
• Which mathematical and logical concepts are fundamental to computer programming?

In Lesson Resources Folder:

• Search Comparison Worksheet to use at the end of Session 2
• DataSets folder that contains the six datasets for the Search Comparison Worksheet
• SearchCode.py contains skeleton code for a numeric search program
• Binary Search in LISP example to show on the screens.

Session 1

Getting Started (5 min)

Journal: What would be the best way to organize a collection of DVDs so that you could find the one you want very quickly? Would you need a different method for a radio station with thousands of DVDs? Discuss.

Class Discussion and Activities (25 min)

Linear Search Discussion (5 min)

As a class, discuss the following questions:
What if you are looking for a specific song. What is the most effective way to look for something if it is in an unordered, unsorted collection?
What are some challenges to organizing large sets of information so they can be processed?
Why does it help to classify data when you are trying to sort it or search through it?

Possible Answers and suggestions for discussion:

• You can search Randomly (How do you stop yourself from repeating yourself?)
• You can search One-by-one, marking off which ones have already been checked.
• You can divide up the problem and each search a pile (multiprocessing)
• Challenges: data entry is time consuming. Large sets of data are more important to keep organized but if you combine information from multiple places they might be organized differently so you have to come up with a single system.
• If you don’t classify the information you’re sorting or searching such as the album title, song title or other searchable information, it would be very confusing to try to find what you are looking for, especially if you don’t know exactly what you are trying to find.
• Having things grouped by artist, genre, or other categories makes it easier to narrow down what you're looking for.

Linear Search Activity (5 min)

1. Pass out pieces of paper with numbers on them to everyone in the class except one person. Students should not share their numbers with anyone.
2. Have everyone stand at the front of the room in a line. The person without a number stands in front and is assigned a number to look for. The class should keep track of how many people they have to ask before they get the number (students that have been checked should sit down).
   • Do this activity a few times. In between, each student should switch with another student a couple of times without showing their paper. (Note: A fun way to do this might be a snowball fight if you can)
   • Ask for a number that does not exist in the set at least once. What happens? How many people does it take before they figure out the number is not in the set?
3. Have everyone sit down but keep their papers.

Binary Search Discussion and Presentation (10 min)

Take out a dictionary (or phone book). Ask the class, how would you search for a particular word/name?

Steps for Binary Search in a book of items to demonstrate to the class:

1. Flip to the middle and pick a word in the middle of the page
2. Is your word higher or lower than this word? If it is higher, “throw out” the lower half of the book. If it is lower, “throw out” the top half. (Not literally unless it is a very old phonebook. Students do love it when you tear up the phonebook, though, and it makes for a very effective demonstration.)
3. Repeat steps 1 and 2 until you find the word.

Why would this not work for an unordered list?

Binary Search Activity (5 min)

1. Have everyone go to the front of the room and get in numerical order by paper. Repeat the search activity using the binary search algorithm.
2. Try with a number not in the list. How can you tell when it doesn’t exist?

Coding Linear Search (20 min)

1. Have students work in pairs to write a code for linear search. The code should:
   1. Read in a csv file that has a list of unordered numbers. (They should input the file name from the user.)
   2. Ask the user what number they want to find and validate that number.
   3. Tell the user whether the number was found. If it was, it should output the number of items it had to look at.
2. Students should save their code for the next day.

Note: Skeleton code (SearchCode.py) is provided in the Lesson Resources Folder.

Session 2

Getting Started (5 min) 

Think-Pair-Share

• Ask students to list non-numbered, real-world things that they search for or sort/order in their daily lives.
• Can all data be sorted, or do types of data exist that cannot be sorted? How would you organize and search these types of data?
• Is there always a "correct" solution when sorting data?

Coding Activity (30 min)

Part 1 Pseudocode (10 min)

1. As a class, write down the steps for Binary Search on the board.
2. In pairs, have the students write pseudocode to implement binary search.
3. When finished, display binary search code in other languages. (Scratch https://scratch.mit.edu/projects/23163175/; javascript https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array ; LISP (see handout)

Part 2 Coding (20 min)

1. Students should use their pseudocode to write a program for binary search. (It would be useful to build on the skeleton code provided for linear search.) The code should accomplish the same things as linear search: read in a file, get a number, and output if the number is found and how many items were checked.

Comparing Searches (15 min) – (May also be Homework if programs are not finished)

• Pass out the worksheet "Search Comparison Worksheet" from the lesson resources folder.
• Students should run both their linear and binary search programs with the six provided datasets of increasing sizes, (also in the lesson resources folder.)
• As they go through, students should record their results in the worksheet and answer the questions at the bottom.
• Discuss the results as a class.

For students that have difficulty understanding the concepts of searching for items in a set of data, pair those students with a student who has a firm grasp of the concept for the activities. Have the pair work together for 1A and then have them keep their own paper secure using the extra game sheet (1A').  Simiilarly for 1B - 1B' and 1C - 1C'.

Correctness of Python functions for linear search and binary search

"Searching Assessment Items.docx" in lesson folder

"Search Comparison Worksheet" in the lesson folder

Summary

In this three-session lesson, students explore and confront the difficulties of the problem of sorting data and the difficulties involved in expressing a clear and efficient algorithm for sorting. 

Outcomes

• Students will be able to relate a real-world task such as sorting cards to sorting/organizing information in a computer.
• Students will understand the problem of sorting and why it is nontrivial for large data sets.
• Students will be able to describe in pseudocode simple sorting algorithms (such as bubblesort).
• Students will be able to reason about the correctness and efficiency of different sorting algorithms, and will understand that the time required to sort a data set increases as the size of the data set grows.

Overview

Session 1:

1. Getting Started (5 min) - Journal
2. Activity Card Sorting (40 min)
   1. Explain the Problem [10 min]
   2. Paired Activity: Algorithm Creation [30 min]
3. Wrap Up (5 min)

Session 2:

1. Getting Started (5 min) - Journal
2. Group Activity: Algorithm Evaluation (20 min)
3. Group Activity: Algorithm Selection and Justification (20 min)
4. Wrap Up (5 min)

Session 3:

1. Getting Started (10 min) - Journal and short discussion
2. Guided Activity: Algorithm Analysis (10 min)
3. Paired Activity: Algorithm Analysis (20 min)
4. Wrap Up (10 min)

• MP2: Reason abstractly and quantitatively.
• MP4: Model with mathematics.
• MP8: Look for and express regularity in repeated reasoning.

The algorithmic techniques and analysis involved in sorting data are seen in a wide variety of contexts and applications. Sorting numbers in a list is challenging but foundational to many algorithms in computer science. 

• How can computation be employed to facilitate exploration and discovery when working with data?
• What considerations and trade-offs arise in the computational manipulation of data?
• Why are some languages better than others when used to implement algorithms?
• What kinds of problems are easy, what kinds are difficult, and what kinds are impossible to solve algorithmically?
• How are algorithms evaluated?
• Which mathematical and logical concepts are fundamental to computer programming?

What makes a "good" algorithm?

What should be taken into consideration when comparing algorithms that complete the same task?

• You will need enough playing cards for every pair of students to have eight different cards. Alternatively, you may make your own cards (e.g., using index cards) with different numbers on them in place of playing cards.
• Handout - Sorting Algorithm Evaluation Student Worksheet.docx (in lesson folder)
• Video collection - https://www.youtube.com/user/AlgoRythmics/videos
  • Note: If students do not have access to computers to individually watch the sorting videos during the paired activity in Session 3, you could instead choose one of the algorithms and show it to the class, having all pairs complete the algorithm evaluation handout for that selected method.

Session 1

Getting Started (5 min)

Journal: Have students respond to the following questions:

• If you had 1 million books, and you had to be able to find any book by its title as fast as possible, how would you organize them? 
• How many books would you need to look at in the worst case scenario to find the title before you have organized the books?
• How many books would you need to look at in the worst case scenario to find the title after you have organized the books?

Teacher note: Having just finished the lessons on searching, students should recall that searching an ordered list allows using the binary search which is faster than searching an unordered list with a linear or random search.

Activity: Card Sorting (40 min)

Teacher note: The focus should be directed more toward the problem-solving technique than nitpicking about the language used. Although students are writing instructions for a human to manipulate a set of playing cards, they still need to be precise, because the assumption is that the person doesn't know what they are doing. This problem is challenging and will require creativity.

Explain the Problem [10 min]

• Demonstrate the card sorting sorting task as you explain.
• Clarify the goal: Today, you and a partner are going to design an algorithm and list the instructions for a person to arrange a row of playing cards into order (from lowest to highest value).
• Explain the basic rules:
• If a card is on the table, it must be face down.
• You can only see the value of a card by picking it up and looking at its face.
• You can only be holding and looking at two cards at a time (1 in each hand).
• You can compare the values of any of the cards you are holding in your hands and determine if one is greater, less than, or equal to the other card.
• When you put a card down, try to be clear about where it should be put back down.  Cards should be put face down.
• You cannot use your memory of face-down cards to make decisions about them. You should behave as though you have no recollection of cards that you aren't currently holding.
• You will have eight cards to practice, but the procedure you follow should be general enough to work for any number of cards.
• Ask the students whether there are any questions about the rules.

• Suggest that it could be helpful to break the task down into parts. Using abstraction and collaboration can decrease the size and complexity of the task that each programmer has to solve. Abstraction allows you to build upon existing processes, collaboration allows you to break up the task once you agree on what the strategy is and what the separate tasks are that need to be solved. Example, cards need to be comared and swapped, one person could write the specific steps for how that should be done.

• Emphasize to students that there are *many* ways to achieve this task. Be creative. As a class, they should try to come up with as many different ways of sorting as possible.

Paired Activity: Algorithm Creation [30 min]

• If there is an odd number of students, there could be one group of three students.
• Distribute the cards to student pairs. The cards can be ordinary playing cards, but each pair should receive cards from the same suit that have been shuffled.  Alternatively, you can use handmade cards with arbitrary numbers on them. Before starting, have students agree on the ordering of the cards (e.g., whether aces are high or low). 
• Have students write their instruction list (algorithm) on a piece of paper.
• The format of the instruction lists is up to the students; they can create a numbered list, a flow chart, a diagram with text and arrows, or other means of communication.
• Students should be working productively for the rest of the class: designing and writing their card sorting algorithm.
• Circulate around the room to make sure that students are on task and that they understand the rules and goals of the activity.

Wrap Up (5 min)

Journal: 

• If you were to give your algorithm a name that describes how it sorts, what would you name it?
• Identify the most difficult part of writing down the instructions for your algorithm.

Homework:  Any pairs that did not finish the activity should complete it as a homework assignment before the next session.

Session 2

In this session, students review the sorting algorithms they wrote in session 1. Students will follow the algorithms created by their classmates and discover a variety of sorting strategies. By analyzing the various algorithms, students will attempt to find the "best" sorting strategy.

Teacher note: There are two main difficulties in algorithm design to highlight: (1) It is very difficult to be precise with language without some agreement about what terms mean. (2) Solving the problem by determining the strategies and steps required to sort objects correctly, as well as efficiently, presents a second level of difficulty.

Getting Started (5 min)

Journal: How do you think a sorting algorithm should be "measured" to determine if it is the "best"? Ask for ideas and discuss this during the group activity.

Group Activity: Algorithm Evaluation (20 min)

• Distribute the "Sorting Algorithm Evaluation Student Worksheet.doc" (in the lesson folder).
• Discuss: How will you determine which algorithm is better and why? How do you define “better”? What criteria will you use?Give students an opportunity to respond individually and collectively. Optionally, you may use a think-pair-share approach or small groups to develop ideas and then share with the class. Solicit student ideas and try to agree of 4 criteria to write down on page 2 of the student worksheet.

• 1. Does it work correctly? (correctness)
  2. Is it well written and easy to follow?
  3. Is it efficient in terms of time? Is it efficient only under certain conditions?
  4. Is it efficient in use of space? Do you need a lot of extra table room as temporary places to arrange the cards in the process of sorting?
• Re-distribute playing cards to student pairs.
• Instruct students to follow directions on the Sorting Algorithm Evaluation worksheet and use it to record their experiences.
• At the end of the session be sure to point out:
  • An efficient algorithm for a problem can help solve larger instances of the problem.
  • What looks more complex in code may actually be a more efficient solution.
  • Different correct algorithms for the same problem can have different efficiencies.
  • An advantage of doing this collaboratively is that it can decrease the size and complexity of the task that each programmer has to solve.

Group Activity: Algorithm Selection and Justification (20 min)

Create groups of four by joining the pairs who previously exchanged algorithms.  

Teacher note: This "swapping algorithm" activity works especially well when students exchange algorithms with a group that has a fundamentally different approach. However, as a practical matter, this can be hard to arrange. From your observations during Session 1, you might have a sense of groups with different approaches that you can assign to swap algorithms.

• Groups should give feedback to each other about the algorithm, making sure to discuss:
• The algorithm's correctness - does it work; do you understand it; could you simulate it or act it out?
• Explain confusing/ambiguous parts of the other group's algorithm in order to help them write it better.
• Discuss which of the two algorithms is "better" and be able to explain why.
• Each group of 4 will nominate one of the two algorithms as the better one of the group.

• Ask each group to volunteer the better algorithm at their table.
• Act out/simulate one group's instructions.

Teacher note: It is possible that the nominated algorithm won't work perfectly. If you encounter any problems with the directions, give them the benefit of the doubt and simulate it as best you can to enable the class to understand the intent.

• Ask if other groups solved the problem with a different strategy and demonstrate a few groups' algorithms.
• Engage students in a discussion about which algorithm was the best. Why is it best? How should algorithms be evaluated?
• Ask students to argue for one method or another and explain their reasons.

Teacher note: The students will perform an actual analysis in a later lesson, so it's okay at this point to simply guide the discussion to see how students are thinking. They will re-examine these ideas later.

• Point out to the students that the speed at which the actor can follow the algorithm is not a measure of the algorithm, but rather the speed of the person. As an analogy, you might compare a person's walking speed with the distance they have to travel. To compare algorithms, you need to measure some "units of work". What those units are is debatable, but must to be agreed upon. For card sorting, "work" could mean picking a card up, putting it down, comparing with another card, etc.

Wrap Up (5 min)

Remind students of the two main issues in writing effective algorithms:

• The need for a clear, unambiguous language for expressing algorithmic solutions.
• Defining criteria for determining whether an algorithm is "good."

Homework:  Assign students to write a final version of their algorithm, working out any ambiguities or other problems revealed during the activities.

Session 3

In this session, we end the set of sorting activities by relating sorting to algorithms in the real world. A further exploration of algorithm analysis with some new algorithms will sharpen their intuition about what should and shouldn't be "counted" when analyzing algorithms, what is "hard" for a computer to do, or what takes a "long time."

Getting Started (10 min)

Journal: discuss ideas and elements from the previous lesson:

• What is "work" for a computer?
• Why would the efficiency of an algorithm be measured in terms of both speed and amount of "space" (memory) required?
• Why does it matter how an algorithm (or program) will be used to decide if it is an appropriate solution?

Teacher should clarify that in general, we want these things from an algorithm:

• To provide a correct solution for any given input.
• To use computational resources as efficiently as possible.
• The suitability of a solution depends on how it will be used. Some sorting algorithms work best in terms of time or memory used, others excel at particular situations like sorting a list that is already mostly sorted but work poorly on lists that are badly out of order.

Guided Activity:  Algorithm Analysis (10 min)

• Go to the website that shows folk dancers simulating various sorting algorithms.  https://www.youtube.com/user/AlgoRythmics/videos
• With the students, click on the bubble sort video, and complete Sorting Algorithm Evaluation.docx for bubble sort, helping the students to identify when a "comparison" is occurring and when a "swap" is occurring.
• Play it again and help the students write the pseudocode for the bubble sort algorithm.
• Compare the students' algorithms to solutions in C++ (https://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm) and MatLab (https://www.mathworks.com/matlabcentral/fileexchange/45125-sorting-methods/content/Sorting%20Methods/bubblesort.m). What features of the bubble sort are identifiable regardless of language? Point out that the language may change the readability of the solution, but that it can be done in any programming language because all provide sequence, conditionals and iteration.

Paired Activity: Algorithm Analysis (20 min)

• Assign each pair a different sorting algorithm.
• Have each pair watch their assigned sorting video and complete the Sorting Algorithm Evaluation for that method.
• Have each group attempt to write pseudocode for their assigned sorting algorithm.  Some of the algorithms are quite complex, so emphasize to the students that the goal of this exercise should be to think about what's happening, rather than to get it completely "right." 
• Compare this algorithm to the one you developed.
• What basic steps do the algorithms have in common? How can abstraction make it easier to solve similar problems by building on existing solutions?

Wrap Up (10 min)

• Instruct students to discuss the following prompts with an elbow partner and then, collaboratively write a response in their journals that incorporates the ideas of both partners.
  • What should and shouldn't be "counted" when analyzing algorithms?
  • What is "hard" or time consuming for a computer to do?
  • Why is the efficiency of algorithms important?
• Assign homework for next lesson on comparing algorithms (Unit 5, Lesson 4): Identify in your journal two places that you often travel between. Of the alternative routes available, what do you consider to be the best route? Why? Are there circumstances in which an alternate route is better? When is that the case?

   

Suggestion: If you have a mix of new and advanced students, challenge the advanced students to sort twice as many cards with a parallel processing algorithm of their own design. Each student on the team can perform one action at the same time. 

Evaluation of algorithms

Convert actions into an algorithm

Pre-lesson Preparation: You should familiarize yourself with www.sorting-algorithms.com paying particular attention to the variety of algorithms and settings along the top of the page. For session 2, you should have the timedsorts.py code and data files (in the lesson folder) readily available for your students.

Summary

In this two-session lesson, students will explore algorithmic efficiency. They will understand the idea through discussion, manual analysis of simple algorithms, and data collection for implemented algorithms.

Outcomes

Students will be able to:

• identify algorithms that have different efficiencies in their problem solving approach.
• explain the metrics used to describe efficiency.
• perform an empirical analysis of sorting algorithms by running the algorithms on different inputs.

Overview

Session 1:

1. Getting Started (5 min) 
2. Guided Activity (40 min)
   1. Good Algorithms and Better Algorithms (5 min)
   2. Algorithmic Efficiency (10 min)
   3. Computational Complexity (10 min)
   4. Comparing Sorting Algorithms (15 min)
3. Wrap Up (5 min)

Session 2:

1. Getting Started (5 min)
2. Empirical Investigation (40 min)
   1. Introduction (5 min)
   2. Experimental Design (10 min)
   3. Data Collection (25 min)
3. Wrap Up (5 min)

• MP5: Use appropriate tools strategically.

• S-ID.1-4: Summarize, represent, and interpret data on a single count or measurement variable
• S-ID.5-6: Summarize, represent, and interpret data on two categorical and quantitative variables

• WHST 12.1 - Write arguments on discipline specific content
• WHST 12.4 - Produce clear and coherent writing in which the development, organization, and style are appropriate to task, purpose, and audience
• WHST 12.6 - Use technology, including the Internet, to produce, publish, and update writing products
• WHST 12.7 - Conduct short as well as more sustained research projects to answer a question

• 1. Asking questions (for science) and defining problems (for engineering)
• 2. Developing and using models
• 3. Planning and carrying out investigations
• 4. Analyzing and interpreting data
• 8. Obtaining, evaluation, and communicating information

• How does abstraction help us in writing programs, creating computational artifacts and solving problems?
• How can computational models and simulations help generate new understanding and knowledge?
• What kinds of problems are easy, what kinds are difficult, and what kinds are impossible to solve algorithmically?
• How are algorithms evaluated?

Sorting:

• Python code for bubble sort and other sorting methods (for use in Session 1 guided activity):
  • http://interactivepython.org/runestone/static/pythonds/SortSearch/sorting.html 
• Sorting Algorithms Animation timing comparison tool (for use in Session 2 guided activity):
  • http://www.sorting-algorithms.com/
• Many online resources are available to help in understanding different sort algorithms. 
• 15 Sorting Algorithms in 6 minutes
  • https://www.youtube.com/watch?v=kPRA0W1kECg
• Bubble Sort versus Quick Sort
  • https://www.youtube.com/watch?annotation_id=annotation_3243502817&feature=iv&src_vid=92WHN-pAFCs&v=aXXWXz5rF64
• Merge Sort versus Quick Sort
  • https://www.youtube.com/watch?annotation_id=annotation_492880&feature=iv&src_vid=aXXWXz5rF64&v=es2T6KY45cA
• Merge Sort in more detail
  • http://www.zutopedia.com/ms_vs_qs.html
• Classic “Sorting Out Sorting” four parts
  • https://www.youtube.com/watch?v=YvTW7341kpA
  • https://www.youtube.com/watch?v=plAi7kcqMNU
  • https://www.youtube.com/watch?v=gtdfW3TbeYY
  • https://www.youtube.com/watch?v=wdcoRfS8edM
• Sorting Animations
  • https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
• Comparing three sorts
  • http://vinayakgarg.wordpress.com/2011/10/25/time-comparison-of-quick-sort-insertion-sort-and-bubble-sort/
• Comparison of Sorting Algorithms Approach
  • http://warp.povusers.org/SortComparison/index.html
• Integers
  • http://warp.povusers.org/SortComparison/integers.html
• Integers with High Repetition
  • http://warp.povusers.org/SortComparison/integers_rep.html
• Strings (slow compare fast move)
  • http://warp.povusers.org/SortComparison/strings.html
• Arrays (fast compare slow copying)
  • http://warp.povusers.org/SortComparison/arrays.html

Session 1

Getting Started (5 min)

Think-Pair-Share: Alternate Routes

• If you assigned the homework from the previous lesson, ask your students to get out their journals to discuss their entries. If not, you could have them write a response in their journal to the following prompt:
  • Identify two places that you often travel between. Of the alternative routes available, what do you consider to be the best route? Why? Are there circumstances in which an alternate route is better? When is that the case?
• Have your students pair off to discuss their responses for a minute or two.
• Ask some of the pairs to share and summarize their journal entries. 

Guided Activity (40 min)

Good Algorithms and Better Algorithms [5 min]

Briefly discuss with your class the topic: what properties make for a good algorithm? What makes one algorithm better than another? Properties you may want to discuss if your students do not volunteer them:

• correctness
• ease of understanding
• elegance (clarity, simplicity, and inventiveness)
• efficiency

A good analogy is purchasing a car, where people are concerned about:

• safety
• ease of handling
• style
• fuel efficiency

Today's session will address the topic of efficiency.

Algorithmic Efficiency [10 min]

Introduce the concept of algorithmic efficiency to your students by asking them if any can describe what algorithmic efficiency is, or what it means for an algorithm to be efficient. Briefly describe efficiency as how well an algorithm uses two resources, time and space (stored memory), to solve a problem. Some topics you may wish to discuss include:

• Two algorithms may both solve the same problem correctly, but with different degrees of efficiency.
• An algorithm that is maximally efficient will minimize the resources it uses.
• Algorithms typically face a space-time tradeoff, where they either use more memory to run faster or take more time but use less memory.
  • When you use a map, you are using more storage resources to go along your route more quickly
• An example of an algorithm that trades space for time (stores more in memory to operate faster) is a lookup table.
  • A real-world example of a lookup table is numbered valet parking. The valet gives the customer a number and goes to park the customer's vehicle in the parking space with that number. When the customer or valet needs to find the vehicle again, instead of having to search through all the spaces, all they need is the remembered (stored) number to go directly to that parking space.
• Most of the time, we are more interested in computational efficiency, or time usage of an algorithm.
• There is also an efficiency in developing algorithms. Programming languages provide abstractions to build on such as variables, expressions, procedures and libraries. By being aware of the many levels of abstraction in developing a program you can effectively apply the resources available to solve a problem efficiently in terms of the quality of the solution and the time spent by the programming team.

Computational Complexity [10 min]

Teacher note: This topic is more advanced, so you may wish to go more in depth or move on to the activity, as appropriate for your students.

A central idea of algorithms is that some algorithms will take more and more time as the size of their input increases. Time is not measured in seconds but rather the number of computational steps needed for the algorithm to finish operation on a given input. Great algorithms grow linearly, at the same rate as their input, meaning the time it takes to finish is directly proportional to the size of the problem they are solving (amount of input data). For instance, an algorithm that takes 10 steps for an input of size 10 and 1000 steps for an input of size 1000 is said to be linear in its input. However, most algorithms take longer as their input gets larger. For instance, an algorithm that takes only 25 steps for an input of size 5 may take 100 steps for an input of size 10, 10000 steps for an input of size 100, and one million steps for a size of only 1000 (it is taking quadratically more time as the input gets larger).

When we analyze algorithms, we often talk about the algorithm's computational complexity, which is the order of magnitude of the algorithm's running time. We almost always discuss the worst case complexity, since that is a bound on the resources required.

If an algorithm finishes with the same number of steps regardless of the size of its input, it is called constant time, which is O(1) in mathematical form (read aloud as "big-oh one"). Constant time algorithms are the fastest in terms of computational efficiency, and any algorithm that takes a constant number of steps is considered O(1). An algorithm that takes 10 steps for an input of size 10 and also takes 10 steps for an input of size 1000 is likely O(1). However, very, very few algorithms are constant time because most algorithms necessarily take longer as the size of their input increases.

An algorithm that can finish by looking at each piece of its input only once is called linear time or linear order, and is written mathematically as O(n), where n stands for "the size of the input." An algorithm that takes 10 steps for an input of size 10 and also takes 1000 steps for an input of size 1000 is likely O(n). Very few algorithms are linear order, especially if they must compare pieces in their input, such as sorting algorithms. The best sorting algorithms are somewhere between linear time and quadratic polynomial time, written as O(n²), where n² stands for "the size of the input, squared." Any algorithm that is O(n²) typically must compare each piece of its input with every other piece of input at least once. An algorithm that takes 100 steps for input of size 10 and a million steps for input of size 1000 is likely O(n²).

Most sorting algorithms are of an order between O(n) and O(n²) known as linearithmic time, written as O(n log n), where log is the logarithmic function. In fact, O(n log n) is the fastest possible order for a comparison-based sorting algorithm. It is impossible for such algorithms to be O(n) since they must make at least some comparisons of their input data. 

Comparing Sorting Algorithms [15 min]

Using the simulation tools at http://www.sorting-algorithms.com/, students will investigate, compare, and contrast sorting algorithms. Notice the grid in the center of the page. Each column is a particular sorting algorithm, and each row is an ordering of horizontal bars (either random, nearly sorted, reversed order, or few unique). Each algorithm will sort the bars in a given cell from top to bottom in increasing order by length.

Ask your students to interact with the website by clicking the green start icons and observing how long it takes each algorithm to sort its bars relative to the other algorithms.

Some questions to have them discuss or record in their journal could include:

• Find the row for "Random" and click the icon above it to see each algorithm sort a randomly ordered set of bars.
• Which algorithms are going slow on average? Which ones are fastest?
• Experiment with larger input sizes by clicking a number for Problem Size near the bottom of the page (30, 40, or 50). Click the icon above Random again. What changes do you notice in the speeds of algorithms? Why are the slow algorithms taking even longer than before? Would you ever want to use them?
• Set the problem size back to 20.
• Find the column for "Bubble" (bubble sort) and click the icon above it to see it run on each of the ordering types. Which one finishes first? Why do you think that is?
• Find the row for "Nearly Sorted" and click the icon above it to see all the algorithms run on nearly sorted input data. Which algorithms finish first? What algorithm is slow on random data but finishes quickly on nearly sorted data? Why do you think it does so?
• Which algorithms do you think are O(n²)?

Make sure your students understand that the size and order of input data can affect how long an algorithm takes. You should direct or help your students discover that bubble sort is a slow sorting algorithm that can be fairly fast for nearly sorted data. You may wish to discuss that bubble sort is O(n²) in the worst case, explaining why it takes so long for large input, but is O(n) in the best case, which is when input is already (or nearly) sorted. In contrast, selection sort is O(n²) in both the worst and best cases, and merge sort is O(n log n) in both the worst and best cases. In general, most sorting algorithms that we would want to use are O(n log n), since O(n²) is usually too slow. You may also want to mention that bubble sort is considered one of the most inefficient sorting algorithms and that quick sort’s worst performance is on already sorted data, so some quick sort implementations shuffle the inputs before sorting to avoid that situation.

Wrapup (5 min)

Watch one or more of the available movie clips that compare the performance of sorting algorithms:

Suggested list of videos (Many more are available):

• 15 Sorting Algorithms in 6 minutes
  • https://www.youtube.com/watch?v=kPRA0W1kECg
• Bubble Sort versus Quick Sort
  • https://www.youtube.com/watch?annotation_id=annotation_3243502817&feature=iv&src_vid=92WHN-pAFCs&v=aXXWXz5rF64
• Merge Sort versus Quick Sort
  • https://www.youtube.com/watch?annotation_id=annotation_492880&feature=iv&src_vid=aXXWXz5rF64&v=es2T6KY45cA
• Classic “Sorting Out Sorting” in four parts
  • https://www.youtube.com/watch?v=YvTW7341kpA
  • https://www.youtube.com/watch?v=plAi7kcqMNU
  • https://www.youtube.com/watch?v=gtdfW3TbeYY
  • https://www.youtube.com/watch?v=wdcoRfS8edM

Session 2

Getting Started (5 min)

Journal: Remind your students about the sorting algorithms from the previous session and have them answer the following questions:

• What are some ways in which one algorithm can be better than another, besides efficiency?
• Explain what algorithmic efficiency is by discussing two different sorting algorithms.

Guided Activity: Empirical Analysis (40 min)

Introduction [5 min]

The students will measure and analyze the effect of sorting set size on execution time for a given sorting algorithm using Python code. Using the timedsorts.py file in the lesson resources folder as a basis, the students will perform an experimental analysis to compare sorting algorithms by timing them on input data of different sizees. They will hypothesize, design and code their experiment, collect results, and write a report for homework.

The sorting functions available in the Python code include: quick sort, merge sort, selection sort, insertion sort, and bubble sort. For advanced students or classes may, you may wish to have them implement additional sorting algorithms. 

The sample code includes helper functions to generate random data, to load data from a file, and to time sorting functions on the data. Example code for invoking these functions is included at the end of the file. You can remove this example code before sharing it with your students if you wish to emphasize the programming and critical thinking required to do this project.

Each student (or pair or group) needs their own copy of the Python code to modify for their experiments.

Experimental Design [15 min]

Students will compare sorting algorithms by timing them with Python code on input data of various sizes. Have your students (individually or in pairs) make a hypothesis about what will happen as the size of data input increases, answering the following questions:

• How can you determine which sorting algorithm is most efficient and which is least effiicient?
• What sorting algorithm do you think is most efficient, and which is least efficient?
• What do you hypothesize will happen to the time as the size of the data input increases?
• What is the independent variable in this experiment?
• What is the dependent variable?

Have your students write out a description of the steps they will take to perform the experiment.

Data Collection [20 min]

Have students modify their Python sorting code to implement the experimental steps they outlined. Students must:

• Time their sorting routines with different size sets of items to sort (e.g., 5000, 10000, 25000, 50000). Sample data files are available in the lesson resources folder, but students should use the provided helper function to generate arrays of random data, too.
• Record (write down) the size of each input array, the name of the sorting function, and the resulting time it took to sort the data for each algorithm/data combination they test.
• Discuss the results with another student or group. What patterns can be seen in the relationship between the amount of data and the time to run the program?

The data collection should be completed by the end of class, but students will continue to work on this activity by writing a report describing their results.

Wrapup (5 min)

Assign as homework to write a short report about the findings, making sure to:

• Write your hypothesis. How do your findings reflect your hypothesis?
• What algorithm or algorithms are most efficient? Why?
• What algorithm is least efficient? Why?
• What values did you use for your independent variable?
• Present the data you collected in a table and in a graph.
• What conclusions can you draw about sorting algorithms?
• Explain why algorithmic efficiency is important by discussing another problem (not sorting) where a correct but inefficient algorithm is unusable at larger input sizes. 
• Pick two sorting algorithms you tested. Write a paragraph for each describing how it works, and one paragraph comparing the two algorithms explaining which is more efficient and why (you can do research and look at the Python code to figure out the reasons).

Students must complete a short research report on their sorting algorithm research procedure, results, and analysis of the results.

The teacher may decide to have the students choose how they want to organize the empirical analysis effort.  Alternatively, scaffolding with a worksheet or checklist could be used to guide the students through the data collection and analysis tasks.

The following "Checks for Understanding" could be used to guide the students towards the three learning objectives:

Objective: SWBAT identify families of correct algorithms that have different efficiencies in their problem solving approach.

1. Students will pair-share what makes a good choice for the route taken to get from point A to point B.
2. Students will compare algorithms and explain why and when some are better than others in terms of efficiency.
3. Students will be able to identify and rank order the least efficient sorting algorithms in the simulations.

Objective: SWBAT demonstrate logical reasoning and metrics is used to describe an algorithm’s efficiency.

1. Predict:  Students will have seen sorting algorithms implemented as folk dances.  Students will predict -- for their algorithm -- how adding additional dancers would increase the dance completion time.

Objective: SWBAT to perform empirical analysis of sorting algorithms by running the algorithms on different inputs.

1. Students will work in pairs to collect data on sorting execution times.  The pairs will share their results with other groups to check for patterns before they write up their results.

Students will complete a short research report on their sorting algorithm research procedure, results, and analysis of the results.

Summary: Students are introduced to the theory of computation, computability, the halting problem, and advanced algorithms. In particular, they will learn about heuristic search used by artificial intelligence (AI) programs to play games.

Objective: 

Students will be able to:

• define computation and some basic ideas of the theory of computation
• discuss computability and understand there are some things computers cannot solve
• explain the Halting Problem
• identify some advanced search algorithms
• understand how AI programs represent games with game trees
• understand how AI programs use uninformed and heuristic search algorithms to play games

Overview:

Session 1

1. Getting Started (10 min)
2. Guided Activity (35 min)
   1. Inverse Operations Activity [10 min]
   2. Computation [10 min]
   3. Computability [15 min]
3. Wrap Up (5 min) - Think-Pair-Share 

Session 2

1. Getting Started (5 min)
2. Guided Activity (45 min)
   1. Search and Game Trees [15 min]
   2. Game-Playing AI [10 min]
   3. Types of Heuristic Search [10 min]
   4. Playing a Game with Heuristic Search [10 min]

• MP2: Reason abstractly and quantitatively.
• MP4: Model with mathematics.

• N-RN.3: Use properties of rational and irrational numbers.
• F-BF.1-2: Build a function that models a relationship between two quantities
• F-BF.3-5: Build new functions from existing functions
• S-IC.1-2: Understand and evaluate random processes underlying statistical experiments
• S-CP.6-9: Use the rules of probability to compute probabilities of compound events in a uniform probability model
• S-MD.5-7: Use probability to evaluate outcomes of decisions

• RST 12.3 - Precisely follow a complex multistep procedure

• 2. Developing and using models
• 6. Constructing explanations (for science) and designing solutions (engineering)

• How can computational models and simulations help generate new understanding and knowledge?
• What considerations and trade-offs arise in the computational manipulation of data?
• What kinds of problems are easy, what kinds are difficult, and what kinds are impossible to solve algorithmically?
• How are algorithms evaluated?

Links to videos and online tools as indicated in the lesson plan.

• http://www.sorting-algorithms.com/ for sorting algorithm review
• The Halting Problem https://www.youtube.com/watch?v=92WHN-pAFCs (7:52)

 Alternative instruction could include the Towers of Hanoi problem and discuss the algorithm for solving it. Some demonstrations are available here:

• http://illuminations.nctm.org/Activity.aspx?id=4195
• http://www.mazeworks.com/hanoi/

Session 1

Getting Started (10 min)

Think-Pair-Share: In pairs, think about and try to answer each of the following questions:

• Given y = 7x + 4 and x=3 what are the steps to find y?
• Given y = 7x + 4 and y=3 what are the steps to find x?
• Factor 81,927,497 and 81,927,499. Can you figure out the steps?
• Multiply 431 x 433 x 439. What are the steps?

Note: just give them a few minutes to try the factoring, but round them up to continue and discuss: which operations were much harder to perform than their inverse? Can you just invert the steps, and why or why not?

Guided Activities (35 min)

Inverse Operations Activity [10 min]

1. Convey the following concepts:
   1. Inverse arithmetic operations
      • add/subtract                     [x + 7 – 7 = x – 7 + 7 = x] ;
      • multiply/divide                  [x * 7 / 7 = x / 7 * 7 = x] ;
      • e^x /ln(x)                              [ln(e^x) = e^ln(x) = x];
      • …
   2. Some arithmetic operations are harder to do then their inverse operations -- as the students did during the warm-up.
      • Cubing a number versus finding the cube root of the result.
        • Find the cube of 12
        • Find the cube root of 5832
      • Multiplying numbers to form a product versus factoring the product.
   3. The same can be true with algorithms.
      • It is much easier to scramble a Rubik’s cube with a few moves than it is to solve a scrambled Rubik’s cube with a few moves.  [Optional -- Have the students discover this using a Rubik's cube or an online simulated cube].

Make a connection to the previous lesson by comparing these to sorting algorithms, where some are speedy and efficient like Merge sort and Quick sort, and others are unusably slow, like Bubble sort. Highlight the difference that different problems have different lower bounds on optimal solutions, and that some problems like integer factorization have solutions but take too long to be solved in a practical way.

Computation [10 min]

Discuss the definition of computation (in a theoretical sense) with your students. Computation is input plus processing to get output. A computer is one system that is a "model of computation" since it takes input, processes it, and produces output.

Another model of computation is called a Turing machine, named after Alan Turing (one of the most famous computer scientists). A Turing machine is a theoretical entity that has a tape of symbols (a line of 0s and 1s), a head that can read only one symbol at a time, and an internal state that can change based on instructions as the head reads symbols. Turing and a mathematician called Alonzo Church are responsible for the "Church-Turing" thesis, which says that a Turing machine can compute anything that a digital computer can. This is a fundamental idea of the theory of computation, and has the implication that anything one computer is capable of doing is possible to be computed by another, given enough resources (time and memory). 

Computability [15 min]

Now discuss the idea of computability with your students. Ask your students to answer or think-pair-share: are there things it is impossible for a computer to compute? The most classic "undecidable" (non-computable) question is called the Halting Problem. The Halting Problem is: make a program that can tell if another program will halt (terminate at some point eventually) or will loop forever and never end.

The Halting Problem is impossible for a computer to compute, which you can prove (informally) by paradox. Suppose you did have a program that solved the Halting Problem, called HALT(X), which takes the code for some program X as input and says "yes" if X terminates or "no" if X loops forever. Then you could write a new program that uses HALT inside it, which we will call PARADOX(X). First PARADOX(X) will run HALT(X) and if the result is no, PARADOX will halt, but if the result is yes, then PARADOX will loop forever. But here is the problem: what if we use the code for PARADOX as the input to PARADOX, running PARADOX(PARADOX)? If it says that PARADOX halts, then PARADOX runs forever, and if it says PARADOX runs forever, then PARADOX halts. This problem is a paradox and does not make sense because the premise, that a program called HALT could exist, must be wrong! Therefore, the Halting Problem is impossible for a computer to solve.

Video explanation with optional student simulation

• Alonzo Church, an American, and Alan Turing, from the UK, independently proved in the 1930s – before computers actually existed – that there are some problems that computers will never be able to solve. View: The Halting Problem at: https://www.youtube.com/watch?v=92WHN-pAFCs  [Optional 7:52]  Have groups of students act out the machines in the video to determine whether they understand the basics of the proof.

Wrap Up (5 min)

Think-Pair-Share:

• Ask your students to think about the following algorithms, pair off, and reorder them based on worst-case computational complexity, with the fastest ones first and the slower (or undecidable) ones last:
  • Bubble Sort
  • Factoring large integers
  • Merge Sort
  • Binary Search
  • Taking attendance
  • The Halting Problem
• Discuss the orderings that a few groups came up with. Advanced groups could also try to guess the computational complexity:
  
  • Binary Search, O(log n)
  • Taking attendance, O(n) since you just read off the list in order
  • Merge Sort, O(n log n)
  • Bubble Sort, O(n²)
  • Factoring large integers, O(eⁿ), approximately exponential depending on the algorithm
  • The Halting Problem, undecidable

Session 2

Getting Started (5 min)

This session concerns advanced algorithms, in particular heuristic search, which is commonly used in artificial intelligence. Refresh your students' minds on the definitions of computation, computability, and undecidable problems. Additionally, mention the properties we consider when we compare algorithms:

• correctness
• ease of understanding
• elegance and style
• time/space efficiency

Guided Activity (45 min)

Search and Game Trees [15 min]

Introduce the idea of heuristic search, which is a class of algorithms used in many artificial intelligence programs. A heuristic is something that is used to find a good solution in a reasonable time, and a heuristic search algorithm is an algorithm that uses heuristics to determine how to search through some space.

A great way to introduce heuristic search is first to discuss game trees. A game tree is a structure that is used to represent the "space" of a game that an algorithm wants to search through.

Think of a game like chess: you make a move, the opponent makes a move, and the process continues until the ending conditions have been met (one player in checkmate or stalemate). A game tree is a mathematical structure used by AI and heuristic search algorithms to model the moves made in a chess game. At any turn, we can make a "tree" by drawing the root node as representing the current state of the board and drawing one branch under it for every possible move. In Tic-Tac-Toe, if you are the starting player, then the root node represents a blank board, and there will be nine branches, one for each possible move (each space where you could place your mark). Following a branch in the game tree takes you to a new node that represents the configuration of the game that results from having taken that move. In Tic-Tac-Toe, if I am the first player and place my X in the center space, I have "followed" that branch down the tree to a new node that represents the board with an X in the center space. The opponent then uses this node as the root of their game tree, and has a branch for each of their possible moves.

Think-Pair-Share: Have your students pair off and play a game of Tic-Tac-Toe and try to draw the game tree as they play it, drawing the nodes for each move they made and every potential branch from those nodes. Bring them back into discussion and ask them what if they had to draw out every node followed down every branch? Now ask them to imagine the game tree for chess, which has 20 possible moves on the first turn, 400 on the second, and many, many more as the game goes on. How can an artificially intelligent program learn to play chess when there are so many (too many) options? Chess actually has around 35¹⁰⁰ nodes in its tree and 10⁴⁰ legal states.

Game-Playing AI [10 min]

Heuristic search on game trees is one way AI programs are able to play games like chess. How good are computer game players?

• Chess: Deep Blue, a complex machine that used databases and heuristic search, beat Garry Kasparov (one of the best chess players ever) in 1997
  • Garry Kasparov vs. Deep Junior (Feb 2003): tie! 
  • Kasparov vs. X3D Fritz (November 2003): tie!
  • http://www.cnn.com/2003/TECH/fun.games/11/19/kasparov.chess.ap/
• Checkers: Chinook is an AI program with a very large endgame database that is the world champion. Checkers, like Tic-Tac-Toe, is "solved," meaning there is a known optimal way to play the game to always win or force a tie. You can play a version of Chinook here:
  • https://webdocs.cs.ualberta.ca/~chinook/
• Bridge: "Expert-level" computer players exist (but no world champions yet).
• Poker: Computer team beat a human team, using statistical modeling and adaptation:
  
  • http://www.cs.ualberta.ca/~games/poker/man-machine/
• Good places to learn more:
  • http://www.cs.ualberta.ca/~games/
  • http://www.cs.unimass.nl/icga

Typically games modelled with game trees are 2-person games, players alternate moves, and they are zero-sum (meaning one player's loss is the other's gain). More complicated elements in such games may have include: hidden information (like other players' hands), chance (dice), or multiple players.

Playing a Game with Heuristic Search [10 min]

How does an AI program use heuristic search to play a game? Typically in these steps:

• consider all moves that are possible for the current turn
• compute what the new positions and configuration of the board (the "state") for each of those moves
• evaluate each state using some scoring function to determine which is better
  • for example, taking an opponent's piece is probably going to be evaluated more highly than simply moving a pawn
• make the move that results in the best evaluated state
• wait for your opponent to play, repeat

The key problems are:

• representing the state of the board
• generating the resulting states from every move
• evaluating the value of the resulting states

For evaluation, some function is typically coded or learned over time.

• For Tic-Tac-Toe, for board state n, an evaluation function could be:
  • f(n) = [# of 3-lengths open for me] - [# of 3-lengths open for you], where a 3-length is a complete row, column, or diagonal
• Alan Turing's function for chess with board state n:
  • f(n) = w(n)/b(n) where w(n) is the sum of the point value of white's pieces on the board at state n, and b(n) is the sum of black's pieces. The point values are those commonly used by professional chess players, pawn is 1 point, the queen is 9 points.

Types of Heuristic Search [10 min]

Refer to the "Advanced Algorithms" slides in the lesson resources folder for examples of uninformed search. For an activity, you may want to create a game tree for Tic-Tac-Toe and have your students walk through how each of the following algorithms would operate over it.

Uninformed Search are algorithms that work without a heuristic, using no information about the likely "direction" of the goal node. Algorithms include:

• depth-first search
  • starting at the root of the game tree, pick one branch and examine the node at the end of it, then pick one branch of that node and examine the even deeper node (hence, "depth-first") until you reach the end of the game, then go back one node, pick one of its branches, explore until you reach the end of the game, and so on
  • this search is unpractical for games with many moves that may go on indefinitely
• breadth-first search
  
  • starting at the root of the game tree, called A. It has n branches leading to child nodes each called B₁, B₂, and on to B_n, for some n nodes. Examine each of these children in order before moving onto the children of B₁, examining each of those in order, then examining the child nodes of B₂ then those of B₃, and so on.
  • this search is unpractical for games with many or variable numbers of moves per turn

For any games with variety and complexity, certainly for chess and even checkers, uninformed search is simply too slow because it is exhaustive. This problem is another example, like with sorting, where the efficiency of our solution matters a great deal. To get programs to play games, we need them to be efficient and intelligent about the number and quality of moves they consider. 

Informed Search algorithms each follow some heuristic that uses information about the game to determine smart directions to explore. Examples include:

• best-first search ("greedy")
  • at every turn, take the branch leading to the node with the greatest value from the evaluation function 
  • the problem here is when there is delayed reward since this "greedy" approach lacks any ability to look ahead. For instance, if there are two moves available, one that is great and another that is just decent, it will always pick the great move even if a winning move could be made the turn after the decent one. 
• A* ("a star")
  • estimates the goal node and picks nodes based on the least cost. It follows a best-first strategy but also factors in the distance it has traveled from the original root node.
• Your GPS device! In order to figure out the best, fastest route to your destination, your GPS will search through the possible roads you can take intelligently by factoring in things such as the span and capacity of the road, the traffic, and potentially even the time of day. 

Advanced classes may wish to discuss local search algorithms, such as hill-climbing and genetic algorithms (in the "Advanced Algorithms" slides in the lesson folder).

Minimax

Thinking about game trees again, we want to select the branch that takes us to a node with the maximum evaluated state. But there is a catch: the opponent gets to make moves, too. That is, every other branch in our game tree is the opponent's turn. How does the AI program account for the other player?

Perhaps most logically, the way AI programs do so is to assume the other player will play optimally. Just as the AI will take the branch that leads to the state with the greatest evaluation, it assumes the other player takes the branch leading to the state that will maximize their position. In other words, the AI searches through their game tree by following the branch with the maximum value on their turn, and following the branch with the minimum value on the opponent's turn. This algorithm is called minimax and is the basis of nearly all AI that play 2-person zero-sum games.

For the Halting Problem proof, it is important that students can translate the solution that is on the video into a representation that makes (some) sense to them.  Acting out the inputs and outputs of the set of machines is an approach worth trying.

The following "Checks for Understanding" could be used to guide the students towards the three learning objectives.

Objective: Students will identify some Advanced Algorithms that Exploit Inverse Operations Efficiency.

1. Pairs of students will be asked to list pairs of basic arithmetic inverse functions.
2. The class will develop a composite list of inverse functions found by the student pairs.  Note: many of these pairs share the same key on their graphing calculators.
3. Students will factor composite numbers and create the same composite numbers from their prime factorization.  They will log the relative effort in their journals.

Objective: Students will identify some Advanced Algorithmic Techniques.

1. Students will find examples from earlier modules where the algorithms used techniques of heuristics, randomness, probability, etc.  This could be a good group review of prior topics.

Objective: SWBAT discuss at least one example of a computing problems that is unsolvable

1. Students will either describe the proof of Turing's Halting problem using models in a way that is similar to that used in the lesson video or they wil build a similar physical model using students as the machines.

Students will be able to summarize -- in their own words or with simple models -- the proof of the Halting Problem.

Students will be able to identify the sensitivity of cryptography to the difficulty of factoring large numbers.

Summary

Students will define, design and implement a programming project: a miniature version of the Create Performance Task. They will create presentations and share with groups the projects they developed and how their project used abstractions.

Outcomes

• Students will complete a miniature version of the Create Performance Task.

Overview

Session 1:

1. Presentation  (5 min) Students are introduced to the Create Task.

2. Activity (15 min) Students select a small programming project to model the Create Task.

3. Activity (10 min) Students identify an algorithm to use in their program and share within tabe groups.

4. Activity (10 min) Students identify an an abstraction to use in their program.

5. Wrap Up (5 min) Students share the algorithms and abstractions they will use with the class.

Session 2:

1. Journal (2 min) - What is your plan for today for the development of your project? What abstractions do you plan on using in your project?

2. Activity (43 min) - Students complete implementing their projects.

3. Journal (5 min) - Reflection. What abstractions did you use in your project?

Session 3:

1. Getting Started (5 min) - Students individually respond to three prompts about their projects.

2. Activity (20 min) - Students prepare one minute presentations of their projects.

3. Presentations (15 min) - Students present their project to table groups.

4. Wrap Up (5 min) - Students create exit slips with any questions about the Create Task.

Students practice choosing a project and planning how to implement it in a fixed time frame. 

Students have just two days to plan and implement a project.  Since these will be small projects, students may need help using algorithms and data abstraction. Since an algorithm is a list of steps that comes to a conclusion, if students develop pseudocode for their projects they can refer to the pseudocode as their algorithm. 

Students may receive most of the credit from an incomplete project if the project demonstrates the required components.

For this practice task, teachers may want to provide program stubs.  Stubs could include suggested functions. 

• How are algorithms implemented and executed on computers and computational devices?
• How do computer programs implement algorithms?
• How does abstraction make the development of computer programs possible?

Session 1:  Planning Day

Present an overview of the Create Task.

Explain that students will have 12 hours to complete the Create Task later in the course and they will three 50-minute sessions for this practice.  The actual Create Task will have a suggested collaborative component and be larger in scope.

Discuss the following guidelines for the full project and the practice project we will be doing.

Full Create Task Guidelines

Three components to create:

• Program
• Report
• Video

General:

One project - individual with collaboration in stages

12 hours of classroom time

Project must use functional and data abstraction.

Report: Written responses  (response to all prompts combined must not exceed 750 words, exclusive of the Program Code.):

a. Provide a written response or audio narration in your video that:  Identifies the programming language and identifies the purpose of your program.   

b. Describe the incremental and iterative development process of your program

c. Describe how a selected algorithm functions.

d. Explain how an abstraction you developed helped manage complexity

Practice Create Task Guidelines

For this practice task, students will complete simpler project and a one-minute presentation about it, rather than a video and a report.

Students work individually to select projects.

After completing the project, students will create a one-minute presentation about it.  Presentation should address the following.

a.  Identify the programming language and the purpose of your program.   

b. Describe the incremental and iterative development process of your program

c. Describe how a selected algorithm functions.

d. Explain how an abstraction you developed  helped manage complexity

The presentation must address at least points a and b of the above and c or d.

Projects are chosen by the student.  If they wish, their projects may be based on the following labs from How to Think Like a Computer Scientist.

Labs

• Astronomy Animation
• Turtle Racing Lab
• Drawing a Circle
• Lessons from a Triangle
• Finally a Circle
• Counting Letters
• Letter Count Histogram
• Approximating the Value of Pi
• Python Beyond the Browser
• Experimenting With the 3n+1 Sequence
• Plotting a sine Wave

Students select a project and share their ideas with partners. 

After collaborating with partners, students submit to their teacher a brief description of the project describing its most important features and how it will work.

Students identify an algorithm and an abstraction to use in their projects.  The algorithm should be written as pseudocode and then shared with their partners.

Students should discuss in groups what abstraction they chose and how they think it would be helpful.

Session 2: Implementation Day

Warm up (2 min)

Students complete a brief journal entry describing:

• Their plan for today in the development of the project.
• What abstractions they will be using in the project.

Work Time (43 min)

Students work to implement and test projects. Teachers may evaluate student performance based on student journal entries and their observations of their effort in implementing the project.

Closing (5 min)

Students reflect on their project and making journal entry of how they used abstraction in the project.

Day 3: Presentation Day

Warmup (5 min)

Students begin by individually responding to these prompts about their project:

b.    describe the purpose, how your program code works and the most important features and algorithms

d.    describe the development process

e.    explain an abstraction and how it helped manage complexity

Presentation Preparation (20 min)

Students prepare one-minute presentation about their projects including their responses to prompts b, d and e. 

Presentations (15 min)

Students present their project to table groups. Time the presentations so that they do not exceed 1 minute. Students share with table groups what they like about the project, what they learned and any questions they have.

Closing (5 min)

Students create exit slips with any questions they have about the Create Task after viewing and discussing the presentations.

For the practice task, project descriptions and pseudocode for each proposed project should be assessed.  Assessment can be done by collaborative partners first.  If partners have concerns, they should be brought to the teacher.  If student projects are too big or too small in scope, teachers should provide feedback.

The project should be scored using the latest rubric provided by the College Board. 

The latest rubric (updated as of June 2016) is in the lesson folder.