AP Computer Science Principles Notes

Nested Conditionals

Nested conditional statements consist of conditional statements within conditional statements.
In a flowchart, nested conditionals involve a condition leading to another condition based on whether the first condition is met.
In Pseudocode, nested conditionals involve an IF statement within an ELSE block or another IF block.

Example: Adjusting Number of Lives

Scenario: Adjusting the number of lives based on time and score.
Variables: time, score, lives.
* Example values: time = 4.5, score = 1200, lives = 5
Conditions:
- IF (time < 3) AND (score > 1000): lives = lives + 3
- ELSE IF (time < 3) OR (score > 1000): lives = lives + 1
- ELSE: lives = lives - 1
- Given time = 4.5 and score = 1200:
  - The first condition is FALSE because time < 3 is false.
  - The second condition is TRUE because score > 1000 is true.
  - Therefore, lives = lives + 1, so lives becomes 6.

Example: Adjusting Number of Lives with different values

time = 3, score = 1000 and lives = 5
IF
time
The first condition is FALSE because time < 3 is false.
The second condition is FALSE because time < 3 and score > 1000 are both false.
- Therefore, lives = lives - 1, so lives becomes 4.

Practice: Determine the Cost of Ice Cream

Scenario: Determine the cost of purchasing 3 scoops of ice cream on a waffle cone with no toppings.
Boolean variables: isWaffleCone, includesToppings
Variables:
- numScoops = 3
- cost = 1.5 * numScoops
Conditions:
- IF (isWaffleCone):
  - IF (includesToppings): cost = cost + 3
  - ELSE: cost = cost + 1
- ELSE:
  - IF (includesToppings): cost = cost + 2
Given isWaffleCone = true, includesToppings = false:
- cost = 1.5 * 3 = 4.5
- Since isWaffleCone is true, the first IF condition is met.
- Since includesToppings is false, the ELSE condition within the first IF is met.
- cost = cost + 1 = 4.5 + 1 = 5.5
Therefore, the cost of purchasing 3 scoops of ice cream on a waffle cone with no toppings is $5.50.

Lists

AAP-2.N(b): Evaluate expressions that use list indexing and list procedures.
AAP-2.O(b): Determine the result of an algorithm that includes list traversals and involves elements of a list
AAP-2.N.1: Exam reference sheet provides basic operations on lists.
AAP-2.N.2: List procedures are implemented in accordance with the syntax rules of the programming language.
AAP-2.O.1: Traversing a list can be complete or partial.
AAP-2.O.2: Iteration statements can be used to traverse a list.
AAP-2.O.3: Exam reference sheet provides pseudocode for loops.
AAP-2.O.4: Knowledge of existing algorithms that use iteration can help in constructing new algorithms.

List Operations

If a list index is less than 1 or greater than the length of the list, an error message is produced and the program terminates.
aList[i] or aList i:
- Accesses the element of aList at index i.
- The first element of aList is at index 1.
x ← aList[i] or x ← aList i:
- Assigns the value of aList[i] to the variable x.
aList[i] ← x or aList i ← x:
- Assigns the value of x to aList[i].
aList[i] ← aList[j] or aList i ← aList j:
- Assigns the value of aList[j] to aList[i].
INSERT (aList, i, value) or INSERT aList, i, value:
- Inserts value at index i in aList.
- Values at indices greater than or equal to i are shifted one position to the right.
- The length of the list is increased by 1.
APPEND(aList, value) or APPEND aList, value:
- Appends value to the end of aList.
- The length of aList is increased by 1.
REMOVE (aList, i) or REMOVE aList, i:
- Removes the item at index i in aList.
- Values at indices greater than i are shifted to the left.
- The length of aList is decreased by 1.
LENGTH (aList) or LENGTH aList:
- Evaluates to the number of elements in aList.
FOR EACH item IN aList or FOR EACH item IN aList:
- The variable item is assigned the value of each element of aList sequentially, in order, from the first element to the last element.

Practice #1

Given a procedure LEN(str) that returns the number of characters in a string str, determine the output for the code segment below:

Code segment:

words ← ["old", "car", "unusual", "new", "bold", "far", "away"]
index ← 1
FOR EACH word IN words
{
    IF LEN(word) = 3
    {
        index ← index + 1
    }
    ELSE
    {
        REMOVE(words, index)
    }
}
DISPLAY words

The words list = "unusual", "bold", "away"
index = 3
unusual, bold, away

Practice #2

If the list words contains ["song", "book", "video", "book"], what will the following code output?

index ← 1
n ← LENGTH(words)
REPEAT n TIMES
{
    IF words[index] = "book"
    {
        INSERT(words, index, "read")
        index ← index + 1
    }
    index ← index + 1
}
DISPLAY words

The correct answer is B. ["song", "read", "book", "video", "read", "book"]

Binary Search

