Notes
- Algorithms can be written multiple ways.
- Sometimes different algorithms can achieve the same results, so it’s good to accept a diversity of approaches to a problem.
- Algorithms can have their nuances, however. Minor changes in the code can yield major changes in the results.
- Conditional expressions can be booleans, and vice-versa.
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
- For inputs 4, 5, and 6, the first algorithm will only print Nice roll! since it fulfills the if condition of the roll being greater than 4; the else condition is ignored.
- For inputs 4, 5, and 6, the second algorithm will print Nice roll! and also Meh… You can do better. This is because these rolls will not only satisfy the if condition for the former statement (the roll is at least 4), but also that of the latter statement (the roll is at least 2).
- Given the nature of input programs, it is also possible to give negative inputs (which will be treated as less than 2), and integers greater than 6 (where the above notes on 4, 5, and 6 apply). It is also possible to enter strings and numbers with decimals, though this will output an error since the input is not an integer.
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:
- isWeekday (set to True)
- isHoliday (since there’s a not statement, the desired condition is False) If these are met, there’s school (as is logical)
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
-
Algorithm 1 starts with 1 as a sum and 3 as a counter, the first two single-digit odd numbers. 4 times, the counter is added to the sum and is increased by 2. The sum is outputted. This yields 1 + 3 + 5 + 7 + 9 (the counter is added 4 times). This seems to work as intended.
-
Algorithm 2 sets the initial sum to 0 and the counter to 9. Until the counter is less than one, the counter is added to the sum and decreases by 2. The sum is outputted. This yields 9 + 7 + 5 + 3 + 1, which is intended.
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
- Algorithms can be based off an idea and can be a combination/modification of existing algorithms
- Iteration: Repeating associated lines of code a set number of times or until a certain condition is fulfilled
- Selection: Code is run based on a condition; multiple options are often available.
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
- IF there’s a green tag = 25% off
- If there’s a red tag = 60% off
- 10% tax
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: If there’s a green tag, cost decreases by 25%. If there’s a red tag, cost decreases by 60%. Regardless, the cost is increased by 10% (the tax)
-
Option B: If there’s a green tag, cost decreases by 25%. If there’s a red tag, cost increases by 10%. Regardless, the cost is decreased by 60%
Option A works as intended
Notes 3
-
Modifying existing code can ease the development process
-
Algorithm: Process/rule set followed in calculations/problem solving (includes computers)
Robot Challenge!
Notes
- The algorithm is programmed so that if the robot cannot move forward, it can move right
- This will result in the robot getting stuck into a loop without reaching the goal
- According to the notes, adding a left-turn option should fix this issue. The algorithm should be programmed so the robot turns left when it can.
### Notes 4
Forms of search:
- Sequential search: iterate through all elements in a list (one-by-one). Often what humans do in real-life.
- Binary search: must arrange elements of list in order. The computer starts the search by splitting the list and comparing the middle value. It then does this again for each half of the list, so each search checks 2^(n-1) elements. Requires less searches to compare all the elements.
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:
- Each player gets 4 attempts for the highest number
- For each attempt, use a random number generator to select random integer from 1 to 10
- After 4 attempts, the greatest number is the score. End the turn.
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.