1. The lesson here is that our choice of abstractions, in this case the use of parameters in our Logo commands, affects the kinds of problems we can solve and how we solve them. That is, our choice of abstractions have an enormous impact on our algorithms. In addition, procedural abstraction (both with and without parameters) makes algorithms easier by raising the level of abstraction.Describe in your own words, with a specific example from Logo, how our choice of abstractions (commands) in this lesson provides us with the ability to solve problems that couldn't be solved with the abstractions (commands) used in Logo Part 1. Logo Part 2 now allows you to turn at angles other than 90 degrees, allowing user to draw more than squares and rectangles. Also, the length of the lines can be changed by the user thanks to parameters. Logo Part 2 solved the problem of limitation of shapes and ease in changing line length.
5.3 Search Algorithms Reflections
1. (POGIL) Define a pseudocode algorithm that will efficiently play the guessing game. Set number to random integer from 1 to 100 Set guess to 50
Repeat until guess is equal to number
If guess is less than number set guess to guess times 1.5
Else set guess to guess divided by 2
If guess is equal to number stop program
2. (POGIL) To guess a number between 1 and 100, what's the maximum number of guesses your algorithm would take? The maximum number of guesses is 7 guesses.
3. (POGIL) To guess a number between 1 and 500, what's the maximum number of guesses your algorithm would take? The maximum number of guesses is 8 guesses.
4. Suppose you have a deck of cards and you want to find the Ace of Spades. If the deck is shuffled, which is the best search algorithm to use and why? Linear searching because the is an unordered set, thus binary searching would not work (unless you were really lucky).
5. Give an example of a search problem you encounter in everyday life. Does it use sequential, binary, or some other search? I have encountered search problems looking for things on Google because I may not use the perfect key words.
5.4 Sorting Algorithms Reflections
1. Bubble and Merge Sort are referred to as comparison sorts because the values of the two pieces of data are compared during each step. Why are the radix and bucket sort not comparison sorts? The radix and bucket sort are not considered comparison sorts because rather than comparing the values of the cards and ordering them by value, they place cards into buckets with the same value. 2. Which sort do you think would be the fastest if you had to sort more than one deck of cards (i.e. as the amount of data to be sorted increases)? Why? Bucket sort is the most efficient because rather than comparing the values and going through the deck multiple times, the cards are placed in buckets based on value and then sorted, which is much quicker.
5.6 Debugging Pong Game Reflections
1. For each of the 3 bugs in the Pong game, explain what the bug was, how to fix it, and the type of error (semantic or syntax). The first bug found in the Pong game was in the event handler When Ball1.EdgeReached. The code said when an edge greater than or equal to negative 1 was hit, the ball would be disabled and a Game Over label would be displayed. This means that the only safe edge to hit would be Edge -3. To fix the bug, simply change "greater than or equal to" to just "equal to" since Edge -1 is the bottom and presumably the edge that is meant to cause the game to be over. This is a semantics error. The second bug is in the ButtonReset.Click event handler. When the button is clicked the ball is moved to X: canvas width/2, Y: ball radius. However, the button should cause the ball to move to X: canvas width/2, Y: 0. This is a semantics error. The final bugs occur in the ButtonStart.Click event handler. The ball heading is set from 0 to 180 meaning the ball could start at 0 degrees or 180 degrees, thus the ball would bounce back and forth at the top of screen. To fix the bug, change 0 to 225 and 180 to 315. This is a semantics error, because the programmer wanted to give the ball a larger range of movement but did not account for the little glitch that would occur if the random integer was 0 or 180.
5.7 Analyzing Algorithms Reflections
Search 1 used a linear search algorithm. It was slower than Search 2 and linear search is slower than binary search.
Search 2 used a binary search algorithm. The maximum time it took was 93 milliseconds, the minimum time search 1 took was 310 milliseconds. Binary searches are always quicker than linear, thus search 2 must be binary.
Sort 1 was a bubble sort because it took the longest out of the 3 sorts, and bubble sort is the slowest sorting method.
Sort 2 was bucket sort since bucket sort is the fastest sorting method and Sort 2 was the fastest of the 3 sorts.
Sort 3 was merge sort since merge sort is quicker than bubble sort but still slower than bucket sort. Sort 3 took longer than Sort 2 but took less time than Sort 1.
5.8 Limits of Algorithms Reflections
1. (POGIL) A password scheme consists of a minimum password length and the different types of symbols (i.e., letters, numbers, specials) that can be used in the password. Using the Password Strength Calculator, determine the optimal scheme for withstanding a brute force attack of at least 10 years by an ordinary PC performing 100 million tests per second. At a minimum, a 12 digit password with just uppercase letters or with just lowercase letters could take up to 30 years with 100,000,000 guesses per second. Most websites use a 16 digit password scheme with uppercase and lowercase letters, and numbers. That type of password would take up to around 5.1 billion years to crack.
2. (POGIL) According to an article from 2012, a password-cracking computer can try 350 billion passwords per second. How would you have to modify your scheme to withstand a 10-year attack by this specially designed computer? Using the same 16 character password with uppercase and lowercase letters, and numbers, a computer guessing 350 billion times per second would take up to around 4.3 billion years.
3. (POGIL) That article was written in 2012, almost 5 years ago. Password cracking technology has probably gotten a lot better. Suppose the number of passwords that can be checked per second doubles every year, use the Password Strength Calculator to determine an optimal password scheme for the year 2020? An optimal password in the year 2020 could STILL follow the 16 character, uppercase, lowercase, number scheme and take up to around 16 million years. If you upped the max character limit to 20, it would take up to around 250 trillion years to crack.
4. (POGIL) For routes starting and ending at Trinity College, identify the nearest neighbor route and the optimal route. What does this show you about the nearest neighbor heuristic? The nearest neighbor route is 8.2 miles. The optimal route is 7.6 miles. This shows that the nearest neighbor heuristic is not always correct and can be off.