Midterm Review Session
Administrivia
Midterm Project due Sunday.
In Lab Midterm on Thursday during the lab you are assigned to on CalCentral. Labs 14 and 15 is due Monday.
Paper Exam Thursday night 6-8pm in 2050 Valley Life Sciences Building.
Two double-sided handwritten 8” x 11” cheat sheets.
Follow these slides on: http://tinyurl.com/cs10su17midtermp1
Programming Concepts
Number Representation
We can represent any values in any base.
We denote different bases with a prefix
0b (for binary)
0x (for hexadecimal)
We can convert numbers to and from different bases with a simple algorithm
Let’s look at some examples
Number Representation (Examples)
Convert the number 27 (in decimal) into its binary and hexadecimal equivalents
Number Representation (Examples)
Convert 0b10101 into decimal and hexadecimal
Number Representation (Examples)
Convert 0x1a into decimal and binary
Domain and Range
Domain -- How we specify the input to a block or function.
Range -- How we specify the output or result of a block or function.
Think:
What type of things can this particular block accept in order to work properly? (Domain)
What is this block capable of producing, or outputting? (Range)
Domain and Range (Examples)
What is the domain of the following block? In other words, can you determine the type of mystery, mystery2, and mystery3?
What is the domain AND range of the following block?
HOFs
Map -- Apply a particular operator to each of the elements of the input list.
The result of the operator applied with the first item of the list becomes the first item of the output list.
The output (or Range) will be a list of the same length as the input list (or Domain)
Keep -- Apply a particular predicate to each of the elements of the input list, and keep them in the output list if the predicate evaluates to true.
Similar to the idea of a filter; get rid of the items that don’t satisfy the provided condition
The output will be a list of size less than or equal to the size of the input list
Combine -- Squish all of the items in the provided input list into one item, according to the provided operator.
Think of a big ball pit: Pick up two balls, apply the operator to them, and place the resulting ball back into the ball pit. Pick another two balls, and repeat the process until there is only one ball left. The one ball remaining is the result!
HOFs (Examples)
Write a block that reports the sum of the numbers in a list that are divisible by 4
For example, list(1, 2, 4, 7, 8, 10, 12) evaluates to 24 (4 + 8 + 12)
HOFs (Examples)
Write a block that reports the sum of the numbers in a list that are divisible by 4
For example, list(1, 2, 4, 7, 8, 10, 12) evaluates to 24 (4 + 8 + 12)
HOFs (Examples)
Write a block that reports a list where each item is a list (a.k.a nested), containing an item greater than 5.
For example, list(3, 5, 8, 9) becomes list( list(8), list(9) )
HOFs (Examples)
Write a block that reports a list where each item is a list (a.k.a nested), containing an item greater than 5.
For example, list(3, 5, 8, 9) becomes list( list(8), list(9) )
Algorithmic Complexity
Definition: How much computation is required for an algorithm to run, or execute (a.k.a Runtime).
Big-O Notation: How we express an algorithm’s complexity.
O(1), O(logN), O(N), O(N^2), O(N^3), … , O(2^N)
The above list is in order of growing complexity
The less complex the algorithm, the better it is! (More efficient)
If we didn’t care about complexity, many computational problems would require weeks, months, or even years to finish executing!
We can determine an algorithm’s complexity by analyzing its code structure.
Algorithmic Complexity (Examples)
What is the complexity of the following block?
Algorithmic Complexity (Examples)
What is the complexity of the following block?
Quadratic
Algorithmic Complexity (Examples)
What is the complexity of the following block?
Algorithmic Complexity (Examples)
What is the complexity of the following block?
Constant. The loop only runs 6 times in the worst case.
Fractals
Fractal #1
level 0
level 1
Base Case
Recursive Case
level 2
Fractal #2
level 0
level 1
Base Case
Recursive Case
level 2
Fractal Solutions
Lectures
Welcome and Abstraction
Detail Removal
“The act or process of leaving out of consideration one or more properties of a complex object so as to attend to others.”
Generalization
“The process of formulating general concepts by abstracting common properties of instances”
Abstraction is one of the big ideas of computing and computational thinking
Think about driving. How many of you know how a car works? How many can drive a car? Abstraction!
Procedures
Procedure: A sequence of instructions that are packaged into a single unit.
Function: A procedure that takes 0 or more inputs, returns an output, always returns the same output if given the same inputs, and has no side effects.
Procedures
Three Types of Procedures in Snap!
Command
No outputs, meant for side-effects.
Can never be a function.
Reporter
Similar to a command, but reports an output.
If output is always the same for a given input, and it has no side effects, then it is a function.
Predicate
Special type of reporter, but can only report a boolean.
Programming Paradigms
Functional -- No side effects. The block will yield the same result for a provided parameter, no matter how many times it is executed.
Imperative -- Side effects. The block might not yield the same result for a provided parameter upon multiple executions.
Object Oriented -- Data is thought of as objects. Sprites are an example of this (message passing with broadcast)
Declarative -- Logic programming and query-based languages (SQL). Provide the computer with a set of queries to yield results. For example, logic puzzles / Einstein’s Riddle
Binary
Humans think about numbers in decimal; computers think about numbers in binary
Base conversion to go between
Hex is more human-readable than binary
All information on a computer is translated to binary
Nice because big difference between “high” and “low”
Binary encoding can represent anything!
Program needs to know how to interpret bits
Lists, Programming Paradigms
Scoping
Variables are fundamental tools for programming. They allow us to store values and perform complex, abstract computation!
The scope of a variable tells us where the variable is accessible, and what value it refers to.
Scopes communicate with each other by calling other functions and reporting values.
Accessing variables outside of the current scope results in a side effect. Can be useful, but better to stay away!
Algorithms
A computational problem is a problem statement with desired I/O relationship
An algorithm describes a computational procedure that satisfies/solves a computational problem
An implementation is an algorithm written out in a programming language (unambiguous, executable)
Properties of algorithms:
Can be combined to make new algorithms
Knowledge of existing algorithms & correctness help
There are many algorithms to solve the same computational problem
New algorithms can yield insight into the problem
Algorithmic Complexity
When developing an algorithm, could optimize for
Simplest
Easiest to implement?
Most efficient
Uses up less resources
Gives most precision
And more…
There are empirical and formal methods to verify efficiency and correctness
Some algorithms cannot be implemented efficiently
In CS10 we’ll consider the following running times:
Functions as Data
We can also make our own custom HOFs by adding functions as data.
To treat a function as data, you must ringify it:
Call vs. Run
You can add inputs to your ringified functions and call them using the call and run blocks
Run: Runs a command block, command block itself
Call: Calls a reporter, reporter itself
Anonymous Functions
Social Implications of Computing : Privacy
-Information footprint is larger than you think!
-No anonymity on the internet
-Information about you on the internet can and will be used by somebody in their interest (and this may be against your own interest!)
-Communication over a network, unless strongly encrypted, is never just between two parties
-Sharing releases control
-Online world and “real world” are inseparable
-You can’t avoid having an information footprint by not going online
Testing
Functional Programming makes testing easier!
Can test individual modules (i.e. Unit Tests)
It’s always a good idea to refactor!
Makes code easier to maintain in the future
Build regression tests with the ‘Test Block’, and use them frequently!
Software mistakes happen...and they can be fatal
Thoughtful testing is VERY IMPORTANT!!
Recursion I
Recursive solutions involve two major parts:
Recursion II
Procedure calls get local copies of variables
Exception: lists!
Mutating lists can cause unwanted side effects
Recursion: identify both the way to reduce/simplify the problem (recursive case) and the stop conditions (base)
For reporters, recursive call done in 3 parts
Divide, Invoke, Combine
Multiple invocations can cause problem to grow exponentially
Recursion is never necessary, but can give cleaner, simpler solutions sometimes
Cyberpolitics
Surveillance and espionage are made easier with computing
Various aspects of computing are integrated into the foreign policies of many states
Countries use cyberattacks to express their power and enforce their will on other countries
Critical infrastructure attacks are worse-case attacks that disable power stations
Could drastically change within the next couple decades
Programming Exercises!
Warm-up Problem
Create a function called “foobar sum” that sums all of the numbers that are multiples of 8 or 10 from a list of numbers.
Try writing the function iteratively, with HOFs, and recursively.
Warm-up Solution (HOF)
Warm-up Solution (Iterative)
Warm-up Solution (Recursive)
Recursively Remove Items from a list
Remove the items in the first list from the items in the second list, use recursion!
Recursively Remove Items from a list
Finding max
Find the max of all the numbers in the input list both iteratively and using HOFs.
Challenge: Also find the max recursively.
Finding max Solution (HOF)
Finding max Solution (Iterative)
Finding max Solution (Recursive)
Max Vowels
Using HOFs, find the words in a list that have the most vowels. Do not alter the original list.
Hint: consider making a helper block that gets the number of vowels from a single word, and a block that given two numbers, reports the larger one.
Max Vowels Solution
You are filling a pack with supplies, and are trying to figure out the number of ways you could do so. Given an input of the maximum weight (in pounds) you can carry, and the weight of the items you can bring (items can be used multiple times):
Bottle of water: 1 pound
Food rations: 2 pounds
Zombie disintegration ray (single use): 4 pounds
Zombie repellant: 9 pounds
Useless bag of haunted bricks: 15 pounds
Write a recursive algorithm to give the possible number of combinations.
Zombie Supplies
Zombie Supplies