5 ms·
Honestly speaking most of these books just show/illustrate how an existing algorithm works, not how to make an algorithm. I don't have a CS education but what
by kamaal 3y ago
Honestly speaking most of these books just show/illustrate how an existing algorithm works, not how to make an algorithm.
I don't have a CS education but what I learned about algorithm thinking is this.
1. Trees- Use this if the solution to your problem involves searching a large search space. Trees comes in two types. Binary(Every node has only two child nodes) and K-ary(a node has many children). Building a tree involves putting data in the tree based on some logic(e.g- right node is less than the parent node, and left is greater than the parent node). Using this sort of logic every time one decides to left/right, they are deciding not to traverse an entire sub-tree. Decreasing search space. These trees can be used to represent physical space. Like say representing a district/county and its sub-areas as subtrees. Or words- Like imagine the words 'application' and 'apple' have first 4 common letters. So you can put this in a tree and decide to left/right to check if a word exists in a tree(this is helpful in building spell checkers). Another example is a file system. Basically think of a tree anytime you have to a) Reduce search space. b) Makes less decisions. In fact tree is a way of making expensive computations in advance and putting them in a way accessing them is easy. There are efficient ways of traversing trees. Inorder, Preorder, Postorder traversals. Once you know these its easy as there are just 3 ways. Use these if your solution demands going 'breadth first' or 'depth first'.
2. Graphs- These are interconnected trees. Many use cases in everyday life involve Graphs. Roads, Weblinks, Family trees, Organisation hierarchies. These structures are used to represent data of similar nature. There are many common problems that have solutions that can use this.
3. Linked Lists- These are just plain lists. For eg- your file is represented as a LL. Things like a Twitter stream, or a shopping cart. Hence simple searching, sorting operations are done here.
Notice how these things are just lists or lists of lists. There are also many such structures which can help with efficient representation of data. Eg- A stack- Solutions where last come, first serve methods are needed. Queues- Solutions where first come, first serve methods are needed. Sets are another useful structure. They are helpful when finding, common elements and grouping needs between two groups. Another useful structure is a HashMap which allows fast look up. etc.
Algorithms-
1. Dynamic programming- If you are doing repeated computations often, you are better of doing it one, and looking up the result, instead of doing it over and over again.
2. Recursion- Solution builds from a base case, and can extended by using recently/already computed values.
3. Bit Shifting- Its often a mistake to assume that common methods used for simple operations like addition, and multiplication are the fastest. There are other methods and these can save time.
4. Searching, and Sorting- Since most common use cases involved pre computing the data and accessing it, you need efficient means of storing them. Hence these algorithms come handy. There are only a handful of them, and once learned can be used to solve those category of problems.
5. Backtracking- Since the computer is not an oracle, and the only way of looking in the future we have is a for loop, some times we have to look ahead to realise it was a wrong move, take a step back and walk into a different branch of a tree. So chess, checkers, route planning etc are efficiently solved with these approaches.
- kamaal 3y agoHow to think about Big-O Big-O has nothing to do with running things fast. Although its a welcome and a nice side effect. Big-O optimisation is basically a way of finding means to reduce effort required to do anything. It just happens when you take fewer steps to do a thing, you also in most cases make it run faster. Though making it run faster was never the goal. Hence you must stop thinking it terms of making a program run faster. This causes confusion given you are not thinking about the problem from first principles. For example writing a vim macro is going from many steps to one command. Hence writing a vim macro is a O(1) operations. There are many such everyday things where you are doing N steps, which can be automated to doing it in 1 step. In programming parlance there is only one way big work is done. Its either done with a for loop, or nested for loops. That is for(i=0;i<SomethingBig;i++){//do something with at speed of tick of i} or for(i=0;i<SomethingBig;i++){for(j=0;j<SomethingBig1;j++){//do all of tick of j repeatedly, at the tick of i}} Of course we can have as many sub loops, which in case the count of operations are ij... Now here is how you think about making it efficient. Notice the i++ part of the for loop conditions to take the for loop forward? Most peoples minds are hard trained to think only in terms of i++, and nothing else. Hence it looks very hard to think anything else could work there. i++ moves the loop forward one element forward at a time. If you have a huge 'SomethingBig' it can take an eternity to get there. How else can we make the counter run fast. Increase i++ to i+2 for eg, is one way. But there are other ways like multiplication for eg i * 2, would mean you are going way faster now, and saving computations. Basically finding how to do that is algorithmic optimisation. Notice as mentioned above using a tree achieves many such tasks.
- ykonstant 3y agoExpanding your code: for(i=0; i < SomethingBig; i++) { //do something with at speed of tick of i } or for(i=0; i < SomethingBig; i++) { for(j=0; j < SomethingBig1; j++) { //do all of tick of j repeatedly, at the tick of i} } Generally, prepend 2 or 4 spaces in line codes for proper formatting. Also, * is used to start emphasis, so you need to escape it with a backslash.
- hnfong 3y agoMathematics had concepts of convergence/bounds of infinite sequences since antiquity. Big-O is just mathematical notation that you can use for whatever you want. Big-O is useful because most of the time we want to reduce time complexity for algorithms when inputs get large, where constant and lesser terms usually become insignificant. Some people measure steps, but we call it "time complexity" because they're essentially the same thing assuming that time taken for each step does not depend on `n`. There are occasionally philosophical implications when you prove a complexity bound, so in those cases making stuff run faster isn't the goal, but unless you're deep into theoretical computer science, usually making code faster is your goal when you have to deal with time complexity. FWIW, for loops isn't actually a primitive of CS or even programming. Of course you can achieve Turing completeness with C-style for loops, but that tweaking for loops isn't usually how people think about reducing time complexity...