Computer Science is exactly what the OP talks about: computers, CPUs, implementation details, hardware, plumbing, etc... One needs actual hardware on the table to work this out. Imperfect hardware, with latencies, clock issues, etc... THAT is true computer science, IMHO, and is very near Electrical Engineering.
On the other hand, Algorithmic Science really is an applied form of mathematics. One does not actually _need_ a computer to design, understand, invent algorithms. A brain, paper and pen are enough.
Those are two different sciences, and I suspect very few people are actually great (world class) in both simultaneously. It is futile to imagine that a single school curriculum would adequately form people in those two very different topics.
I could add that where I work, we have in-house the two kinds of people: a couple of mathematicians for the (amazing algorithms) and a few very picky low-level programmers who actually implement the algorithms with blazing fast, hand-crafted code. The two groups would never dream of doing the other's job.
It really depends on what sources you base your concepts on. I would say that, for instance, what you mention is more closely related to "computer engineering" than "computer science".
For instance, in [0]: "Thus CS is closer to the underlying theory of computation, with its roots in mathematics, and CEN is closer to the design of physical devices (...) Of the three great divisions in computing, namely theory, software and hardware, to a first approximation theory goes with CS, hardware with CEN, and software with both (...)"
In my country, our technical schools and most universities provide what we call "informatics engineering" (engenharia informática), which has a bit of CS (in terms of basic concepts, algorithms, abstract data types, etc.), CE (some low level electronic stuff) and Software Engineering (Programming, OOP, Web Programming, Logic/functional programming, etc.).
[0] http://www.eng.buffalo.edu/undergrad/academics/degrees/cs-vs...
If computers still only had 512bytes of memory we'd be writing programs different then today making a trade off of computation speed for ram size.
If CPUs didn't have pipelines then parallelized algorithms wouldn't be as important and I feel that mutli-CPU machines would have taken off to make room for other forms of parallelization.
As the GP says, Galileo's telescope didn't make the universe smaller or larger, it just let him see things in that universe. Nothing changed but what he was holding.
This is typically called Computer Engineering in curricula.
Computer Science is all about the "Science" of Computing, hence its focus on algorithms, computability, etc.
What's missing is actually Programming. "Software Engineering" tends to focus on project management; "Computer Science" is about modeling computing and not programming; "Computer Engineering" is about how the hardware works, not how to use it...
Programming well still tends to be tribal knowledge, apprenticeship, and craft.
> I doubt these people know the inner workings of computers
...wha...? This is so ridiculous of a claim that I can't even think of how to respond...
This is my impression from my interactions with some of them.
I've explained here: https://news.ycombinator.com/item?id=13252108
> ...wha...? This is so ridiculous of a claim that I can't even think of how to respond...
GP probably means that while these pioneers might be aware of, might have tinkered with the nuances of processor design and syscalls and nitty-gritty details of TLB's and interrupts and stuff that, say, a kernel-level or SSD firmware guy might deal with regularly, it's highly unlikely that they would know their way around these like they know their way around the algorithms that they deal with on a regular basis, which exist at a much higher level of abstraction.
Take everything with a grain of salt.
I think you missed my point. What I'm saying is there's a world of difference between "X knows B better than A" and "X doesn't know A [very well]". When you're talking about world-class experts who are at the forefront of research in their fields, if you work in the same discipline, there's a pretty damn good chance they're more of an expert at your work area than you are. (I'm obviously assuming "you" here are not the world-class expert in your area. "You" are just a generic but respectable engineer in your area of work.)
I think what you (& the OP) need to realize is that there's a HUGE and crucial difference between being, say, "rusty" on something (e.g. because you're not doing it on a day-to-day basis, or because it's someone else's system and obviously you can't magically know how it was designed a priori), and not having enough prior expertise such that your ramp-up time would be low enough to be negligible, should you ever need to touch that thing at some point. You need to realize, these folks have done so much work that they even get rusty on their own research topics after a few years. That doesn't mean they stop being experts on their topics. On top of that, they still keep up with their colleagues' research in other related areas... which, mind you, are likely to be more advanced than what you're doing. Chances are if they spent a day or two reviewing other stuff, they'd be as good (or even better) experts on them than they were originally, quite likely better than you (again, generic "you" here, as above).
I'm a researcher and particularly I'm an undergrad assistant to people who do important things. EWD was an expert. I know a little about computer science and am still learning. EWD knew everything there was to know at that time and was teaching.
That's what an expert is. The pinical of the field's knowladge accumulated into one person. You don't earn the title Expert from a degree. You don't earn it by any means from years of experiance. You earn the title Expert by consistantly blowing the minds of everyone else in your field and by consistantly pushing your field forward further then your peers.
Nice strawman. Where did I ever generically talk about "researchers"? Are these people mentioned (Karp, Valiant, etc.) just merely "researchers" to you? You really think I have the same regard for (say) a random grad student as I do for someone like Karp? And you really think I don't have the same respect for the best people working on corporate/commercial technology (Musk, Page, etc. just as a couple of examples off the top of my head)? It seems like you really have low opinions of all researchers no matter how accomplished they are, in which case that would explain everything, but I certainly don't. Otherwise it's like you're actively trying to waste my time and miss my point...
I don't have a low opinion of researchers.
A simple example is dijkstra's algorithm vs bellman ford. Sure, in the abstract sense, the greed algorithm wins. However, it would be wrong to assume that dijkstra's algorithm is faster than bellman ford, because it's not. That's because dijkastra's algorithm doesn't parallelize as well, where as bellman ford parallelizes very well (and by "well" I mean it exploits the architecture - in a sense has "mechanical sympathy"). You end up creating very exotic data structures that are good for caching and stealing work from unused threads. There are many other examples, check out matrix matrix multiplication if your interested.
I'm not making the argument that one is more important than the other, but I think it's a bit reductive to say algorithm only matter because there are so many examples of where computer architecture matters more (and vice versa).
Another way to say what I mean is that ultimately reality matters.
> The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.? I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute.
Um, why would you think that they don't understand the inner workings of computers? Is that just your intuition or is that based on some practical knowledge? I'm not saying I know the answer (I haven't quizzed them), but since we're guessing here I'm going to say that they probably know a lot about the inner workings of computer - and there's no harm in us mortals trying to do the same. They probably don't know like specific things about how intel's branch prediction works or anything like that, but as a general concept, the inner workings of computers is pretty fundamental stuff and is very helpful to know, along with algorithms.
>Um, why would you think that they don't understand the inner workings of computers?
Yes, great point. I know of at least one person who seems to straddle both those worlds - Jon Bentley:
https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientis...
He wrote Programming Pearls, More Programming Pearls, and Writing Efficient Programs. I own copies of either two or all three of those, and have read good amounts of the first two, and pretty close to the whole of the third (some years ago), which is out of print. A fantastic book (the first two are too).
And the point here is that in the Efficient programs book, he goes into a lot of detail on performance improvement at the lower levels too, not just at the level of algorithms, though he covers that some too. And he has also invented algorithms (e.g. the Bentley–Ottmann algorithm). So he is an example that one can do/be both high-level and low-level.
And of course, many more people do that, at a lower level of accomplishment (but still non-trivial), such as working with low-level languages (C, assembly) and doing perf tuning, as well as creating or improving algorithms and data structures for their work, high-level software design/architecture, etc.
This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students.
From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class.
I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good thing.
> While true, all things held equal a new algorithm will advance the field, providing "gains" as you said
> but it's false to assume that algorithms are more important than understand computer architecture, full stop
I wish there were two like buttons. I have nothing to add that you haven't said better then I could have.
This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students.
From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class.
I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good idea.
... amidst cries from a handful of lunatics who insist we shouldn't be using linked lists any more because they don't use the L1 cache very well compared to arrays.
In the same sense if you're in a python shop doing web development and you say "EVERYONE we need to STOP using python and write ALL of our HTTP code in C! We'll be able to optimize the hell out of it and probably save 10K of memory per request! That's HUGE!" you would also in tern be shitcanned before you finished the sentence.
If you take that same exact mentality and bring it to a company that builds realtime systems that do DSP and maybe even handle some user interaction in an embeded form facter and you say "EVERYONE! I've found that if we replace our current memory allocator with a circular buffer and pre-allocate everything in an SRAM we can get power-off tolerance AND allow ourselves to make use of all of our memory while not even needing to WASTE the cyles on freeing our memory! We'll save on the oders of 1ms over 50actions! That's a HUGE boon for our batter life!" you'd walk out the head of the office. Saving 500ns, 100 bytes, or even improving something on that scale no matter what it is in contect is huge.
The problem boils down to one thing. For the embeded systems people saving 1MS may be on the oder of 20% of their runtime. For the python shop saving 10K of memory is probably on the oder of sub-00.001% of their memory usage.
It is all about context.
(Disclaimer: I have changed from LL to arrays in some applications because it made a measurable improvement to the speeds of my systems.)
Also, if you're working in an HLL, know how LL is implemented in your PL. Because even in Lisp, not all LLs are created equal, and even if you create them the same way, they don't necessarily have the same perf characteristics.
For instance, because Haskell, ML, and the other functional languages don't allow datastructure mutation, they can CDR-code all their lists, something Lisp does as well (which is why list literals created with QUOTE cannot be modified, IIRC). This collpses the linked list structure into something resembling an array, increasing cache response time. Additional conses will be allocated separately, but this will still increase efficiency.
Performance and memory is one of those weird things where it doesn't matter until it does, and then it really matters. I can't count the number of projects I've been on where there wasn't a way to "scale" out, we had fixed resources and the only path forward was deep low level optimizations.
I would also challenge that 99% of all applications are disk bound but I think it's really besides the point. Really, the argument is that performance doesn't matter in all situations, which is true, but hardly means that we should be against writing fast software.
>but hardly means that we should be against writing fast software.
On the contrary.
Lisp is slow. Python is slow. Ruby is slow. Smalltalk is slow. What do these languages have in common? Dynamism. They trade speed for other that were, in the language designer's opinion, equally or more important than being fast.
The point is, that when you make a decision about performance, the decision has consequences in either direction. LLs are slow, but they have a lot of advantages. With skip lists you can get decent access tumes on ordered LLs, and in some contexts even O(n) is acceptable. But what LLs do better than other list structures like arrays is insertion. With an array, you get best-case O(1) appends, but all other types of insertion are O(n), and even appends can be O(n) if you run out of space and have to reallocate.
By contrast, provided you have a pointer to the location in the LL that you want to insert at (which is why most LL uses in applications like to insert at the head of the list), LL insertion is guaranteed O(1). That's sometimes useful.
Most of the time you should, I'd say. Regardless, the decision should be very natural/ trivial for any developer - understanding the performance attributes of the most common data structures is not asking too much of developers.
> They trade speed for other that were, in the language designer's opinion, equally or more important than being fast.
Yes, of course. I am not advocating for highly tuned software - I've stated as much in the last post. There are often tradeoffs.
No one is arguing that a linked list is not more algorithmically efficient at certain things. What I will say is that Vectors still end up faster for most operations, and it shouldn't be hard for a developer to determine when those situations arise.
I am not arguing against LL. I am just saying that it isn't 'lunacy' to understand basic performance characteristics of your software. Your post essentially came off, at least to me, as "people are crazy for wanting ot use a more efficient data structure".
It's not: it's very important.
>Your post essentially came off, at least to me, as "people are crazy for wanting ot use a more efficient data structure".
My point was more that people aren't necessarily crazy for using an LL. I don't, however, think that anybody is crazy for choosing not to use one for perf reasons.
I guess what I'm saying is that AFAICT, we're entirely in agreement, and I have no idea why we thought we weren't.
I find that taking these lessons to database access patterns helps a lot. Know your data access, and the data structure design has meaningful discourse. Don't know your access patterns? You are unable to pick the best one. Period.
Pretty much: if you don't know the access patterns, draw up a naive implementation so you can figure them out.
This is actually connected to one of the disadvantages of Lisp: because Lisp makes it so easy to draw up a naive datastructure based on LLs, it can take some effort to rip all that out and make something actually fast in its place.
>I wouldn't say it is the dynamism as much as the lack of control.
Don't undereatimate the cost of runtime dynamism. Lisp compilers have gotten pretty good at avoiding implementing it when possible, but there are pretty tight limits on how far you can go with that sort of optimization.
Essentially, every time you call a CLOS method, or you use eval, or you in any way introspect on your runtime state, or create the possibility for your code to do so at runtime, the code you are writing becomes more costly to run.
I view it as reducing the coefficient of writing a program. This means more will be made. So more slower ones will get made.
However, nothing prevents you from writing a fast program in that language. Other than the slower successes.
Suppose you're required to solve a problem with very high performance, and it has to be expressed in some high level language. No high level language achieves it using any straightforward code without dropping to assembly language. Not C, nothing.
In that situation, I'd arm myself with Lisp, because the problem basically requires inventing some specialized fast language and mapping it to the machine at hand.
I did not think I was stating anything profound.
You can sit a person in front of a whiteboard all you want. Brainwash them about arrays, maps, matricies, trees and graphs and they have a high likely hood of coming out knowing nothing but verbatum what you have told them. Conversly you cannot sit a person in front of a computer, guide them through the exercises that I described, and expect the same as the student who once sat in front of the whiteboard.
Trees grow from seeds and the best way to plant these seeds are not with an expo marker but, in my opinion, by bringing the student to a crossroads where they need to discover a concept on their own. This is a common tactic in game design: allow the player to discover new rules after you've taught them the basic foundation.
After they understand the basic foundation of how they will be interacting with the machine I think that, with the guidance of the correct assignements in the notebook codesegment phase of the program, the student will be able to create these different routines and ideas on their own.
Some such examples I will provide below:
- Make some way that will allow you to find a number between two possitions in memory
- Make a wrapper for this routine that will operate from a starting possition and an offset of the size
- Make a way to find the distance between two points on an X, Y plane
- Find a way to apply the same transformation in every item between two points in memory
- Find a way to implement a way of storing data about an X, Y plane. For instance where a dot is on a section of graph paper
- Make a subroutine that will allow you to store potentially infinite items in a collection. There are many ways to approch this but the three main ones are to: use a section of memory that is preallocated and reallocated when it is filled, make some way to daisy chain items of the list together possibly by wrapping them in in more data that will serve to aid your program, do the same as the daisy chain but allow the chain to coninue in more then one direction. Hint: this will probably need an init_<structure>, add_<structure>, remove_<structure>, free_<structure>
This would take a long time but under the correct stimulating guidance the student will be able to seek out why they need these tools. These tasks should be presented after they've completed a project that someone in our position knows that the optimal way of solving the problem was not choosen and a more abstract and simple solution exists. These situations will present themselves often. I've possitioned myself to make these suggestions to my peers at my university who are having a very difficult time passing the classes we are in together. The people who need to see why AND how.I'll look at their work and say "how about try using X method of solving the problem and show me what you come up with" and when they come up with a solution I say "now try and make it a library. Remove it from your current solution and allow yourself to use it for further work on other projects".
This changes the way they think about programing.
I feel that you greatly misunderstand why theory is important. It is not just something to be memorized to aid in implementation. It is useful and interesting in its own rite. CS Theory is Mathematics and like mathematics can be pursued simply with the goal of better understanding.
An understanding of Turing Machines and computability is a good example for this. Generally knowing that there exist uncomputable functions is of little practical use as you are exceeding unlikely to encounter one in implementation. Similarly understanding turing machines well is not useful as they compute in a very different way compared to current computers. However, from a purely theoretical standpoint it is critical to know that there exist uncomputable functions.
> You can sit a person in front of a whiteboard all you want. Brainwash them about arrays, maps, matricies, trees and graphs and they have a high likely hood of coming out knowing nothing but verbatum what you have told them
The same could be said for teaching implementation. Thoughtless memorization is rarely useful in any field. You can instead have them discover the theory like they would discover an understanding of implementation you advise.
Much of the theory of CS is not particularly hard to work out yourself if you are given the right hints. For example, an approach to teaching sorting algorithms could start by asking students to devise an algorithm to sort a list, and then have them compare algorithms and devise a way to evaluate which ones are the best and in which ways. Then after their progress slows introduce ideas like big O to help them further develop their ideas. The sorts taught in introductory algorithms classes are not very hard to understand (or design), and with the idea of big O in hand the introductory analysis in within reach of the student.
However, I agree that teaching programming in general from learning the rules to interact with tyeh computer and building up abstraction is often the right path for many students. Personally, it was not a great start for me (I started with C; not exactly the lowest level, but lower than most CS courses nowadays). I would have preferred to learn more theory earlier in my learning, and that is not easy to do when you are focused only on the code and not on the ideas behind the code that are universal.
I don't think you understand what I mean. I don't mean the theory isn't important. Nor do I feel that the only thing important is the theory.
What I do feel is this: - If you're teaching someone something they don't care about yet and wont remember, it's useless - If you're learning theory before running into WHY you need that theory then you by definition don't care
Our field should be about hiding the unimportant abstraction for the time being and it shouldn't be able shoving it in your face and saying "you'll need this in 3 years when we get to graphs".
No one will remember that. I have a hard time remembering every single "important algorithm". Do you think I could write a radix sort off the top of my head with no prep time? What about something easier like a merge sort? No. I don't care because my job isn't writing sorts. Most of the time using the built in language sorting function is ok. If I need to write one I choose based on the language I'm using and task by sitting down, thinking through my past experiances and what I used them (like not using a radix for floats/strings and instead using a merged quicksort). After I find one that'll work like it has in the past I google for that and reimplement the algorithm.
There are hundreds and thousands of ideas that I need to keep in my head when programming of which sorting is one of the least important ones.
> The same could be said for teaching implementation. Thoughtless memorization is rarely useful in any field. You can instead have them discover the theory like they would discover an understanding of implementation you advise.
The entier point of my post is to say we shouldn't do that. We should give them a task that they will want to acomplish and like every good task you take one too many cakes from a stranger and fall into a rabit hole of other problems. You can go from
- I need a script to manage this deamon
- Now I want logs parsing and a way to run analytics on them
- Ok now I want to run realtime events triggered by these log lines
- One of those needs to be a SMS service, let me go write that
And that goes on and on and on and on until you run into every problem in the book a software developer runs into.Feature creep, undocumented code, bad styles, slow performance due to features, breaking changes, why a dev enviroment is important.
Programming is a small part of being a programmer.
> Much of the theory of CS is not particularly hard to work out yourself if you are given the right hints
That's exactly how I feel.
> Personally, it was not a great start for me (I started with C; not exactly the lowest level, but lower than most CS courses nowadays).
C has many problems that are not present in far lower levels in the stack. In assembly you can do anything any way. You don't need to care. You have a magical way to save the contents of a register and get it bad, to go to a subroutine, and a massive set of "pre-defined functions" (instructions).
On older, simpler, systems this was even less of a problem. For instance a Z80 machine has huge advantages one such being the amazing instruction set and extremely simple features.
> I would have preferred to learn more theory earlier in my learning, and that is not easy to do when you are focused only on the code and not on the ideas behind the code that are universal
The theory should come as you get stuck, not before. The act of getting stuck and then pulled out of the hole is what teaches you when something is meant to come in handy.
One such example is when your car battery dies. You probably don't have one of those self-jumping battery packs in your car but they come in handy. You only ever see why after your battery goes flat and you cant find anyone to give you a jump.
My point is that there does not need to be a need for the theory. Learning for the sake of knowledge is enough. If you don't care about that reason though, learning much of theory will be hard unless you have a more concrete reason (a need for the theory in practice).
> Do you think I could write a radix sort off the top of my head with no prep time? What about something easier like a merge sort? No. I don't care because my job isn't writing sorts.
I think pretty much all programmers should be able to write a merge sort off the top of their heads. At its core mergesort is really just `merge(mergesort(leftside),mergesort(rightside))` which should not be hard to remember and writing the splitting of the list and merge is something any decent programmer should be able to do.
I will give a pass on radix sort though, it is a little more complicated and not at widely known. (I would also excuse not knowing how to implement heapsort).
> > The same could be said for teaching implementation. Thoughtless memorization is rarely useful in any field. You can instead have them discover the theory like they would discover an understanding of implementation you advise. > The entier point of my post is to say we shouldn't do that. We should give them a task that they will want to acomplish
I am not sure I understand your response. Would you not have people naturally discover theory with strategically minded hints to help make sure they don't get stuck for a long time?
> The theory should come as you get stuck, not before. The act of getting stuck and then pulled out of the hole is what teaches you when something is meant to come in handy. > One such example is when your car battery dies. You probably don't have one of those self-jumping battery packs in your car but they come in handy. You only ever see why after your battery goes flat and you cant find anyone to give you a jump.
Oftentimes you need to know the applicable theory before you get into a problem that necessitates it because you would never know that the theory even existed unless you had studied something related. For most practical people, a decent taste of some of the big theoretical ideas should be learned simply to facilitate later on-demand looking up of theory.
For example, big O is a powerful concept, but you may not have ever heard of it unless you looked into theory of algorithms. Despite that you may start writing some brute force (exponential time complexity) algorithm and not realize that is a problem while working on AI pathfinding for a game. Despite there being many polynomial time complexity algorithms out there.
More seriously though, knowing a number of NP-complete problems may help you realize that a problem you are working on is NP-hard and thus you should stop looking for a polynomial algorithm for it (unless you think you can break NP =? P).
Following your analogy, what if you never knew that even jumper cables existed and instead got your car towed to a mechanic every time your battery died. You may learn about jumper cables after doing that once, but it would have been much better if you knew they existed beforehand.
I'd love to write more but I usually need a prompt on a topic that I've thought about. I try to keep my ideas to myself until I've formulated an argument for either side that is "sufficient" in my mind.
I'd love to write about this in more detail and I'll definitely write about anything emailed to me if I'm able to formulate an idea either way. I'm heading home soon and write up something more detailed on this topic and why I feel this way on the topic of education.
What is a "true scottsman" of CS? Low level programmers? What about people that have pioneered the theory of computer science? The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.?
I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute.
Increasingly today the underlying architecture, for most intents, is becoming irrelevant (to first order of magnitude). The biggest gains are not made from superoptimizing compilers, but from algorithmic efficiency. That doesn't figure anywhere in your curriculum.
I think your curriculum would be great as an intro to computer architecture, or even as a series covering the topic, but I don't think it's an adequate introduction to computer science.