More Snap
SNAP is a multi-paradigm language, meaning it incorporates several programming paradigms:
- Functional programming
Evaluate an expression and use the resulting value for something.
cascading values compose functions - Imperative programming (sequential)-computation in a series of steps
examples:Pascal and C
First do this and next do that
mutation is allowed.
This is a harder way to think, harder to debugf(x)=(x+3)*√x ans=x ans=√ans ans=(x+3)*ans return ans
- Object-Oriented Programming (OOP)
examples:Java, C++
Objects as data structures
attributes and behaviors
easy to build massive project in a group way
classes an instances
inheritance
Send messages between objects to simulate the temporal evolution of a set of real world phenomena. - Declarative
example:prolog
You tell the system some rules and then you can question it about the rules.
Tell you what you want, not how to do it. What is forefront. subcategories: constraint
logic
Answer a question via search for a solution.
new counter (this is a new instances of counter) It is a function that takes no inputs, but returns an object changes count by 1
Data Types
A data type is first class in a programming language if data of that type can be- the value of a variable
- an input to a procedure
- the value returned by a procedure
- a member of a data aggregate
- anonymous (not named)
A fundamental design principle in SNAP! is that all data should be first class. If it's in the language, then we should be able to use it fully and freely.
Lists are a type of data structure, a particular way of storing data. Many objects can be easily stored in a list, and so lists have become a very useful and ubiquitous data structure in computer science. For example, if you are developing a game and you want to keep track of the people that have played your game, you might keep their names in a list.
SNAP does not allow you to make lists in the same way as Scratch. If you want a global named list, make a global variable and use the set block to put a list into the variable:
There are two ways to create lists in SNAP.
- The Imperative Programming approach, familiar to Scratch users. This is based on a set of command blocks that modify a list.
- The Functional Programming approach, which uses reporter blocks, not command blocks, to build up a list values. In a functional program, you often use recursion to construct a list, one item at a time. The in front of block makes a list that has one item added to the front of an existing list, without changing the value of the original list. A nonempty list is processed by dividing it into its first item (item 1 of) and all the rest of the items (all but first of), which are handled through a recursive call:
There are two ways to specify a list in data types:
- Passing a list:
-
Allowing multiple inputs:
- Open SNAP
- Create this custom block and test it out:
In this script, you first create a temporary variable, then put an empty list in it, then you go through the items of the input list using the add ... to (result) block to modify the result list, adding one item at a time, and finally reporting the result.
Answer this question: Does the above code represent the imperative or functional programming paradigm? Explain your answer.
- Look at the functional programing example provided in the introduction. Create your own version of the evens block, but have your function should check if the item in the list is divisible by a number that the user provides:
- Build an evens list block using the keep block:
The keep block takes a Predicate expression as its first input, and a list as its second input. It reports a list containing those elements of the input list for which the predicate returns true. Notice two things about the predicate input:- It has a grey ring around it.
- The mod block has an empty input.
Keep puts each item of its input list, one at a time, into that empty input before evaluating the predicate. (The empty input is supposed to remind you of the “box” notation for variables in elementary school: ☐+3=7.) The grey ring is part of the keep block as it appears in the palette. What the ring means is that this input is a block (a predicate block, in this case, because the interior of the ring is a hexagon), rather than the value reported by that block. Here’s the difference:
Evaluating the = block without a ring reports a number; evaluating the block with a ring reports the block itself. This allows keep to evaluate the = predicate repeatedly, once for each list item.
Answer this question: Is keep a higher order block? Explain your answer. - It has a grey ring around it.
- Here is an example of combine
These are the blocks that combine can use
Answer this question: Why can't combine use subtraction or division? -
Make a list of lists. See if you can access a particular element of a list.
- Create a players list
- Put together these blocks and in a text file describe what the code does:
- Add at least four names.
- Say hello to all the names from the players list. Separate each name by a comma and separate the second to last from the last with the word "and."
- Put together these blocks and in a text file describe what the code does:
A block that takes another block as input is called a higher order block.
SNAP provides three higher order blocks for operating on lists:
Here are examples of how map works:
Exercises
Algorithms
An algorithm is any well-defined computational procedure that takes some value or a set of values as input and produces some value or set of values as output.Algorithms are conceptual definitions of how to accomplish a task and are language agnostic.
Commonly Used Algorithms
- Luhn
credit card validation. - Damerau-Levenshtein distance
Spell-checker - PageRank
Google's way of measuring "reputation" of web pages - EdgeRank
Facebook's method of determining what appears in your newsfeed
Choosing a technique
Most problems can be solved in more than one way, meaning that those problems have multiple algorithms to describe how to find the solutionNot all algorithms are equally good. Very often you have to make a trade-off when you select a particular one to use to solve a problem.
Speed is often a priority. Sometimes the trade off involves resources or probability of returning the right answer Total correctness means that the answer will always be correct, but the algorithm may never report an answer.
Probabilistic algorithms have a certain probability of returning the right answer (think predicting outcomes of political races or weather). The more you run them, the closer you will get to coming up with a correct answer.
Problem Solving Approaches
- Brute force
- Top down- dividing the problem into smaller subproblems.
- Bottom up-Start with a simple solution and build up to complex ones. Building individual buildings instead of a campus (Saint Ann's)
- Solidify understanding of what an algorithm is and why they’re important to computer science and other fields.
- Gain a basic understanding of why certain algorithms perform better than others.
- There’s often more than one way to solve the same problem. Certain solutions will be superior to others, but very often choosing a solution will require evaluating a list of trade-offs relevant to your particular situation.
- Practice implementing algorithms that were discussed verbally.
- Memoization is a technique that can be used for improving the performance of algorithms with repeated calculations at the expense of a higher memory requirement.
- Hiding algorithmic details behind a layer of abstraction makes it easier to upgrade or adjust your implementation in the future
An algorithm is a set of steps that allows you to solve a particular problem. While these steps are referred to as algorithms in computer science, they are similar to recipes in a kitchen, or the protocols followed by professions.
UPS Truck Drivers have “340 Methods,” the UPS handbook for drivers, that describes 340 different protocols that should be followed and how long each one should take.
Salesman often have scripts to follow when making a sales call. The scripts describe how to open the conversation (and possibly more) in order to increase the odds of gaining a client.
Subway Sandwich Artists have a series of signs stuck to the inside of the counter that prompt the employees with what should be said.
Do-It-Yourself projects all come with some sort of instructions. Directions, such as those for assembling a piece of furniture or a Lego kit, are algorithms.
Computer science algorithms are conceptual solutions to a problem (such as sorting a list), whereas the implementation of an algorithm is the actual code that brings the solution to life. The implementations themselves can typically be written in almost any programming language and run on any computer; the concepts behind the algorithm are not affected by these types of conditions.
The call block has a right arrowhead at the end; clicking on it adds the phrase with inputs
and then a slot into which an input can be inserted. If the left arrowhead is used to remove the last input slot, the with inputs disappears also. The right arrowhead can be clicked as many times as needed for the number of inputs required by the reporter block being called.
If the number of inputs given to call (not counting the Reporter-type input that comes first) is the same as the number of empty input slots, then the empty slots are filled from left to right with the given input values. But if call is given exactly one input, then every empty input slot of the called block is filled with the same value:
The provided framework includes
, which will allow you to sort a list. Sorting the list will take a decently long time, so we'll want to do it as few times as possible. How many times will you need to sort the list for each test run?
Searching through sorted data, while faster, also requires a more complicated block. You won't need to search through every space in the list anymore -- you can assume that many of them won't work. You can keep track of the range of numbers in a list that are a possible solution to the problem by recording the minimum and maximum slots that could possibly contain our number. This range should shrink after each guess because you can throw away the half of the numbers on the wrong side of the center point. Here's how things should generally work:
Assignment
Using the framework provided, implement a BYOB block in the Unsorted sprite that finds a number in a list of unsorted numbers using the strategy that we discussed. The block should accept the target number (the "needle") and a full list of numbers (the "haystack") as arguments, and return the index of the number’s position in the list. What was the strategy we discussed for unsorted lists, and how could you implement it in BYOB? Fill in a separate block for the sorted approach and implement it as well. Use the framework to determine how their running time changes as the list size increases. Which is faster for a list of size 5? 50? 500? 5000? Why do you think this is?Unsorted Lists
Unsorted data doesn't give you a lot to work with. Your knowledge is limited to strictly the most obvious information: the numbers themselves. This makes strategy somewhat non-existent; the best you can do, on average, is to simply start at the beginning and search through the list one by one. This approach can become incredibly slow if we're dealing with a lot of data, but is actually fairly quick when working with smaller amounts of data. In addition, the block is relatively straightforward to create and doesn't require the data to be put into a particular order to work. The block should return the location of the number in the list, or zero if the number doesn't exist in the list.Searching Sorted Data
You could say that putting information in a particular order (lowest => highest, for example) actually creates new information. Instead of being a simple list of numbers, sorting the information adds order and allows us to make additional assumptions that we weren't able to make before. This type of information is different from the numbers themselves: it is not stored in a variable or list, but becomes a property of the information itself. We can use the property to reduce the number of checks we have to do to find a particular number. The trade-off to this, however, is that we need to sort the list (which takes time) before we can make use of the order.The provided framework includes
, which will allow you to sort a list. Sorting the list will take a decently long time, so we'll want to do it as few times as possible. How many times will you need to sort the list for each test run?
Searching through sorted data, while faster, also requires a more complicated block. You won't need to search through every space in the list anymore -- you can assume that many of them won't work. You can keep track of the range of numbers in a list that are a possible solution to the problem by recording the minimum and maximum slots that could possibly contain our number. This range should shrink after each guess because you can throw away the half of the numbers on the wrong side of the center point. Here's how things should generally work:
-
The range of possibilities starts off including every number in the list (the minimum is position #1 and the maximum is the final position). Let's say that you're searching for the number 33 as shown in the diagram. Start your search around the middle of the list. Check the value of the number there.
-
If the number at the spot you searched is greater than 33, set the maximum to the slot before the one you just searched (after all, 33 CAN'T be on the larger side if it's is smaller than the one you just checked!). If the number is smaller than 33, set the minimum to the slot after the one you searched.
-
Check the middle position of your new range. Repeat step 2 for this new range and reduce the range further.
-
Continue to repeat steps 2 & 3 until either (a) you find the number you're looking for or (b) you get in a position where the minimum and maximum of the range are equivalent without finding the number. If (b) happens, it means that the number doesn't exist in the list.
