What we covered today:
- Warmup and Test Suite
- Algorithms
- Chris' You Teach - Mindfulness in Programming
- Interview Questions I and II
- Homework - Code Binary Search in Ruby or Javascript
Here is quite a good visualisation.
Binary Search is a really common one. Here are the steps:
- To find index of element e with certain value:
- Start with an array sorted in descending order.
- In each step:
- Pick the middle element of the array (m) and compare it to e.
- If element values are equal, then return index of m.
- If e is greater than me, then e must be in left subarray. If m is greater than e, e must be in the right subarray.
- Repeat those steps on new subarray.
- In each step:
Performance varies depending on sequence characteristics (distribution)
Much data is actually connected node and vertices, which makes it much harder to find algorithms that compute solutions quickly.
A lot of research goes into solving graph problems.
One of them most common ways to navigate a graph, is by using a thing called a Depth First Search (DFS).
- DFS progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children.
- Then the search backtracks, returning to the most recent node it hasn’t finished exploring.
Other solutions for this kind of thing include:
The Travelling Salesman Problem
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
This is considered an NP-Hard problem (Non-deterministic Polynomial-time hard), meaning that all solutions are exponential.
Geometry: Detecting Collision
Don't detect the box around it, detect the actual content.
Primality Tests
Watch this and read this.
k Means Clustering
Read this and read this (better).
Decision Trees
Compression: Run Length Encoding
Image Processing: Edge Detection