9 ms·
Great ideas in theoretical computer science
- abdullahkhalids 3y agoWhat would versions of this course look like for other fields? Great Ideas in Theoretical Physics? Great Ideas in Experimental Physics? Great Ideas in Economics? etc I did teach a course once called, Inventing the Information Age, in which we discussed all the inventions and ideas (starting from writing) all the way to modern computing infrastructure needed for a civilization to replicate our information age. This was not a single-field course, because the ideas/inventions were in language, physics, mathematics, and computer science. That made it more fun.
- osti 3y agoThe CMU class is for freshmen, so students without advanced background can still comprehend most of it. But for physics I feel that without at least some good physics and math background, you can't really understand and appreciate the "great ideas".
- abdullahkhalids 3y agoIf the students know the core concepts and mechanics of Calculus and Linear Algebra, which is entirely possible for high school students in certain parts of the world, it's possible to teach a lot of core physics ideas with simple models. In fact, in my undergrad, the Physics lab and theory courses were flipped - you look the lab course before the theory course. In the lab course you used simple maths and simple experimental setups to probe phenomena in mechanics, thermodynamics, electromagnetism, optics etc. Doing experiments/observations in astronomy, quantum mechanics are also possible at that level.
- josh-sematic 3y agoSean Carrol has a series he’s working on called “The Biggest Ideas in the Universe” which is on physics. Only the first one is out now (Time, Space, and Motion), but the second is due in May I think (on Quanta and Fields). Its intended audience is anyone with a high school education. It introduces basic ideas in calculus and then does use equations to motivate understanding, but not at the level you’d need if you were actually studying physics. I have a bachelor’s in physics but still deepened my understanding of General Relativity from the first one. Highly looking forward to part 2. https://www.preposterousuniverse.com/biggestideas/ https://www.preposterousuniverse.com/biggestideas/
- steve_adams_86 3y agoNice, this was the push I needed to start reading his book. I really enjoy his podcast and was on the fence about taking it on (thinking I don’t have the brain cells required to soak in the book) but the way you described it makes it seem like a fairly tractable project.
- shanusmagnus 3y agoThat sounds awesome and very creative. Do you have a link to an old class site, or a syllabus, or anything that would give a flavor?
- abdullahkhalids 3y agoI taught the course during the initial part of Covid, so the material ended up not being organized - split between different systems. But here are some of the books/papers that I sourced class readings from * Brian Winston - Media technology and society a history: from the telegraph to the Internet, Routledge (1998) * James Gleick - The Information A History, a Theory, a Flood (2011, Pantheo) * Michael G. Raymer - The Silicon Web: Physics for the Internet Age, CRC Press (2009) * Simon Singh - The Code Book: How to Make It, Break It, Hack It, Crack It (2003) https://www.jstor.org/stable/43737424 https://www.jstor.org/stable/43737424
- trenchgun 3y agoYour course sounds awesome. Do you have the materials somewhere available? Would love to read more about it.
- abdullahkhalids 3y agoSee my answer here https://news.ycombinator.com/item?id=39728134 https://news.ycombinator.com/item?id=39728134
- thejazzman 3y agoThe most painful class I ever took. I know, I'm not a real nerd, or something. I'm okay with it.
- russfink 3y agoInteresting to read your experiences. Looking over this, it seems to take a highly theoretical approach and work up, rather than a practical/applied approach and work down. I was surprised to see automata covered so early, which is more in the vein of computability theory than that of introductory concepts.
- leetrout 3y agoThere are literally dozens of us making great careers solving problems with computers without CS degrees or any particular interest in the lowest levels of computing nor the mathematical backings / abstractions. Horses for courses.
- __rito__ 3y agoRelevant: https://news.ycombinator.com/item?id=15153838 https://news.ycombinator.com/item?id=15153838
- deleted 3y ago[deleted]
- rramadass 3y agoYou might find this motivating : https://news.ycombinator.com/item?id=39721301 https://news.ycombinator.com/item?id=39721301
- pvg 3y agoA previous thread from 2017 https://news.ycombinator.com/item?id=15146905 https://news.ycombinator.com/item?id=15146905
- __rito__ 3y agoA more complete version: https://youtube.com/playlist?list=PLm3J0oaFux3aafQm568blS9blxtA_EWQv&si=M0qz7o99NnC_HWxS https://youtube.com/playlist?list=PLm3J0oaFux3aafQm568blS9bl...
- riedel 3y agoThanks. To me the first part linked above is rather "foundation of computer science". I remember this to be content of my first classes in CS ( turing machines, lambda calculus, finite automata, ... (Actually the course in 1999 in Uni Karlsruhe was unfortunately also was the last time I implemented things using Haskell). This full list I guess goes beyond and looks interesting.
- djaouen 3y agoI have nothing to add other than saying that Physicists and Philosophers often make better programmers than Computer Scientists. :)
- DrDroop 3y agoSometimes you find the truth at the bottom of HN. It hurts, I spend my early adulthood trying to learning most of the topics on this page thinking it would make me a great software engineer. These are good ideas, but I wouldn't call them great, they are often very dull and don't make one a great thinker.
- bo1024 3y agoNot really on the topic of this link at all. But I wouldn't be surprised, since you're likely comparing the few physicists and philosophers who switch fields against the average computer scientist.
- zitterbewegung 3y agoI think there should be a companion class on anti patterns or bad ideas in computer science. It’s much harder to see a horrible idea and then you have to argue why not to do something. Something like variable names being too long or short. How to figure out what to do with unrealistic timelines.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- soganess 3y agoI don't know where, but there is another version of this class that includes "The Probabilistic Method"[1]. While not exactly the same thing, I can't imagine doing modern existential (vs constructive) proofs of topological solution space obstructions without that style of thinking. [1]: https://math.bme.hu/~gabor/oktatas/SztoM/AlonSpencer.ProbMethod3ed.pdf https://math.bme.hu/~gabor/oktatas/SztoM/AlonSpencer.ProbMet... Bonus points for those interested -- I think this paper(sadly, not mine) has a concise collection / history of obstruction proofs in its background section (1.2/1.3 and since it is a paper all of them are cited!): https://arxiv.org/abs/2309.09913 https://arxiv.org/abs/2309.09913
- pushedx 3y agoYou may be referring to the version of this course that was taught by Luis von Ahn (the creator of reCAPTCHA and the founder of Duo Lingo), when he was a professor at CMU. https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-s09/Site/Calendar/calendar.html https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-s... He liked to call the course "SOME Theoretical Ideas FOR Computer Science", and it was known to be a very popular (and difficult) course.
- soganess 3y agoI didn't know LVA taught at CMU, rad! I did some digging and found the class: https://people.eecs.berkeley.edu/~venkatg/teaching/15252-sp20/ https://people.eecs.berkeley.edu/~venkatg/teaching/15252-sp2... I enjoy that it is called "More Great Ideas in Theoretical Computer Science", like a sequel (...and 'some' being the prequel). I'm now eagerly awaiting the 'return of the jedi' installment.
- pushedx 3y agoAh, great! Seems like there was a tradition of having fun with the course title.
- dogcomplex 3y agoDamn. Impressed to see something this fundamental that never made it into my computer science postgrad education (and judging by the depths and difficulty of it, might not for a while!) Seems like a powerful technique that scales to cover quite a lot of other problems.
- deleted 3y ago[deleted]
- rramadass 3y agoNice! If folks would like to learn these ideas by hand via programming, i highly recommend Tom Stuart's Understanding Computation From Simple Machines to Impossible Programs - https://computationbook.com/ https://computationbook.com/
- NlightNFotis 3y agoMy favourite computing book. Very highly recommended.
- 3abiton 3y agoDo you have any other favorite recommendations?
- NlightNFotis 3y agoYeah, I’ve also enjoyed greatly the following: * Computer Science, an interdisciplinary perspective by Robert Sedgewick * Code by Charles Petzold * Good Math by Mark C. Chu-Carroll
- __rito__ 3y agoWow, thanks for sharing!
- rramadass 3y agoYou might also like Algorithmics The Spirit of Computing by the great David Harel (https://en.wikipedia.org/wiki/David_Harel https://en.wikipedia.org/wiki/David_Harel). The book is accessible to the intelligent general reader (though not a popular science book) and covers its domain rather comprehensively.
- __rito__ 3y agoI will definitely give it a try. Genuine thanks again!
- bo1024 3y agoInteresting positioning as "great ideas" -- it seems like the topics are a pretty standard undergrad Theory of Computer Science course.
- lupire 3y agoI wouldn't expect the theory of a field to be built upon Bad Ideas! It is a strange course though. It is grad level (2xx at Harvard) but the syllabus is survey topics from a range of undergrad courses in CS. I would guess it's a smattering of advanced topics in those areas, but the description doesn't sell it as having all those topics as prereqs. Maybes it's meant as an extension school / professional master's class for people who do not have CS degrees? Refugees from math, physics, and autodidacts?
- yankjenets 3y agoIt's a second semester freshman course for CMU CS undergrads.
- shusaku 3y agoThat’s my impression too, maybe the name just gets undergrads more excited.
- projectileboy 3y agoIf you dig this you might like https://cs121.boazbarak.org/ https://cs121.boazbarak.org/, which also has a link to Barak’s textbook, available as a PDF.
- diebeforei485 3y agoThis class is great because it introduces a lot of concepts but most importantly really sharpens your problem-solving skills. > The method we tend to use in 251 is throwing you deep into the water without a paddle (i.e., giving you very basic definitions for a new topic you haven't seen and expecting you to solve things that you might be given in a course dedicated to that topic in say the third week). We do this over and over, pretty much starting from scratch on a new topic every week. As a result, it can be very frustrating—which, of course, is the intention. If you're constantly trying to solve things that are just outside of your reach, you develop better strategies for thinking about problems you're given.
- VoidWhisperer 3y agoI'm not sure I necessarily agree with this strategy. In my CS undergrad, I had an algorithms class where the professor did this and expected the students to be able to do homework assignments each week that were worth a significant portion of our grade with basically no explanation on how to solve these extremely complicated optimization problems. When comparing our assignments to that of another student taking the same class with a different professor, theirs were much, much easier. I dont think this teaching methodology made me gain any more from the course, if anything, it made me gain less because I constantly had the stress of trying to do these ridiculous problems on top of all of my other work every week
- ericjmorey 3y agoMaybe I'm not reading that correctly, but it seems like you were able to do more difficult assignments than the students in the other class.
- deleted 3y ago[deleted]
- volfied 3y agoFor algorithms, sure. For this class, it had worked great when I took it 20 years ago. The class didn’t expect us to solve the problems, just understand them enough to apply them in our daily thinking for software.
- assbuttbuttass 3y agoI TA'd for this course back in undergrad. Despite being in the CS department, it's structured like a math class, and all of the homework assignments are proof-based. I don't think I wrote code for that course a single time, except for pseudo-code for a Turing machine
- brcmthrowaway 3y agoComputation is a fundamental propery of the universe? How is that? How do flora and fauna compute?
- ozim 3y agoYou have to have right amounts of inputs to get outputs. Plants I grow are complex function of CO2, water, energy and bunch of other things things. But I do know if I don’t water enough or too much, plant function will return not good results.
- graycat 3y agoUh, let's take an example: Mars gets a force from the gravity of the earth. That force has magnitude and direction so is a vector. Mars also gets such a vector from each of the Sun, Jupiter, Andromeda, dark matter, .... Then to determine the direction Mars will go, have to add all those vectors with the current value of the Mars momentum vector. Soooo. the universe adds vectors, that is, does computation. Done?
- steve_adams_86 3y agoThis makes me wonder something. When I’m computing values in code I’ve written, the inputs and outputs are very quantifiable and the steps between them are too. There is a start and end to every part of the process. In the universe, how are the inputs and outputs divided into discreet units and states in which computation can occur? I know the universe isn’t running on a chip (wait… No I don’t), but what I’m unsure of here is how, or even if, the state of things in the universe is ever determined in order to be “computed” such that it can transition to the next state in which it has been acted upon again by the inputs around it. Perhaps it’s the wrong analogy. I don’t understand though how computations can work with a fluid rather than clearly sliceable and unitized parameters you find in current computing technologies. Or is the universe actually able to broken down into frames of time? I suppose if you don’t think you need to compute in discreet steps then the question doesn’t make sense. It’s taking the analogy too literally. I struggle not to, though. What is computation if it can’t be proven or reversible at any stage?
- tzs 3y agoTheoretical computer science can be fun. But it can also be really annoying! Around the time most schools were starting the 2014-15 school year I saw a post on Reddit in either a math or CS group from someone asking for how to solve a particular theoretical CS problem. The poster didn't say where the problem was from or why they needed a solution, but others quickly figured out it was from someone trying to cheat on the first homework set from COMS 331 (Theory of Computing) at Iowa State University. No one helped and the poster deleted their post. I thought it was an interesting problem and gave it a try, expecting it to be a short but interesting diversion. I didn't expect it to take too long because although I was not a CS major (I was a math major) I did take all of the undergraduate theoretical courses at my school and I got decent grades in them. That had been ~35 years earlier so I had forgotten a lot but the problem was from the first COMS 331 homework set so shouldn't require anything past the first week or so of that class, which should all be fairly basic stuff I would still remember. I spent a couple days on it and got absolutely nowhere. Several times since then I've remembered it, thought about it for a few hours or a day and have continued to completely fail. If anyone is curious, here is the problem: Define a 2-coloring of {0, 1}∗ to be a function χ : {0, 1}∗ → {red, blue}. (For example, if χ(1101) = red, we say that 1101 is red in the coloring χ.) Prove: For every 2-coloring χ of {0, 1}∗ and every (infinite) binary sequence s ∈ {0, 1}∞, there is a sequence w₀,w₁,w₂,··· of strings wₙ ∈ {0, 1}∗ such that (i) s = w₀w₁w₂ ···, and (ii) w₁, w₂, w₃, · · · are all the same color. (The string w₀ may or may not be this color.)
- scubbo 3y agoInteresting problem! I've never formally studied computer science, and my math degree is far behind me, so I probably won't be the one to help you solve this, but I'm commenting to at least remind myself to check back here. Some thoughts that immediately spring to mind (apologies if you've already thought of these - just getting the brain flowing!): * We only need consider colorings for which 0 and 1 are differently coloured. If 0 and 1 are the same colour, then we're trivially done - let w1, w2, w3, etc. all have length 1 * this smells like it'll be some sort of combination of induction and contradiction? E.g. "assume this property is true for w1w2w3...wn-1, and that wlog they are red. Assume there is no wn that can continue the sequence of red substrings - thus, all strings starting from the end of wn are blue. If that's the case _and_ if we can convert the string [w1...wn-1] into blue substrings, then we're done. So show that there is some contradiction proving that impossible (maybe using the observation I made above that we only care about cases where 1 and 0 are different colours)"
- Avtomatk 3y agoAnd where is Category Theory and Lambda Calculus?
- bsdpufferfish 3y agolambda calculus is one way to describe computable functions. this course chose to focus on Turing machines. category theory is historically not important to theory of computation, and it has questionable use if you aren't familiar with abstract algebra
- freework 3y ago"Theoretical computer science" is garbage. Of all the scientific fields, computer science is the one that is mostly closely related to fields where theory is most worthless. If you have a computer science theory, then write some damn code to prove it. Then share your code. Others can then run it and replicate those results. At the "theory" phase, the idea is worthless.
- bollu 3y agoYou are very wrong. Many of the key results of theoretical CS is to prove impossibility. There is no code to be written when you show that something is not possible. - Halting problem: impossibility of TM to determine if other TMs halt. - crypto: impossibility for a Turing machine to break a cryposystem in polytime - sorting lower bounds: impossibility to sort objects given only a less_than operator on them in time less than O(n log n) and so on. There is no code to be written for these, because they are mathematical theorems. > computer science is about computers as much as astronomy is about telescopes ~Dikjstra.
- ChrisClark 3y agoWow, just... wow. Theoretical computer science is literally more solid and real than any code you could write. It's literally the mathematical foundation of how your favorite language works. It is all precise mathematical proofs, not just 'thoughts'.
- hnfong 3y agoWhat are mathematical proofs but mere 'thoughts'? (I'm only being half rhetorical. I've been thinking about this deeply lately.)
- hibbelig 3y agoThe relationship between thoughts and proofs is analogous to the relationship between noise and music. It’s a subset kind of relationship. There is also the social aspect: people have to agree on it. Noise becomes music, and thoughts become proofs, only if several people agree.
- a-dub 3y ago"string theory" i found this stuff to be a lot of fun!
- Simon_ORourke 3y agoAhhh, I remember my old college course on time complexity, which was effectively the professor picking on random kids and saying something like - "I have some 4 dimensional matrix multiplication algorithm which then uses a bloom filters to match on random ids... what is the time complexity of this?", and some poor kid would stutter something like, "aaaaahhhh.... O(nlogn)", only to have the professor to shout "No, wrong!" and go pick on someone else.
- Simon_ORourke 3y ago> Garbage collection This is a huge Yes now. Every language that's become successful since 1999 has GC and is designed for all normal users to use it to manage all memory. In five years, Rust or D might make that last sentence untrue, but even if that happens, GC will still be in the yes category. Sorry, I had to guffaw when I read that last part about D. A dumpster fire of a language for garbage collection.
- sporkland 3y agoInspired by the title my two top ideas from theoretical compsci: 1. Move to front lists are at most 2x the optimal list order search time (and are often much better than any static list order). [1]. A similar conjecture exists for Splay trees but is unproven called the dynamic optimality conjecture. 2. Randomized algorithms (e.g quicksort) often have the same worst case time as a non-randomized one but often are much faster in practice than their non-randomized variants. 1: https://www.dgp.toronto.edu/public_user/JamesStewart/378notes/13mtf/ https://www.dgp.toronto.edu/public_user/JamesStewart/378note...