A binary search algorithm is structured and operates to efficiently search sorted data.
AAP-2.P: For binary search algorithms:
- Determine the number of iterations required to find a value in a data set.
- Explain the requirements necessary to complete a binary search.
AAP-2.P.1: Binary search starts at the middle of a sorted data set and eliminates half of the data; this repeats until the value is found or all elements are eliminated.
AAP-2.P.2: Data must be in sorted order.
AAP-2.P.3: Binary search is often more efficient than sequential/linear search when applied to sorted data.

Sequential Search

Examines each element in a list, starting with the first element, until the target is found or the end of the list is reached.
Elements do not need to be in any order.
Example: Searching for the number 27 in the list 10, 14, 19, 27, 31, 35, 42 would take 4 comparisons.

Binary Search

Put the numbers in order (ascending or descending).
Start the search by looking at the middle number first.
Middle Index = {(Highest Index + Lowest Index) \over 2 }, truncate the decimal part to round down if needed.

Divide and Conquer

Binary search is about divide and conquer, dividing each range by 2.
Example: A list of 600 sorted numbers requires a maximum of 10 list elements to be examined (600/2, 300/2, 150/2, 75/2, 38/2, 19/2, 10/2, 5/2, 3/2, 2/2).

Practice Questions

Set 1:
1. Middle number in a binary search of 1, 5, 16, 19, 22, 31: 16 (index 3).
2. Second number looked at if the target is more than the middle number: 22 (index 5).
3. Comparisons to find 31 in a binary search: 3; in a sequential search: 6.
Set 2:
1. Lists suitable for binary search:
  - I. [“Anthony,” “Carlos”, “Donte”, “Hayat”, “Laura”, “Yoseph”]
  - IV. [6, 8, 13, 64, 75]
2. Maximum number of list elements to look at in a list of 200 sorted numbers: 8.

Developing Procedures

AAP-3.C: Develop procedural abstraction to manage complexity in a program by writing procedures.
AAP-3.C.1: The exam reference sheet provides the syntax for defining a procedure that takes zero or more arguments.

Updating Grades

Sample code segment updating grades, which the programmer wants to be able to reuse regardless of the point totals of the quiz.

Example:

currentGrade ← currentPoints / 40
currentGrade ← currentGrade * 100
IF currentGrade > quizGrade
{
    quizGrade ← currentGrade
}

To encapsulate in a procedure, determine the name and parameters:

    PROCEDURE updateQuiz(quizGrade, currentPoints, totalPoints)

The procedure needs to know the quiz grade, current points, and total points.
Even though currentGrade shows up in each program segment, we can calculate the current average on the quiz with the above information, so we do not need to include
it as a parameter.

Implementation:

PROCEDURE updateQuiz(quizGrade, currentPoints, totalPoints)
{
    currentGrade ← currentPoints / totalPoints
    currentGrade ← currentGrade * 100
    IF (currentGrade > quizGrade)
    {
        quizGrade ← currentGrade
    }
    RETURN (quizGrade)
}

Robot Example

Write a procedure that will rotate the robot 180 degrees.
Implementation:
pseudocode PROCEDURE rotate180() { ROTATE_RIGHT() ROTATE_RIGHT() } // or PROCEDURE rotate180() { ROTATE_LEFT() ROTATE_LEFT() }

Lists

AAP-2.N(a): For list operations, write expressions that use list indexing and list procedures.
AAP-2.O(a): For algorithms involving elements of a list, write iteration statements to traverse a list

Finding minimum Value in a list

Create or access the list.
Make a variable to hold the minimum and set it to a potential minimum value.
Loop through the list.
Check each element to see if it is less than the minimum variable.
If the element is less than the minimum variable, update the minimum.
After all elements of the list have been checked, display the minimum value.
Implementation of the above points is listed below
Nums = [65, 89, 92, 35, 84, 78, 28, 75]
min ← nums[1]
FOR EACH score IN nums:

IF (score < min)
min = score
DISPLAY (min)
Implementation of the above points is listed below.

Sum of even numbers in a list

Write the code to find and display the sum of only the even numbers of a list called nums that contains integers.
Implementation of the above points are listed below.
Nums[5, 3, 8, 4, 7, 2, 1, 10]
sum ← 0
FOR EACH score IN nums:
IF (score MOD 2 = 0)
sum = sum + score
DISPLAY (sum)

Developing Algorithms By Modifiying Existing Algorithms

Famous Collatz Conjecture

Modify an existing algorithm to create a new one.
AAP-2.M.2: Knowledge of existing algorithms can help in constructing new ones.
AAP-2.M.3: Using existing correct algorithms as building blocks has benefits such as reducing development time and simplifying the identification of errors.
Challenge: Create an algorithm that will start with any positive integer n and display the full sequence of numbers that result
form following the Collatz Conjecture
If n MOD 2 = 0 The the number is even, Or else the number is odd where you follow the procedure
Implementation of the above points are listed below.
Challenge: Create an algorithm that will start with any positive
integer n and display the full sequence of numbers that result
from following the Collatz Conjecture