Unit 2 Lab 2 Teacher Guide

Students have touched on lists in Unit 1, but this lab is where we really dive into them. First, in the very simple shopping list app, students learn list creation and mutation. Then, in the quiz program, we introduce the very important idea of data abstraction, specifying a constructor and two selectors for the quiz item data type.

But what we don't do in this lab is to introduce the higher-order functions that will be our main tools for list processing later in the course. We hint at them in the third page by using for each item, which is a higher-order procedure but not a function, and therefore doesn't require the gray ring notation that will be introduced in the next lab.

Pacing

Lab Pages

Page 1: Shopping List App.
- Learning Goals:
  - Construct a list, add items to it.
  - The empty list is different from a list with an empty item, and is the right starting point when building a list one item at a time.
  - The when I am clicked block allows a sprite to be used as a button.
Page 2: Planning a Quiz App.
- Learning Goals:
  - An abstract data type consists of a constructor procedure and one or more selector procedures.
  - Plan and build an abstract data type.
- Tips:
  - This page has more reading, and less doing, than most. To make it look less intimidating, we have hidden much of the reading behind "hint" links. Exercise 2 asks students to read the text, clicking links one at a time to look at and then re-hide each code picture. This is the only place where we've used the "hinting" mechanism on things we want every student to read; it's an experiment.
  - After the text comes a long vocabulary box that defines six terms. It starts with the most concrete terms, the ones that name procedures you can point to. Then comes the notion of a data type, and the distinction between primitive types built into the language and abstract types that are specific to one application, rather than a general feature of the programming language. At the end, data abstraction itself is defined as the use of abstract data types.

