Notes

Algorithms

Compare python code. Do they yield the same results?

print("What did you roll on the dice?")
diceRoll = int(input())
if diceRoll >= 4:
    print("Nice roll!")
else:
    if diceRoll >= 2:
        print("Meh... You can do better")
    else:
        print("That was not a great roll!")

print("What did you roll on the dice?")
diceRoll = int(input())
if diceRoll >= 4:
    print("Nice roll!")
if diceRoll >= 2:
    print("Meh... You can do better")
if diceRoll < 2:
    print("That was not a great roll!")

Notes

The notes then gives a potential adjustment to code block 2 to correct the logic error

 print("What did you roll on the dice?")
diceRoll = int(input())
if diceRoll >= 4:
    print("Nice roll!")
if diceRoll >= 2 and diceRoll < 4:
    print("Meh... You can do better")
if diceRoll < 2:
    print("That was not a great roll!")

Conditionals and Booleans

Using AND and NOT operators can be helpful. The following two code blocks (pseudocode) are identical.

IF (isHoliday)
{
    school⟵false
}
ELSE
{
    IF(isWeekday)
    {
        school⟵true
    }
    ELSE
    {
        school⟵false
    }
}

This checks if there is a holiday. If this condition is true, the school condition is false. If false, the else condition is executed with a nested if statement about there being a weekday. If true, school is true (and if not, false).

Using AND and NOT can reduce this to a single line of code:

school⟵((NOT (isHoliday)) AND (isWeekday))

Using the AND operator means both conditions must be true to yield true. The following are the conditions:

Practice 1

Algorithms to sum all single-digit odd numbers. Do they work as intended?

sum⟵1
counter⟵3
REPEAT 4 TIMES
{
    sum⟵sum + counter
    counter⟵counter + 2 
}
DISPLAY sum

sum⟵0
counter⟵9
REPEAT UNTIL counter < 1
{
    sum⟵sum + counter
    counter⟵counter - 2
}
DISPLAY sum

Using different algorithms to accomplish the same task can instill creativity within a developer, which may allow them to come up with solutions to novel problems later.

Notes 2

Example algorithm: Robots

Need to move the robot forward, turn right, move forward, turn left…

Need to reach the goal

PROCEDURE movemntSeq(n)
{
    REPEAT n TIMES
    {
        MOVE_FORWARD()
        ROTATE_RIGHT()
        MOVE_FORWARD()
        ROTATE_LEFT()
    }
}
movemntSeq(4)

Practice 2

Display says

Choose algorithm with selection and iteration to determine correct cost of an item

Option A

DISPLAY (“What is the cost of the item?”)
cost←INPUT ()
IF (greenTag)
{
    cost ← 0.75 * Cost
}
IF (redTag)
{
    cost ← 0.40 * Cost
}
cost ← 1.10 * cost

Option B

DISPLAY (What is the cost of the item)
cost←INPUT ()
IF (greenTag)
{
    cost ← 0.75 * Cost
}
IF (redTag)
{
    cost ← 1.10 * cost
}
cost ← 0.40 * Cost

Notes

Option A works as intended

Notes 3

Robot Challenge!

Notes

### Notes 4

Forms of search:

Practice

1) Which is a plausible way to pattern numbers for a binary search? a. [1,4,5,2,3] b. [24,22,23,28,30] c. [5,6,7,8,2] d. [1,2,3,4,5]

Note: Only Option D is in ascending order. Therefore, this option is correct.

2) How many checks would it take to print 20 with sequential search?

[1, 3, 4, 5, 7, 8, 10 ,20]

It will take 8 searches to print 20, since 20 is the 8th entry of the list. Sequential search will reach this element last.

3) How many checks will it take to print 30 using binary search?

[1, 2, 3, 4, 6, 8, 9, 11, 30]

Let’s use tables. Apparently there’s an even number of entries issue

I checked two simulations and they checked the item to the left of the middle for even numbers of elements.

Check number Numbers checked
1 6
2 2 and 9
3 1, 3, 8, and 11
4 4 and 30

It will take 4 checks to get 30 using binary search

4) Using Binary Search how many checks would it take to find the word kiwi.

[Apple, Banana, Kiwi, Mango, Strawberry]

Note: Kiwi is the middle entry, so theoretically it will be found first (in one search). The entry “kiwi” will not be found since it’s not in the list (elements are case sensitive). Rap: I did this in-class.

Final Hacks

1) Write this boolean in form of conditional statement (IF/ELSE) stayInside⟵((isCold) OR (isRaining))

This is in pseudocode, so I’ll use pseudocode to be consistent.

IF(isCold)
{
    stayInside ← True
}
ELSE
{
    IF(isRaining)
    {
        stayInside ← True
    }
    ELSE
    {
        stayInside ← False
    }
}

2) Make an algorithm utilizing selection/iteration to represent a player’s turn (in a game). Parameters:

I’ll use pseudocode again just because that’s the only programming language I’ve seen in the lesson.

PROCEDURE takeTurn()
{
    score ← 0
    REPEAT 4 TIMES
    {
        temp ← RANDOM(1, 10)
        IF (temp > score)
        {
            score ← temp
        }
    }
    DISPLAY(score)
    RETURN(score)
}

3) Make an algorithm to make the arrow reach the gray square

The only required movements are forward movement and right turns. This is easier than the example in the notes.

IF(CAN_MOVE(forward))
{
    MOVE_FORWARD()
}
ELSE
{
    IF(CAN_MOVE(right))
    {
        ROTATE_RIGHT()
        MOVE_FORWARD()
    }
}

4) Make a binary search tree of the list [1,2,3,4,6,9,11,69]

Even number of entries issue. Assume the entry to the left of the middle is selected. Here’s your png.

5) Explain how to find the number 69…

There are an even number of elements. According to two simulations I found, lists with even numbers of elements start with the element from the left of the middle.

For search 1, select 4. This splits the list into two portions.

The left portion has middle element 2 for search two. The right portion has 4 entries and must select the element left of the middle (9) for search 2.

For search 3, the left portion is split into two portions with one element each. Select 1 and 3. The right portion is split into two portions, one with a single element (6) and one with two elements (pick left element 11)

For search 4, 69 is selected.

6) Make a diagram explaining how you found the list (using equations, not the tree)

I’ll assume this question is referring to element 69. This is a little bit confusing. Honestly this is just about the same thing as my response to (5), just being formatted in something akin to a flowchart

7) Arrange the strings in order used for binary search

[“store”, “Market”, “Walmart”, “Target”, “Ralphs”]

I’ll arrange alphabetically. I don’t know if this is supposed to be case-sensitive.

[“Market”, “Ralphs”, “store”, “Target”, “Walmart”]

Then I found Khan Academy and Princeton University and even Wikipedia and apparently I misunderstood binary search. The CollegeBoard makes those search trees to work with all possibilities, but not all the elements in the tree are actually searched in a single instance (only those leading to the desired element). The way binary search works is it compares the list’s element to a desired element. Say the desired element is greater than the element in the list. That element and all other elements are eliminated since they would surely not contain the entry. Repeat. 8) Explain why binary search is more efficient than sequential search.

Binary search is more efficient than sequential search since there are less required checks to find a given element of a list. This is because binary search eliminates around half of a list’s (nonmatching) elements per search, whereas sequential search eliminates one nonmatching element per search.

9 (open question)) [64,36,16,11,9] Explain which number you are finding, how many check it would take, and make a binary search tree

Note; The list is sorted in descending order. This is fine.