Aditya Bhargava
Note, you can find all my solutions to tasks.
Algorithms — is a set of instructions to accomplish the task.
Algorithm which works with sorted data. Binary search is using following technique:
For example, let's assume we have numbers from 1 to 100 and we need to find 67. Instead of using simple search and checking all possible variants, Binary search offers us to take the middle element (50 in our case) and compare with our value. If it's lower or higher, in both cases we can skip the half of the array. I guess you got the point.
You may not remember what logarithms are, but you probably know what exponentials are. log10 100 is like asking, “How many 10s do we multiply together to get 100?” The answer is 2: 10 × 10. So log10 100 = 2. Logs are the flip of exponentials.
In this book, when I talk about running time in Big O notation (explained a little later), log always means log2. When you search for an element using simple search, in the worst case you might have to look at every single element. So for a list of 8 numbers, you’d have to check 8 numbers at most. For binary search, you have to check log n elements in the worst case. For a list of 8 elements, log 8 == 3, because 23 == 8. So for a list of 8 numbers, you would have to check 3 numbers at most. For a list of 1,024 elements, log 1,024 = 10, because 210 == 1,024. So for a list of 1,024 numbers, you’d have to check 10 numbers at most.
Note, if the maximum size of the guesses equals to list's size then it's a linear time. The Binary search runs in logarithmic time.
Big O notation tells you how fast an algorithm is. For example, suppose you have a list of size n. Simple search needs to check each element, so it will take n operations. The run time in Big O notation is O(n). Where are the seconds? There are none—Big O doesn’t tell you the speed in seconds. Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows.
Big O notation is about the worst-case scenario. So you can say that, in the worst case, you’ll have to look at every entry in the phone book once. That’s O(n) time. It’s a reassurance—you know that simple search will never be slower than O(n) time.
Binary Search Tree is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
BST has O(log n) time for lookup, insert and removal.
It's a data structure which keeps all it's items nexy to each other in the memory.
Array's have a disadvantage: in case if we want to add new item and its place is filled with another item, you need to move your array to a new place
With linked lists, your items can be anywhere in memory. Each item stores the address of the next item in the list. A bunch of random memory addresses are linked together.
Let’s say you’re trying to find 10,000 slots for an array. Your memory has 10,000 slots, but it doesn’t have 10,000 slots together. You can’t get space for your array! A linked list is like saying, “Let’s split up and watch the movie.” If there’s space in memory, you have space for your linked list.
Linked lists have a similar problem. Suppose you want to read the last item in a linked list. You can’t just read it, because you don’t know what address it’s at. Instead, you have to go to item #1.
Arrays are great if you want to read random elements, because you can look up any element in your array instantly. With a linked list, the elements aren’t next to each other, so you can’t instantly calculate the position of the fifth element in memory—you have to go to the first element to get the address to the second element, then go to the second element to get the address of the third element, and so on until you get to the fifth element.
| Process | Arrays | Lists |
|---|---|---|
| Insert | O(n) | O(1) |
| Read | O(1) | O(n) |
| Delete | O(n) | O(1) |
It’s worth mentioning that insertions and deletions are O(1) time only if you can instantly access the element to be deleted. It’s a common practice to keep track of the first and last items in a linked list, so it would take only O(1) time to delete those. Which are used more: arrays or lists? Obviously, it depends on the use case. But arrays see a lot of use because they allow random access. There are two different types of access: random access and sequential access. Sequential access means reading the elements one by one, starting at the first element. Linked lists can only do sequential access. If you want to read the 10th element of a linked list, you have to read the first 9 elements and follow the links to the 10th element. Random access means you can jump directly to the 10th element. You’ll frequently hear me say that arrays are faster at reads. This is because they provide random access. A lot of use cases require random access, so arrays are used a lot.
- Tail Recursion
D&C algorithms are recursive algorithms. To solve a problem using D&C, there are two steps:
- Figure out the base case. This should be the simplest possible case.
- Divide or decrease your problem until it becomes the base case.
“If you find the biggest box that will work for this size, that will be the biggest box that will work for the entire farm.” If it’s not obvious to you why this statement is true, don’t worry. It isn’t obvious. Unfortunately, the proof for why it works is a little too long to include in this book, so you’ll just have to believe me that it works. If you want to understand the proof, look up Euclid’s algorithm. The Khan academy has a good explanation here: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm.
You just got a sneak peak into inductive proofs! Inductive proofs are one way to prove that your algorithm works. Each inductive proof has two steps: the base case and the inductive case. Sound familiar? For example, suppose I want to prove that I can climb to the top of a ladder. In the inductive case, if my legs are on a rung, I can put my legs on the next rung. So if I’m on rung 2, I can climb to rung 3. That’s the inductive case. For the base case, I’ll say that my legs are on rung 1. Therefore, I can climb the entire ladder, going up one rung at a time.
You use similar reasoning for quicksort. In the base case, I showed that the algorithm works for the base case: arrays of size 0 and 1. In the inductive case, I showed that if quicksort works for an array of size 1, it will work for an array of size 2. And if it works for arrays of size 2, it will work for arrays of size 3, and so on. Then I can say that quicksort will work for all arrays of any size. I won’t go deeper into inductive proofs here, but they’re fun and go hand-in-hand with D&C.
A hash function is a function that maps strings (actually any kind of bytes) to numbers. There're skme requirements for those functions:
- They should be determenistic (means they calling same argument should always return the same output))
- They should return different numbers for different arguments (in best case)
Put an array and hash function together and you'll get hash table
In reality it's impossible to write hash function that to all different args will give different outpot.
The collision is when the same key assigned to different arguments.
To avoid collisions we need: — Low load factor
- Good hash function
Load factor = numbers of items in hash table / length of hash table
Having a load factor greater than 1 means you have more items than slots in your array. Once the load factor starts to grow, you need to add more slots to your hash table. This is called resizing. First you create a new array that’s bigger. The rule of thumb is to make an array that is twice the size.
As a recap, these are the two questions that breadth-first search can answer for you: • Question type 1: Is there a path from node A to node B? (Is there a mango seller in your network?) • Question type 2: What is the shortest path from node A to node B? (Who is the closest mango seller?)
- Find info on khan academy
- The queue is called a FIFO data structure: First In, First Out.
- In contrast, a stack is a LIFO data structure: Last In, First Out.
You used breadth-first search in the last chapter. Breadth-first search will find you the path with the fewest segments. What if you want the fastest path instead? You can do that fastest with a different algorithm called Dijkstra’s algorithm.
When you work with Dijkstra’s algorithm, each edge in the graph has a number associated with it. These are called weights.
To calculate the shortest path in an unweighted graph, use breadth-first search. To calculate the shortest path in a weighted graph, use Dijkstra’s algorithm.
Dijkstra’s algorithm only works with directed acyclic graphs, called DAGs for short.
A greedy algorithm is simple: at each step, pick the optimal move. In this case, each time you pick a class, you pick the class that ends the soonest. In technical terms: at each step you pick the locally optimal solution, and in the end you’re left with the globally optimal solution.
Clearly, the greedy strategy doesn’t give you the optimal solution here. But it gets you pretty close. In the next chapter, I’ll explain how to calculate the correct solution. But if you’re a thief in a shopping center, you don’t care about perfect. “Pretty good” is good enough. Here’s the takeaway from this second example: sometimes, perfect is the enemy of good. Sometimes all you need is an algorithm that solves the problem pretty well. And that’s where greedy algorithms shine, because they’re simple to write and usually get pretty close.
This is called an approximation algorithm. When calculating the exact solution will take too much time, an approximation algorithm will work. Approximation algorithms are judged by • How fast they are • How close they are to the optimal solution
The traveling-salesperson problem and the set-covering problem both have something in common: you calculate every possible solution and pick the smallest/shortest one. Both of these problems are NP-complete.
Here’s the short explanation of NP-completeness: some problems are famously hard to solve. The traveling salesperson and the set-covering problem are two examples. A lot of smart people think that it’s not possible to write an algorithm that will solve these problems quickly.
NP-complete problems show up everywhere! It’s nice to know if the problem you’re trying to solve is NP-complete. At that point, you can stop trying to solve it perfectly, and solve it using an approximation algorithm instead. But it’s hard to tell if a problem you’re working on is NP-complete. Usually there’s a very small difference between a problem that’s easy to solve and an NP-complete problem. For example, in the previous chapters, I talked a lot about shortest paths. You know how to calculate the shortest way to get from point A to point B.
- Recursive solution
- Optimize repetitive calculations
- Bottom-up method
KNN is used for classification and regression and involves looking at the k-nearest neighbors. • Classification = categorization into a group. • Regression = predicting a response (like a number).
- Binary Search Tree
- B-trees
- Red-black trees
- Heaps
- Splay Trees
- Inverted indexes
- The Fourier Transform
- MapReduce
- Bloom Filters
- Hyperloglog
- Hash Functions
- SHA
- SHA is actually a family of algorithms: SHA-0, SHA-1, SHA-2, and SHA-3. As of this writing, SHA-0 and SHA-1 have some weaknesses. If you’re using an SHA algorithm for password hashing, use SHA-2 or SHA-3. The gold standard for password-hashing functions is currently bcrypt (though nothing is foolproof).
- Simhash
- If you make a small change to a string, Simhash generates a hash that’s only a little different. This allows you to compare hashes and see how similar two strings are, which is pretty useful!
- SHA
- Diffie-Helman
- RSA
- Linear Programming
- Simplex Algorithm