Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: How to best acquire theoretical computer science knowledge?

news.ycombinator.com

Post reply on HN
Print view View original

111–120 of 122 posts

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#111

Post by sytelus »

jandrewrogers wrote: post #88

There is an alternative approach that inadvertently worked for me that may work well for you, particularly if your goal is to learn things beyond a conventional computer science curriculum. I have been working in high-end theoretical computer science for many years, with significant advances to my credit, but I went to school for chemical engineering. People are often curious as to how I acquired so much esoteric dom…

Before you dive in to hard problem, don't you need to create certain basic CS foundation? For example, can you start working on database kernel without studying even basic algorithms like red-black trees and B-trees? It would be interesting to know what are your go-to books for CS and other resources you use to dive in to particular topic? For example, do you start with Arxive or plain old web searches or taking cues from expert you know in person or look for books on Amazon or attend conferences?

Another thing is that creating algorithms are easy, especially the ones with bugs :). The difference between a joe-the-programmer creating an algorithm and a CS PhD creating an algorithm is that later produces a proof of correctness and performance while former relies on intuition for same thing. This is the hardest and most critical part of being a CS researcher. It would be interesting to know your approach for acquiring these skills.

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#112

Post by beloch »

If you can get a decent prof (not necessarily the most famous or well-published) to take you on to do a M.Sc., that beats the hell out of doing another B.Sc.. (Caveat emptor: Choosing a bad prof will bring you nothing but pain! Your supervisor is not just another prof. He will have an insane impact on you!) B.Sc.'s are the Honda Civics of academia. Universities mass produce them because they bring in the most cash per head. Grad school is more like a bespoke roadster or F1 car. The resources universities spend on grad students and research are disproportionate compared to what they spend on undergrads. Also, just as you learn more than just the core knowledge of your major in undergrad, you learn a lot of additional things in grad-school. Teaching, speaking, etc.. Above all, grad students are placed under pressure to actually think instead of just regurgitating. If you do another B.Sc. you'll be repeating a lot of stuff you already know.

A good prof will figure out where your knowledge is lacking and give you the resources to catch up fast. You'll likely be thrown into some grad-level courses that are way outta your league and will have to work like a crazy bastard to catch up with students who have a CS B.Sc., but you'll have great student-teacher ratios and your best teachers will actually be the other students. You'll probably have to TA material you'll be learning the night before, and teaching something is a fantastic way to learn it well. Eventually, you should do some research, and hopefully you'll have chosen a prof doing something you're interested in. Do NOT do a course-based M.Sc., as those are just upgraded Honda Civics!

You'll be under intense pressure to learn a lot fast, but you'll have the resources to do it. A B.Sc. will likely take longer and you'll spend a lot of time slacking off because undergrad courses are pretty damned easy. Also, a M.Sc. is a better credential to have than another B.Sc..

When you're choosing a prof, talk to the other grad-students. DO NOT just choose the guy who was nominated for a nobel prize. As the saying goes, "Happy students never won anyone a Nobel!".

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#113

Post by casperc »

mahyarm wrote: post #50

This is the core of a CS degree, each one is class, sometimes multiple classes that go into more detail. All interview questions will basically only cover these topics. 1. Algorithms & Data Structures 2. Baremetal Hardware. ASM, goes into the design of a physical cpu with ALUs, etc. Sometimes you make your own basic CPU. I suggest using a course with ARM ASM, simpler than x86 ASM. 3. Operating Systems & Multithreadin…

Could we try to add some books for each of these topics?

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#114

Post by jandrewrogers »

sytelus wrote: post #111
jandrewrogers wrote: post #88

There is an alternative approach that inadvertently worked for me that may work well for you, particularly if your goal is to learn things beyond a conventional computer science curriculum. I have been working in high-end theoretical computer science for many years, with significant advances to my credit, but I went to school for chemical engineering. People are often curious as to how I acquired so much esoteric dom…

Before you dive in to hard problem, don't you need to create certain basic CS foundation? For example, can you start working on database kernel without studying even basic algorithms like red-black trees and B-trees? It would be interesting to know what are your go-to books for CS and other resources you use to dive in to particular topic? For example, do you start with Arxive or plain old web searches or taking cues…

Yes and no. You do need to have broad enough experience with programming that you are comfortable with the basic implementation algorithms even if not up to speed on the nuances of them. However, a modern database kernel typically has few or no B-trees or red-black trees in it, using more specialized and purpose-built algorithms instead. Probably one of the most important lessons I learned when I first started poking at database kernels is that the algorithms in the literature were demonstrably not being used in commercial databases because the behavior did not match what you would expect. The algorithms you learn in a CS curriculum are often not really correct for any real system built with a high degree of skill.

I've only ever owned a few CS-related books (e.g. Li and Vitanyi). Trawling search engines for CS papers and references to CS papers with potentially useful information is how I did most of my work. Honestly, Wikipedia is a good starting point to find search terms but you still have to follow threads in the literature that are poorly or non-existently documented on the Internet. There are important areas of literature that still have very limited presence on the searchable web. This is a huge bias I see with many people fresh out of school -- if it is not on the web it doesn't exist.

On your last point, that is the most difficult part. To be frank, most PhDs in computer science do not have the skills to successfully design new algorithms either. Oddly, chemical engineering provided a very good conceptual framework for thinking about this; there are no pure mathematical solutions and you optimize complex systems in part by understanding every knob in a holistic context. One of the things I've noticed about most people with a computer science education is that they make a large number of implicit assumptions about the nature of computational and algorithmic systems that are not required and sometimes not correct, often without realizing it. Most of the algorithm work I've done amounts to violating implicit but foolish assumptions in the orthodox literature that no one had seriously examined in decades.

