I have read Skienas book, both the second and third edition. Love the idea. There is an errata nearly every other page for the second edition. Third edition appears better...for now. Someone needs to get this man a proper editor!
Algorithmic thinking is a fun read. I will recommend it.
Skiena is also a fun read. I quite enjoyed the anecdotes (real life case studies) in Skiena’s book.
Yes, of course, but that's a silly attitude. Isn't anything better than nothing? Therefore isn't it better to skim one good book then to read nothing? I see why someone would ask for recommendation for a single book.
You described the books as containing “knowledge we don't gravely need in the first place”. If that’s the case, and if you’re reading for knowledge, why bother reading either one? If you already know you don’t need the knowledge those books contain, move on to other books.
And if you’re just reading for fun, that’s fine, but then why does the amount of knowledge the book contains even enter into it? Why even bring it up in your comment, especially in a way which comes across as snarky?
And fwiw, if I’m reading snark into your comment where no snark was intended, my apologies.
No snark intended. If you're software engineer with tight schedule due to young kids or ill family member or whatever, but you still want to slowly move the needle when it comes to career and your own knowledge then you don't "gravely" need the algo book, but you would benefit from reading one, it's just a question of what will give you the best ROI (ROI here being both financial but also personal satisfaction etc).
English is my second language so my thoughts often come across differently than intended - thank you for replying instead of just down voting
But books absolutely are about getting knowledge through. I can guarantee you that you won't have fun with a lot of hard books a lot of times but you will still do it for what you get out of it if you understand the benefits for life or career or something else. I never thought I would read dozens of tomes on health, family and children topics, or pmbok for PMP etc. But I still did because it mattered. Same with GEB, it got tiring and hard after a while but I knew finishing it would be worth it so I did it even though I wasn't having fun at one point!
Of course! My comment was more of reminiscing for the time I was able to read multiple books on same subject before having a kid rather than just a lazy sob. Now I appreciate when someone compares the books so I can pick one, ie. GP mentioned anecdotes, I like them so I would start with that book, it would motivate me to start as well.
So what exactly does happen when you admit you don't know a thing? And what's worse: admitting you don't know a thing or showcasing you don't know a thing by presuming the wrong thing? Intriguing stuff.
One interesting part of this book is the language chosen is C. Now, we all know the downsides but the good part is it allows the student to understand the runtime efficiency, memory usage and complexity of various algorithms closer to what you can expect in the ideal case. I see a lot of books nowadays using Python, it is not clear with such a high level language you understand the tradeoffs. How much of the slowness is due to the algorithms vs the data structures you chose from Python.
Of course, no GC, segfaults and OOM are some of the downsides of C but this is not production code. You can use this knowledge to understand how various algorithms are implemented in other languages and predict behavior or chose a better one.
When we teach students we have to balance employability, pedagogical utility, interest, and learning curve.
The majority of students won’t need to know C to be employable. Teaching an Algos course in JS helps web dev. In Python helps data science. Java is still pretty popular for enterprise.
The majority of students will find it quite difficult compared to most languages they use.
C does not reflect a truly low level machine. You might be able to teach them the same thing with an assembly language.
The kids who want to know C will teach themselves. And they will be taught some in operating systems.
I think it's best to teach in a high-level, multi-paradigm language that isn't one of the popular languages. It resets the playing field, provides a nice language to have in their tool belt, and still allows easy transition to other languages.
I don't know C for what it's worth, but learned a different low-level language and found the experience to be enlightening, even after programming most of my life.
C is a much more appropriate choice in my opinion. It expresses 99.9% of the same concepts while being orders of magnitude faster to read. Most people I know who have tried to read (some of) Knuth cited MMIX among their reasons for eventually growing tired and abandoning the effort.
> It expresses 99.9% of the same concepts while being orders of magnitude faster to read.
Knuth thinks so, or did at some point.
"I think C has a lot of features that are very important. The way C handles pointers, for example, was a brilliant innovation; it solved a lot of problems that we had before in data structuring and made the programs look good afterwards. C isn't the perfect language, no language is, but I think it has a lot of virtues, and you can avoid the parts you don't like. I do like C as a language, especially because it blends in with the operating system (if you're using UNIX, for example).
All through my life, I've always used the programming language that blended best with the debugging system and operating system that I'm using. If I had a better debugger for language X, and if X went well with the operating system, I would be using that."
Dec 7, 1993, Computer Literacy Bookshops Interview.
What he's talking about is pointer arithmetic. In assembly you have to "know" what is being pointed at such that you can access an element in an array or a component of a composite type, for example. The computer only knows about bytes. In C you can just do stuff like `(p + 6)->t` and the compiler knows how many bytes "+6" is because it knows what `p` is pointing at.
> Also, the combined dereferencing and member lookup operator (->).
That's actually a dud. The motivation was likely caused by the silly choice of the dereference operator being unary/prefix, requiring parentheses in (*ptr).memb.
Compare with Pascal's ptr^.member where no parentheses are required.
But ptr.memb can just work as well as value.memb. The operator statically knows whether the left operand is a pointer to a struct/union or a struct/union value.
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.
I'd amend the definition of a graph to be something like, a graph is a set of nodes and a set of their relationships called edges. A tree is a special case of a graph where every node has exactly one relationship with its parent. Essentially, now that we know about N-aray trees where any node can have N many children, what about a datastructure where any node can have N many parents?
This avoids confusion with some non-optimal representations, like a list of trees and a list of edges between those trees. While that's useful for some algorithms (for example, what's called a least-single-common-ancestor (LSCA) tree and auxiliary list of edges, which can be used for efficiently finding the least common ancestor of two or more nodes), it's really bad for most.
The logical build up from linked lists to trees to graphs is useful for practical applications.
It's also useful to know that this is an abstraction and you can store everything in faster data structures like hashmaps and arrays to efficiently lookup tree or graph relationships.
I intentionally omitted direction from the description to avoid pedantry, because the problem I was highlighting was that "interconnected trees" is very wrong.
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.
Mathematics 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...
Finally the most easiest answer of all. Just don't use for loops to do anything. Begin by imagining your programming language doesn't have a for loop. Now write code. This is how you write recursive code.
