Summary of the principles covered in the course:
- computational thinking (aka critical thinking)
- using algorithms to solve problems: inputs => secret sauce => outputs
- Is the code any good? use the axes of correctness, design, and style to evaluate.
- abstraction, using layering to simplify problems (functions!)
- precision: considering all the possible edge cases when problem-solving
- fake news
- content regulation on social media platforms?
- keeping someone out of your resources 🕵️♀️
Password strength permalink
When length of password is 4:
- 10 x 10 x 10 x 10 for just digits - 10k options
- 52 x 52 x 52 x 52 for just letters (upper and lower) - around 7 million
- 94 x 94 x 94 x 94 all characters (digits, letters, symbols) - around 78 million
Iterating through all possible passcodes with python:
from string import ascii_letters, digits, punctuation
from itertools import product
for passcode in product(ascii_letters + digits + punctuation, repeat=4):
If you use an 8-character password instead, it's six quadrillions (six followed by fifteen zeroes) 💡
- Encryption is the scrambling of information so that it can’t be read without a key to decrypt it.
- End-to-end encryption means that the messages between the two parties involved are encrypted. So even if we are using a third-party chat or video service, the companies running them cannot decrypt or read the contents of our communications.
Decision making permalink
- Decision tree: used to represent the logic behind decisions, with questions being asked at each step and further questions or actions based on the answers to each.
- Minimax is a game-playing algorithm where every outcome has a value or score, and each player is either trying to maximize or minimize the score.
if player is X: for all possible moves: calculate score for board choose move with highest score else: for all possible moves: calculate score for board choose move with lowest score
there are 255,000 thousand possible games of tic-tac-toe
for chess, only considering the first four moves, there are 288 billion possible games
depth-limited minimax: uses an evaluation function which is used to estimate the expected utility of the game from a given state (limiting the path of branches we follow)
- The minimax algorithm is one type of search algorithm, where the goal is to find the next move in a game or solution to some problem (e.g., Google maps)
- depth-first search (DFS): follows a path, choosing randomly if a choice needs to be made, and going backward only if there are no more choices possible
- Breadth-first search : alternate taking each path, one step at a time, like searching outwards from the starting point. This will lead to finding the shortest possible path but also explore many unnecessary paths.
- Both of these are categorized as uninformed search - the algorithms don’t have additional information about the problem, apart from the very next steps they can make.
- In informed search: use knowledge about the problem to find solutions more efficiently with heuristics, some way of estimating solutions.
- Manhattan distance: the number of squares away from a distance (ignoring any obstacles)
- Greedy best-first: at each fork in the road, pick the path with the best value (e.g., the lowest Manhattan distance)
- A search*: pronounced “A star search”, uses both the heuristic value of the path, as well as the distance it has already gone for that path.
- Ideally, you'd look for a heuristic that's easy to calculate
Machine learning permalink
- Reinforcement Learning
- to make this algorithm more efficient, switch between explore (something new) and exploit (what it already knows) actions
E.g., epsilon greedy approach:
epsilon = 0.10 if random() < epsilon: make a random move else: make the move with the highest value
- Genetic learning: where the fittest organisms survive and evolve over time
make initial generation of candidates randomly repeat until successful: for each candidate: calculate candidate's fitness remove least fit candidates make new generation from remaining candidates
Neural networks permalink
- In the human brain, neurons pass signals to one another to perform computations.
- A neural network is a collection of neurons, and we can also simulate them digitally.
- Deep learning: refers to the use of these neural networks, combined with linear algebra, to solve some problem (e.g., handwriting recognition)
- The key to these algorithms is a large amount of data that leads to more accuracy
- Interpretability, the ability for humans to understand what the neural network is doing to come up with its outputs, is a concern.