Great Ideas in Theoretical Computer Science
cs.cmu.edu
cs.cmu.edu
15-251 Great Theoretical Ideas in CS is the freshman spring semester discrete math & theoretical CS (a follow up to the discrete math course they take freshman fall). The course itself goes for breadth over depth. In this aspect, it serves as a solid foundation for all theory classes students take going forward. It's a class where students learn proof techniques, collaboration, and problem solving.
The course is often praised for its rigor. The problem sets require a fair amount of work to complete, and the course staff sets a high standard for responses.
On the other hand, it commonly receives criticism for being quite intense as a freshman class. Many CMU students look back on it as one of the hardest classes they took.
I personally feel quite lucky to have taken 251. It gave me a foundation to appreciate a lot of deeper CS topics, and taking it freshman year meant I had 3 years more to put it to use.
It happened multiple times that I googled some relatively obscure topic, and I found multiple excellent sources from Carnegie Mellon professors. For example, there is this excellent document [1] by Jonathan Shewchuk, about the conjugate gradient method, and you will found as many as four lectures about DRAM memory on youtube.
[1] https://www.cs.cmu.edu/~quake-papers/painless-conjugate-grad...
I have no doubts about CMU's excellence, but I found Berkeley's undergrad CS education to be quite good. There certainly were research professors who were bad teachers, but many like Shewchuck were outstanding teachers, and there were also several Teaching Professors whose job description to focus is more on teaching than research, like Dan Garcia, Paul Hilfinger, John DeNero, and Brian Harvey (since retired): https://www2.eecs.berkeley.edu/Faculty/Lists/faculty.html
I too have heard that private schools like Harvard and Stanford are not very hard once you get in, just very hard to get into (though I can't speak from experience). I haven't heard people say that about Berkeley, which is a public school so it doesn't have shareholders where alumni can form a controlling majority, and it's funded more by the state than by tuition. That also certainly was not the experience of myself or anyone I know.
There's this mentality at Berkeley that the EECS classes are the hardest and most competitive in the country (and that private schools just give everyone A's) but after meeting many CMU graduates I realized that it's program is also similarly rigorous. The classes might not be as competitive but then again I don't think that means it's worse for it.
Slides: http://www.cs.cmu.edu/~aada/courses/15251s16/www/schedule.ht...
I've lately studied a bit of program design when it comes to working out. A lot of effort goes into designing workout programs, making the programs efficient, trying to get the maximum results from the least amount of effort. There's a clear progression and a clear way of measuring progress. Every exercise, stretch, and movement is supposed to a particular function that best moves you toward your goal. Particular muscle sets are targeted at particular intensities for particular intervals on particular days. There's a reason for every specific decision that gets made.
You can contrast this with the aimless way a lot of people workout. They go to the gym, they do whatever exercises or work on whatever machines seem like a good idea to them at the moment, and hope it increases their fitness in some non-specific way. Lacking good metrics for measuring effectiveness, they often judge a workout by how sore it makes them the next day (an extremely poor way to measure effectiveness). It's not that this approach can't improve your health, it's just that it's extremely inefficient compared to the more goal orientated and progression based system.
In my experience most universities follow the aimless second approach - throwing what they can at the students, hoping some of it sticks, and judging the courses based on difficulty (this usually becomes even more obvious when professors explain their courses). I don't think I've come across any study measuring the effectiveness and metrics of different programs and progression paths.
To use your gym analogy, it's like focusing on one muscle group per week. On Monday, you're shown proper form and technique for a squat, but by the following Monday, you'd better be able to squat significantly more than you could a week ago (and you'll get graded on it). Are you going to become a competitive squat weight lifter? Absolutely not. Do you now know proper form, and understand what it takes to train properly? Almost certainly.
I'd also note two things:
- Most topics covered were useful in later courses.
- A lot of the credit for this course's success can be given as much to really, really dedicated TAs as it can to the professors.
(Note: I took this course my freshman year, it was blisteringly hard, and I wouldn't have traded anything for it.)
https://github.com/papers-we-love/papers-we-love#other-good-...
Why other mathematicians at the time, were so nasty towards Cantor's ideas? The quotes noted in the PDF -- just sound nasty and dismissive (or may be this is not the whole story)
There's even a separate article on objections to his theory: https://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_th...
Seems like the notion of "completed infinity" which sort of gives infinity ontological status (? I'm no mathematician) did not sit well with some--I guess I could understand why--it definitely isn't an intuitive notion:
"Before Cantor, the notion of infinity was often taken as a useful abstraction which helped mathematicians reason about the finite world; for example the use of infinite limit cases in calculus. The infinite was deemed to have at most a potential existence, rather than an actual existence.[18] "Actual infinity does not exist. What we call infinite is only the endless possibility of creating new objects no matter how many exist already".[19] Carl Friedrich Gauss's views on the subject can be paraphrased as: 'Infinity is nothing more than a figure of speech which helps us talk about limits. The notion of a completed infinity doesn't belong in mathematics'.[20] In other words, the only access we have to the infinite is through the notion of limits, and hence, we must not treat infinite sets as if they have an existence exactly comparable to the existence of finite sets."
I guess this shows that the overall pragmatic value of your work may eventually win out against formal refutations.
In this relaxed view, Cantor's arguments make sense from his premises, and it's interesting to entertain the idea of his premises because they lead to such interesting results. Whether or not "completed infinities" are "real" is delegated to the philosophers, while mathematicians 'play the proof game', and change the rules if they make it more fun.
It's like telling a lay person (or even many mathematics students for that matter) that 0.999999.... = 1. They understand the proofs, but it's so against their intuition there is a visceral negative reaction to it.
I agree that all of the proofs you normally see in high school are flawed in one way or another because they don't properly define what "..." means in the first place.
If I'm wrong then I'm wrong for this reason. Mathematicians are using the symbol … ambiguously. Because in some places in math it really does just mean “and so on“ and nothing more. Or more pedantically “and keep going in such a manner following that pattern“.
If, as you say, in instances like this mathematicians take … to mean “the limit (from calculus) of the demonstrated sequence” this is news to me. Well, maybe it's not news to me but I'm not exactly buying it.
What I'm saying is that the expression could be taken to be one of any number of things (not sure if I ought to qualify that with the phrase 'mutually exclusive'): (1) the (symbolic representation of the) sequence, (2) the most recently generated term, (3) the generator (4) the limit (from calculus) of the sequence. That you say the convention is that it most assuredly is 4 is not something I'm buying into. (I'd nearly go a step further and assert that it ought not be defined this way).
Where we get into problems, I believe, is when people say nonsensical things like the sequence reaches 1. Or if they start talking about the actually completed sequence rather than a symbolic representation of it. And this, by the way, is the gripe that people have with Cantor's completed infinities. It really is an ontological claim, not a mathematical one that such things exist. It's a claim whose refutation I support. When this topic comes up on HN I invariably point[0] people towards the absolutely best book I've read on the subject. René Guénon's The Metaphysical Principles of the Infinitesimal Calculus. This book is lucid, compelling, precise. I urge anyone with even the slightest bit of interest in this topic to read it. The notion of the continuum is a very very slippery beast and I know of no other book that deals with the topic so well. Category theorists have a much better handle on the smoothness of the continuum than set theorists because they have far better machinery.
[0] http://www.sophiaperennis.com/books/rene-guenon-series/the-m...
Here's a link to a copy in various formats on Archive.org https://archive.org/stream/reneguenon/1946%20-%20The%20Metap...
You're demonstrating why so many people get confused by the 0.999... notation: they (and you) are thinking of it as the sequence (0.9, 0.99, 0.999, ...) ; but actually it doesn't represent this sequence, or a process for producing this sequence; rather, it represents the limit of this sequence, which is a different type of object: a real number.
> Mathematicians are using the symbol … ambiguously
Sure, it can mean other things in other contexts (like in my description above of a sequence), but we're talking about what it means in the case 0.j_1 j_2 j_3 ... where the j_k's are base 10 digits. In that case it has a well-defined, non-ambiguous meaning: \lim_{n\to\infty}\sum_{k=1}^n \frac{j_k}{10^k} .
> If, as you say, in instances like this mathematicians take … to mean “the limit (from calculus) of the demonstrated sequence” this is news to me. Well, maybe it's not news to me but I'm not exactly buying it.
OP is right. I have a degree in math and this is what mathematicians mean by 0.999...
> What I'm saying is that the expression could be taken to be one of any number of things
Yeah we could have had the notation mean something else. But we didn't. We have other notations for the things you're talking about. Who cares?
> That you say the convention is that it most assuredly is 4 is not something I'm buying into.
What would it take to make you believe that this is what mathematicians mean by this notation? I promise with all my heart that this is true.
Don't take my word for it. Here's some random analysis book. Flip to page 31 (51/686 in the numbering of the PDF): http://www.matematica.net/portal/e-books/Apostol%20-%20CALCU...
> (I'd nearly go a step further and assert that it ought not be defined this way).
Plenty of stuff in math has pedagogically dubious notation, it's not really novel or philosophically interesting to claim you dislike some piece of notation or think it could have been better. It's all just convention.
> Where we get into problems, I believe, is when people say nonsensical things like the sequence reaches 1.
No mathematician is saying that. The sequence (0.9, 0.99, 0.999...) quite clearly never reaches 1, and any mathematician will agree with that. But its limit is 1.
> Or if they start talking about the actually completed sequence rather than a symbolic representation of it. And this, by the way, is the gripe that people have with Cantor's completed infinities. It really is an ontological claim, not a mathematical one that such things exist.
Well, things don't have to "exist" for us to be able to study them in mathematics, so what's the point of claims like this?
This notation is defined as meaning the limit as n approaches infinity of the sum from k=1 to n of 9/10^k . A sequence doesn't have to reach its limit!! For example, the limit of the sequence 1/2, 1/4, 1/8, ... is 0, even though the sequence never reaches 0. The limit of the sequence 0.9, 0.99, 0.999, ... is 1 (and this is BY DEFINITION what 0.999... means).
Or, you can decide to give some arbitrary meaning to all that stuff, and get some incredibly useful results. It's your choice.
Yes, there is. Ask yourself: What's the decimal expansion of 1/3, or pi?
For someone who doesn't understand what 0.999... means, why should we expect them to understand what 0.333... means and believe that it exists?
Do you really know "why" 0.99.. = 1 by writing 0.99... = 3 * (0.33...) = 3 * 1/3 = 1 ?
I'd argue that you just kicked the can down the road.
From your examples -- one's a ratio and the other is irrational. Almost as if you suggest "The set of real numbers exists, ergo 0.999999... exists"?
Then, given that 0.99999... exists, what useful properties could it possibly have, if it is to be treated as a number.
0.99999... = 0.9999... * 1 = 0.99999... * 9/9 = 0.99999... * (10 - 1)/9 = (0.99999... * 10 - 0.99999... * 1)/9 = (9.99999... - 0.99999...)/9 = 9.00000.../9 = 9/9 = 1
So if 0.99999... exists and has the same arithmetic properties as decimal expansions of rational numbers, its value must be 1. Now whether you think it should have these properties is an entirely different question, but most mathematicians seem to like it this way.
And the claim is correct. It is the statement that the limit of the partial sums of the inverse powers of 9 is 1, which can be rigorously proven with the epsilon-delta definition of a limit.
Well, it's technically a claim, but one that is obviously true once we agree on what 0.999... means. Anyone who doesn't agree that 0.999... = 1 has a different definition of 0.999... from the one used in mainstream math notation.
If you happen to somehow built a decimal expansion of 1/3, please share it with us!
This is incorrect. A decimal expansion is just a type of Cauchy sequence, which by definition is infinite (a function from the natural numbers to the reals).
You are confusing the decimal expansion with its truncated approximations.
> If you happen to somehow built a decimal expansion of 1/3, please share it with us!
Sure thing! Here it is:
def oneThird(place): if place >= 0: return 0 else: return 3
Convert to your favorite programming language/Turing machine/other abstract machine of choice.
def oneThird(place):
if place >= 0:
return 0
else:
return 3
def printOneThird():
for x in iter(int, 1):
print(oneThird(-x))
It seems you don't understand what a sequence is. Formally, a sequence is a function whose domain is the natural numbers (or integers). A decimal expansion is simply a sequence whose codomain is the set of digits {0,1,2,3,4,5,6,7,8,9}. I gave you just such a sequence.
Are you really going to continue disputing a basic mathematical fact?
What I am saying is that the definition should be put in place whenever ellipsis is used. Better yet, do not even use ellipsis. Else at some people get confused.
An incorrect but partial analogy is use of physics meaning of the words energy and power in common language.