Timeline for Computer science for mathematicians
Current License: CC BY-SA 2.5
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 25, 2022 at 20:05 | comment | added | Dmitri Pavlov | @Z.M: Concerning Fibonacci heaps, the book does not explain the reasoning behind its claim, nor how to identify “most applications”. For me, “learning” means understanding why this is the case and being able to make such judgments for other data structures, not just communicating some vaguely stated claims without any evidence, like CLRS do. | |
| Dec 25, 2022 at 18:52 | comment | added | Z. M | @DmitriPavlov Thanks. Now it is clearer (it was clear, but I was distracted by comments about "caching", which led me to think that you are talking about technicalities) and fair enough. But this comment "you wouldn't learn from CLRS that Fibanacci heaps are unsuitable for real programming" seems to be incorrect. In the second edition, introduction to Fibonacci heaps, it reads that "From a practical point of view, however, the constant factors and programming complexity ... less desirable than ordinary binary (or k-ary) heaps for most applications." | |
| Dec 25, 2022 at 17:46 | comment | added | Dmitri Pavlov | @Z.M: You are talking about entirely different set of issues (vectorization, pointers), none of which are discussed above. What is discussed above is whether CLRS give reasonable advice on implementing linked lists, trees, etc. I posit they do not, since a typical software engineer reading their book would be led to think that it's okay to dynamically allocate individual elements of the list, when in reality the resulting program will be orders of magnitude slower than the one that packs the list into an array. This has nothing to do with vectorization. | |
| Dec 25, 2022 at 12:51 | comment | added | Z. M | @DmitriPavlov This is machine/platform dependent, and I am afraid that the efficiency difference between arrays and pointers is no longer significant or even existent. Look at this answer on StackOverflow. The modern compilers today are very different from decades ago. Years ago, I wrote some codes in C and Rust to test, and the Rust code ran faster than C, both compiled with best optimizations. I looked at the assembly code and I did not understand, but very different from 8086 that I learnt, e.g. en.wikipedia.org/wiki/Automatic_vectorization | |
| Dec 24, 2022 at 19:35 | comment | added | Dmitri Pavlov | @Z.M: For example, the fast sorting algorithms in CLRS have running time O(n log n), and CLRS explain a bunch of them. In practical implementations, the running time is dominated by memory access. Using asymptotics alone, we cannot say which algorithm is better. Variants of quicksort have the smallest constant, and exploit the benefits of caching by using mostly sequential memory access. Of course, in the case of sorting algorithms these facts are well known, but this applies equally well to other situations, where such an analysis need not exist. | |
| Dec 24, 2022 at 19:17 | comment | added | Dmitri Pavlov | @Z.M: There are plenty of algorithms out there (in many areas, the majority) whose running time is dominated by memory access (i.e., moving things between RAM and registers). For such applications, constants most certainly do matter, and it is important to understand how memory access works and how to make it more efficient. This can easily result in a speedup factor of 10 or more, and cannot be ignored. | |
| Dec 24, 2022 at 19:14 | comment | added | Dmitri Pavlov | @Z.M: Looking at my comments, I should have specified that I meant “learn to use efficiently”. While CLRS do discuss how to pack lists and trees into arrays from a theoretical point of view, they precede the whole discussion with the sentence “How do we implement pointers and objects in languages, such as Fortran, that do not provide them?”, which does create an impression of the irrelevance of material for pretty much any other programming language. And the fact that one also has to use such ideas in languages that offer dynamic memory management is not mentioned at all. | |
| Dec 24, 2022 at 18:56 | comment | added | Z. M | @CarlOffner I wonder whether "analysis of algorithms" (in Knuth's way) is useful in practice? I mean, the techniques to seek asymptotic expansions of running time instead of a coarse asymptotic equivalence? I guess that, in industry, one simply profiles different algorithms with the "same" time complexity — the current architecture is much more complicated than MMIX (e.g. there are out-of-order executions). | |
| Dec 24, 2022 at 18:37 | comment | added | Z. M | @DmitriPavlov I am probably late. I remember that I learned linked lists from CLRS when I was a high school student (more than 15 years ago) without "very high level of programming culture". I believe that I looked at the second edition, and now I glimpse it on Google Books, and I would not agree with your judgment. For example, §10.3 is covering the necessary materials on memory management. | |
| Jan 15, 2011 at 4:56 | comment | added | Dmitri Pavlov | @Igor: It might be the case that the phrase “the students appeared to have learned a lot” characterizes the situation much more accurately than you would like it to be. I really don't see any point in understanding how linked lists work if you cannot implement one yourself efficiently. For me it's much easier and faster to implement an algorithm myself than try to look it up in some library. Also, the implementations of standard algorithms such as linked lists or hash tables in languages like C++, Java, Python, or OCaml are simply way too slow. | |
| Jan 9, 2011 at 4:01 | comment | added | Igor Rivin | @Dmitri and @Carl, continued. This, to me, seems to indicate an inefficiency in your work. C++ or Java or python, or OCaml, well, any currently used programming language (except possibly Fortran) implement a Map type (C has many hash table libraries available). Is it implemented as hash tables? B-trees? Do I really care? Do I REALLY want to implement an optimized quicksort myself? Yes, I have done such things, but I have no interest in doing them again. Should you knoww how these things work? Sure, but plowing through $\aleph_0$ pages of Knuth seems to be not very efficient... | |
| Jan 9, 2011 at 3:56 | comment | added | Igor Rivin | @Dmitri and @Carl: I have nothing but respect for Knuth and his books. But as mathematics books, not practical computing books. Just look at the exercises -- they are all math problems. Calling the books "The Art of Computer Programming" was great marketing, but not exactly truth in advertising. CLRS is far from perfect, but I have (very successfully, in the sense that the students appeared to have learned a lot) taught algorithms from that book. As for my comment on subroutine libraries. Dmitri said he used algorithms from Knuth "hundreds of times". | |
| Jan 7, 2011 at 0:22 | comment | added | Dmitri Pavlov | @Igor: CLRS is meant for theorists, not programmers. For example, to learn linked lists from CLRS one needs to possess a very high level of programming culture. And a programmer with such a high level of programming culture almost certainly already knows linked lists. Knuth's books are much better in this respect, because they actually explain how to implement linked lists. And you wouldn't learn from CLRS that Fibanacci heaps are unsuitable for real programming, even though they have better asymptotics. No offense meant, but to claim that CLRS is "vastly superior" is simply ridiculous. | |
| Jan 7, 2011 at 0:14 | comment | added | Dmitri Pavlov | @Igor: Knuth's books were updated in 1997. Volume 4A will be published this year. Knuth will update the first three volumes again when Volume 5 is finished. Thus one cannot say that his books are old. Your 5% estimate is very far from the truth. My estimate is that at most 1/3 of the book is devoted to matters that are currently irrelevant for programming. As for (b), it simply does not make any sense. What are you trying to say with it? Should we study proofs of known theorems, provided that these proofs are already written down somewhere? | |
| Jan 6, 2011 at 22:28 | comment | added | Carl Offner | @Igor: Well, that's a different matter. I was responding to your statement that Knuth's work had "very little to do with computing". Just on the face of it, that's not true at all. I in fact teach an analysis of algorithms class. I use Cormen et al. And I also point out to my class that the very phrase "analysis of algorithms" was coined by Knuth in his preface to Volume 1. His work is fascinating, both for the wealth of information it contains, and also for the historical insights of someone who was "there at the time." | |
| Jan 6, 2011 at 2:50 | comment | added | Igor Rivin | @Carl: first, does not mean best. Corman Leiserson Rivest, though imperfect, is vastly superior for learning that sort of stuff from. | |
| Jan 6, 2011 at 2:50 | comment | added | Igor Rivin | @Dmitry Pavlov: The algorithms described in Knuth take up MAYBE 5% of the volume, and the rest consists of related parts of mathematics, used to get exact asymptotics (not very useful in applications, since the actual running time is heavily hardware dependent), to third order (REALLY useless in applications, though mathematically quite cool. Plus (a) the books are very old, and much better (and different kinds of) algorithms now exist and (b) subroutine libraries in all known programming languages implement optimized versions of the most modern algorithms. So, I am not sure what you mean. | |
| Jan 6, 2011 at 2:03 | comment | added | Carl Offner | @Igor: Well, Knuth is where I learned about trees and stacks. Both of which I've used -- a lot -- in programming. Sure, since then other books have come along. But Knuth is where a lot of that sort of stuff was first coherently organized. (The MIX business, though, I think is pretty forgettable and ignorable.) | |
| Jan 5, 2011 at 20:43 | comment | added | Dmitri Pavlov | @Igor: I also don't understand you remark about MIX. MIX (and its successor MMIX) are used only a few times in the entire series of books to illustrate some concepts that cannot be illustrated easily in high-level language (like implementing coroutines, for example). The absolute majority of algorithms in Knuth's book is written in English, not in MIX or MMIX. | |
| Jan 5, 2011 at 20:41 | comment | added | Dmitri Pavlov | @Igor: Theoretical Computer Science might as well be thought of as a part of mathematics. I don't find Knuth's books particularly useful for my mathematical work, but I used algorithms from Knuth's books literally hundreds of times in my programs. | |
| Jan 5, 2011 at 19:38 | comment | added | Igor Rivin | @drbobmeister: I have them on my shelf, and they have been quite helpful for questions for polynomials over $\mathbb{F}(p),$ and the like, but NEVER, EVER for anything to do with programming. @Mitch Harris: what? you don't program MIX daily???? | |
| Jan 5, 2011 at 19:15 | comment | added | Mitch | @Igor - I was about to say the same thing, but it certainly is a text about mathematics that is inspired by thinking about writing programs...well, those programs that Don Knuth was thinking about in 1960. | |
| Jan 5, 2011 at 19:08 | comment | added | drbobmeister | Knuth's books are on the shelf of almost every serious programmer I have ever met. | |
| Jan 5, 2011 at 18:28 | comment | added | Igor Rivin | You are? That's a mathematics book, having very little to do with computing, in my opinion. | |
| Jan 5, 2011 at 18:11 | history | answered | John D. Cook | CC BY-SA 2.5 |