It is not just computer science, in most fields of endeavor the vast majority of things are done the way they are because that is the way they've always been done as set forth by a smart person a long time ago. The underlying assumptions and implicit constraints are rarely reexamined. I found a lot of upside to studying theoretical knobs that had been essentially frozen in literature since at least the 1980s.

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#115

Post by mahyarm »

jd007 wrote: post #77
mahyarm wrote: post #50

This is the core of a CS degree, each one is class, sometimes multiple classes that go into more detail. All interview questions will basically only cover these topics. 1. Algorithms & Data Structures 2. Baremetal Hardware. ASM, goes into the design of a physical cpu with ALUs, etc. Sometimes you make your own basic CPU. I suggest using a course with ARM ASM, simpler than x86 ASM. 3. Operating Systems & Multithreadin…

I would add computability and complexity theory to that list. Some computational complexity should be covered in algorithms and data structures, but theory of computation is not really (as algorithms by definition solves only computable problems). A fundamental knowledge of what is and what isn't computable is quite important in theoretical computer science IMO.

Yes I forgot about that. In my degree it was just the second 'algorithms & data structures' class.

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#116

Post by mahyarm »

mahyarm wrote: post #50

This is the core of a CS degree, each one is class, sometimes multiple classes that go into more detail. All interview questions will basically only cover these topics. 1. Algorithms & Data Structures 2. Baremetal Hardware. ASM, goes into the design of a physical cpu with ALUs, etc. Sometimes you make your own basic CPU. I suggest using a course with ARM ASM, simpler than x86 ASM. 3. Operating Systems & Multithreadin…

Forgot to add that computer graphics can use linear algebra & calculus.

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#117

Post by revorad »

petercooper wrote: post #4

I'm going to keep this reply shallow but my advice is dig up a curriculum and course guide for a CS degree (there are many publicly discoverable with Google), establish what all of the main topics and threads are, grab the best/most recommended textbooks for a couple of topics at a time, work through the books a few pages at a time and for anything you don't understand, Google and learn about it. Take copious notes a…

What's the MSc in software engineering course you're going to do? What's the curriculum for it?

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#118

Post by jophde »

tspike wrote: post #99
jophde wrote: post #82

Earlier quoted context omitted.

In order to get into an MS program would I need to do a BS in CS or just do the prerequisites I am missing. Off the top of my head I know that I am missing Calc 2, Calc 3, Linear Algebra, Algorithms, and Operating Systems. Does it matter where I do the prerequisites? I imagine I could just do the maths at a community college.

I did the exact same thing. You only need to do the prerequisites. No, it doesn't matter where you do them, but it's obviously best if you do them at the same school you intend to attend, as you'll be able to get recommendations from professors in the same department, and obviously the courses will transfer fine. EDIT: FWIW, at the University of Colorado, I had to do 2 courses above calc 1 - for me that was calc 2 an…

That's a really a good point about the letters of recommendation. I think this is the route I will be going down. I had no idea how I was going to get the letters otherwise.

Do you have to apply to take the prerequisites or do you just pay them and go?

Re: Ask HN: How to best acquire theoretical computer science knowledge?

#119

Post by ninh »

Universities tbh are more for meeting likeminded people nowadays: most of the stuff taught at CS can be learnt on your own given you're disciplined enough.

Just to underline some of the points others have made, here is a short list of things I found most valuable from my CS degree:

- Algorithms, Datastructures & Computational/space complexity (ADC). - Discrete Mathematics. It's the lingua franca when talking about CS and you will need it to understand ADC for example. It introduces set theory, graph theory and so forth, which are used in ADC/AI etc... to describe and solve problems.

- Linear Algebra: if you ever want to work with 3d stuff, this one will be essential. It'll also work out nicely for 2d work, and seeing as you mentioned you've got a knack for UI work, you probably will appreciate this one. It'll allow you to get an understanding of for example affine transformations etc... You will need a computer graphics course too, but this is definitely a prerequisite course to do those.

- Probability and statistics. I really hated this course (it's also one of the harder ones coincidentally), but once you "get it", you really do "get it". Ever wondered how gesture recognition works? Or how spam filters work? Well, the math required for this will be addressed here, together with the following subject.

- Artificial Intelligence. Extremely useful if you're interested in game dev, or just want to learn to solve problems in a smart and efficient manner. It combines ADC with discrete mathematics with probability & statistics.

- Calculus. If not for the math, it'll definitely make you look at things in a different way, which imo in turn, contributes to your way of looking at problems. Partial derivation / integrals and how it can relate to 3d surfaces for example. And let's not forget taylor series etc... It'll give you an idea of how mathematical functions such as sin(1) etc... can be implemented etc...

- Operating systems, Computer Architecture/organization. Essential for understanding what happens under the hood. Allows you to reason about what the best code path is for solving a problem. Should you use the GPU for example instead of the CPU etc... and if so, why? etc... It also introduces models such as finite state automatons etc... which are also applicable in language processing for, say, compilers.

And that brings us to the last, but certainly not least subject, my all time favorite: - Compiler construction. Gives you an insight in how languages are being processed, and how to design your own language and build a compiler for it. It should also give you additional insights on how runtimes/virtual machines work.

The software engineering courses were more about processes, philosophies and patterns etc... and even though they're definitely useful, I think most experienced software engineers have already "got this". Either via books, company policy/culture or via experience.

Again, these are my experiences, YMMV :) Good luck!

Post reply on HN