The table below compares the "ordinary language" use of abstract with the CS use. (It's not about data abstraction specifically, but the major levels of abstraction in computer science generally.)

In ordinary language, the actual physical computer is the "least abstract" thing, because you can hold it in your hand, push its buttons, maybe take it apart. In ordinary language, programming seems to deal with "more abstract" ideas, things with no visible, tangible existence. In some ways, the physical thing might seem easiest to think about, and the programming at the top of the table harder.

Computer scientists use "abstract" to mean something more like "this is defined in terms of that": application software is written in a high level language, which is itself implemented in a low level language. It's easier to understand a language than to deal with all the details—how the language is built from lower level languages, and how they work with the computer architecture, and how that's built of transistors, which depend on the behavior of electrons, and so on. From that perspective, things get harder as you move down the table. It's easy to write a program in Snap!, harder to write one in C, because you have to think about more details of memory management. It's easier to understand the design of a computer architecture (the Intel Core design, for example) than to understand the physical circuits that implement it.

Ordinary language	Levels of abstraction	Computer science
most abstract (harder)	application software	most abstract (easier)
	high level language (Snap!)
	low level language (C)
	machine language
	computer architecture
least abstract (easier)	physical computer (chips, wires)
	transistors
	atoms
	protons, neutrons, electrons
most abstract (harder)	quarks	least abstract (harder)

Page 3: Checking Each Quiz Answer.
- Learning Goals:
  - Traverse the items of a list.
  - Understand and use the abstraction of the for each item block, which hides the use of index numbers to access each item. The programmer can just write the code to handle one item, and the block takes care of supplying items one at a time.
- Tips:
  - A very common beginner's bug is to mistrust the for each item block and try to do the traversal in the script in the C-shaped slot.
  - Another common bug is to think that the item variable provided by the block contains an index (an item number), whereas it actually contains the item itself.

Solutions

Correlation with 2020 AP CS Principles Framework

Computational Thinking Practices: Skills

2.B: Implement an algorithm in a program.
3.A: Generalize data sources through variables.
3.B: Use abstraction to manage complexity in a program.
4.B: Determine the result of code segments.

Learning Objectives:

AAP-1.C: Represent a list or string using a variable. (3.A)
AAP-1.D: For data abstraction:
1. Develop data abstraction using lists to store multiple elements. (3.B)
AAP-2.K: For iteration:
1. Write iteration statements. (2.B)
2. Determine the result or side-effect of iteration statements. (4.B)
AAP-2.O: For algorithms involving elements of a list:
1. Write iteration statements to traverse a list. (2.B)
2. Determine the result of an algorithm that includes list traversals. (4.B)

Essential Knowledge:

AAP-1.A.3: Some programming languages provide types to represent data, which are referenced using variables. These types include numbers, Booleans, lists, and strings.
AAP-1.C.2: An element is an individual value in a list that is assigned a unique index.
AAP-1.D.1: Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation.
AAP-1.D.2: Data abstractions manage complexity in programs by giving a collection of data a name without referencing the specific details of its representation.
AAP-1.D.3: Data abstractions can be created using lists.
AAP-1.D.4: Developing a data abstraction to implement in a program can result in a program that is easier to develop and maintain.
AAP-1.D.5: Data abstractions often contain different types of elements.
AAP-1.D.6: The use of lists allows multiple related items to be treated as a single value. Lists are referred to by different names, such as array, depending on the programming language.
AAP-1.D.7: The exam reference sheet provides the notation
```
[value1, value2, value3…]
```
to create a list with those values as the first, second, third, and so on items. For example,
- ```
aList ← [value1, value2, value3,...]
```
  creates a new list that contains the values
```
value1
```
  ,
```
value2
```
  ,
```
value3
```
  , and
```
…
```
  at indices 1, 2, 3, and … respectively and assigns it to
```
aList
```
  .
- ```
aList ← []
```
  creates a new empty list and assigns it to
```
aList
```
  .
- ```
aList ← bList
```
  assigns a copy of the list
```
bList
```
  to the list
```
aList
```
  . For example, if
```
bList
```
  contains
```
[20, 40, 60]
```
  , then
```
aList
```
  will also contain
```
[20, 40, 60]
```
  after the assignment.
AAP-2.N.1: The exam reference sheet provides basic operations on lists, including:
- assigning a value of an element of a list to a variable:
```
x ← aList [i]
```
  assigns the value of
```
aList[i]
```
  to the variable
```
x
```
  .
- assigning a value to an element of a list:
  - ```
  aList[i] ← x
```
  assigns the value of
```
  x
```
  to
```
  aList[i]
```
  .
- ```
aList[i] ← aList[j]
```
    assigns the value of
```
aList[j]
```
    to
```
aList[i]
```
    .
- inserting elements at a given index:
```
INSERT(aList, i, value)
```
  shifts to the right any values in
```
aList
```
  at indices greater than or equal to
```
i
```
  . The length of the list is increased by 1, and
```
value
```
  is placed at index
```
i
```
  in
```
aList
```
  .
- adding elements to the end of the list:
```
APPEND(aList, value)
```
  increases the length of
```
aList
```
  by 1, and
```
value
```
  is placed at the end of
```
aList
```
  .
- removing elements:
```
REMOVE(aList, i)
```
  removes the item at index
```
i
```
  in
```
aList
```
  and shifts to the left any values at indices greater than
```
i
```
  . The length of
```
aList
```
  is decreased by 1.
AAP-2.N.2: List procedures are implemented in accordance with the syntax rules of the programming language.
AAP-2.O.2: Iteration statements can be used to traverse a list.
AAP-2.O.3: The exam reference sheet provides
```
FOR EACH item IN aList
{
    <block of statements>
}
```
The variable
```
item
```
is assigned the value of each element of
```
aList
```
sequentially, in order, from the first element to the last element. The code in
```
block of statements
```
is executed once for each assignment of
```
item
```
DAT-1.A.5: Abstraction is the process of reducing complexity by focusing on the main idea. By hiding details irrelevant to the question at hand and bringing together related and useful details, abstraction reduces complexity and allows one to focus on the idea.

Lab 2: Making Lists