Foundations of Computer Science(infolab.stanford.edu)
infolab.stanford.edu
Foundations of Computer Science
http://infolab.stanford.edu/~ullman/focs.html
53 comments
Just my opinion:
> -- start with binary and work your way through hardware and logic gates
I'd consider this foundations of computer engineering.
> -- start off with theory like turing machines, first order predicate logic and work your way up
I'd think of this as more like foundations of computability theory, but, yeah, this seems like another viable angle for me.
> -- start off with a hello world, and slowly iterate over programming (in a post internet world, this is especially popular) with loops, if/then statements and so on
I'd call this foundations of software engineering.
> -- start with binary and work your way through hardware and logic gates
I'd consider this foundations of computer engineering.
> -- start off with theory like turing machines, first order predicate logic and work your way up
I'd think of this as more like foundations of computability theory, but, yeah, this seems like another viable angle for me.
> -- start off with a hello world, and slowly iterate over programming (in a post internet world, this is especially popular) with loops, if/then statements and so on
I'd call this foundations of software engineering.
> I'd think of this as more like foundations of computability theory, but, yeah, this seems like another viable angle for me.
Nah I would call this foundation of computer science.
Nah I would call this foundation of computer science.
How about a compromise: theoretical computer science
what other kind is there?
Practical, obviously. ;-)
"What does his lucid explanation amount to but this, that in theory there is no difference between theory and practice, while in practice there is?" –Benjamin Brewster, 1882
https://quoteinvestigator.com/2018/04/14/theory/
"What does his lucid explanation amount to but this, that in theory there is no difference between theory and practice, while in practice there is?" –Benjamin Brewster, 1882
https://quoteinvestigator.com/2018/04/14/theory/
I love this exchange, because it helps answer another question often asked, which is "Why shold I study CS at a university if I want to be a Software Developer?"
These are 4 different corners of a pretty large, but related field, and while not a single individual can fill out the whole spectrum, it does make sense to expand into each direction. Software Engineering is a discpipline of Computer Science at my university, and my degree also taught systems architecture and computability theory.
Each of these can but doesn't have to be important for your work as a software developer, and very few people working in CS in any capacity can completely ignore and of the other facilities.
These are 4 different corners of a pretty large, but related field, and while not a single individual can fill out the whole spectrum, it does make sense to expand into each direction. Software Engineering is a discpipline of Computer Science at my university, and my degree also taught systems architecture and computability theory.
Each of these can but doesn't have to be important for your work as a software developer, and very few people working in CS in any capacity can completely ignore and of the other facilities.
FWIW, the foundations of computer science I learned at university in the first two or three semesters was "all of the above".
Predicate logic, data structures and algorithms (much of what you see in the submitted link), binary and logic gates, a programming language from scratch ('what is an if') in our case Java - yes I skipped those lectures of course and just took the exams ;)) and math (some repeat of calculus from school, then more advanced and also probabilities).
I.e. we learned all of these things 'first' in parallel.
Predicate logic, data structures and algorithms (much of what you see in the submitted link), binary and logic gates, a programming language from scratch ('what is an if') in our case Java - yes I skipped those lectures of course and just took the exams ;)) and math (some repeat of calculus from school, then more advanced and also probabilities).
I.e. we learned all of these things 'first' in parallel.
My university started with digital design using gates, real analysis, and introduction to programming using C. Then in the next 3 semesters we did computer architecture, data structures, algorithms, microprocessors, ToC, OOP, OS, Linear Algebra, Graph theory, so your approach is actually followed in the real world.
> -- start off with theory like turing machines, first order predicate logic and work your way up
Or start off with the lambda calculus-based alternative to Turing machines, as in seen in SICP.
Or start off with the lambda calculus-based alternative to Turing machines, as in seen in SICP.
I learned this stuff in my school following the textbook https://introtcs.org/public/ and found that in general it was nice to put the actual "gory details" mechanics of how a TM or lambda calculus works into the background to focus on computability.
This topic transcends machines as we know them including binary and Turing and Neumann and all that Jazz. These are things philosophers 2000 years ago could and might actually discussed and though about. Dividing a piece of land into states, then counties then cities, etc. is an example of a tree. These "foundations" are mostly useful with computers as we know them, but they don't have to. People might discover new species of computers that do things very differently, but I think will still use these foundations.
I also agree with you that something like gates and binary would be a great introduction to computers. This book doesn't seem like an intro to CS, but for somebody who has already programmed or somebody coming from a mathy background.
Foundations and Introduction to X are typically very different courses. The second has a much more informal approach, and the objective is to facilitate understanding for someone in their first approach to the discipline.
In the case of foundations, the aim is to establish a solid and complete base on which to build all subsequent knowledge; and that need not be easy at all.
In the case of foundations, the aim is to establish a solid and complete base on which to build all subsequent knowledge; and that need not be easy at all.
Related HN submission:
https://news.ycombinator.com/item?id=30084470
https://cacm.acm.org/magazines/2022/2/258231-abstractions-th...
Aho and Ullman received the Turing Award last year and their Turing lecture and this book have some overlap.
https://news.ycombinator.com/item?id=30084470
https://cacm.acm.org/magazines/2022/2/258231-abstractions-th...
Aho and Ullman received the Turing Award last year and their Turing lecture and this book have some overlap.
Looks good! Their examples of using goto in automata (chapter 10) is the first time I've seen it that makes sense to me.
This is great! It would be wonderful if this kind of thing would be added to the open textbook movement so people can mix, match, and update the content. https://open.umn.edu/opentextbooks
Us societal rejects would greatly appreciate it.
Us societal rejects would greatly appreciate it.
> Us societal rejects would greatly appreciate it.
Don’t do this. Even if you’re in a bad place socially this is the internet. No one knows you’re a dog. Offline it’s a bad idea too because you’re at least as likely to provoke “kick that whining puppy” as pity and both of those are bad.
If things are shit that sucks but they can get better.
Don’t do this. Even if you’re in a bad place socially this is the internet. No one knows you’re a dog. Offline it’s a bad idea too because you’re at least as likely to provoke “kick that whining puppy” as pity and both of those are bad.
If things are shit that sucks but they can get better.
I'd appreciate it, too.
Oh man this book is great! I still have the copy I managed to find second hand for my undergraduate degree. It’s amazingly relevant and useful given how old it is.
Yep. It's also a fantastically clear exposition of C programming, in addition to the very choice material on data structures and computer science.
What other books teach data structures/algorithms along with discrete math like this one?
Knuth?
For those who want a local copy, below might help:
$ wget -r -p --tries=3 -nc --no-parent http://infolab.stanford.edu/~ullman/focs.html
Fetches the focs.html file (and all other under ~ullman too!). My wget-fu isn't that great. :)
$ wget -r -p --tries=3 -nc --no-parent http://infolab.stanford.edu/~ullman/focs.html
Fetches the focs.html file (and all other under ~ullman too!). My wget-fu isn't that great. :)
ERR_ADDRESS_UNREACHABLE ?
It's quite ironic that the "Foundations of Computer Science" are hosted on an HTTP server without TLS.
I was lucky enough to have gone to a university system (UC) which gave me an opportunity to learn the fundamentals of computer science, but when I see major universities (like Stanford) operate public HTTP sites without TLS, I can't be anything other than disappointed.
It's 2022, there's really no excuse to operate public HTTP sites without TLS (with minor exceptions). Even self-signed certificate HTTPS would be far better than HTTP without TLS.
I was lucky enough to have gone to a university system (UC) which gave me an opportunity to learn the fundamentals of computer science, but when I see major universities (like Stanford) operate public HTTP sites without TLS, I can't be anything other than disappointed.
It's 2022, there's really no excuse to operate public HTTP sites without TLS (with minor exceptions). Even self-signed certificate HTTPS would be far better than HTTP without TLS.
Why would it need encryption? The only convincing argument would be stuff like as insertions by ISPs and so on but that's extremely uncommon. Additionally everyone and their mother seems to be a CA these days...
There's more to HTTPS than just data integrity promises. One of the most popular topics on Hacker News is privacy, so I'd imagine people here would understand why virtually all public websites should be HTTPS only.
Ah yes, the obvious privacy implications of reading topics in elementary computer science.
You are right that virtually all public websites should be HTTPS only. Serving static, non-sensitive data is the use case that "virtually" is there for.
You are right that virtually all public websites should be HTTPS only. Serving static, non-sensitive data is the use case that "virtually" is there for.
> You are right that virtually all public websites should be HTTPS only.
That is correct.
That is correct.
Is there any reason to be so sarcastic here, other your desire to engage in bad faith here? There are good reasons to make the paths that people request on public websites private to the client & server, even when that content is seemingly not interesting (to you) to gather for snooping purposes.
Its always entertaining to see users claiming bad faith when they are engaging in bad faith themselves.
Please list the good reasons that are relevant for a fully publically accessible page of information that contains nothing that asks for usernames/passwords or whatever.
Please list the good reasons that are relevant for a fully publically accessible page of information that contains nothing that asks for usernames/passwords or whatever.
The proof of the burden as to why this website should force all communication to be public is on you. HTTPS exists and configuring it is simple in this era, and the choice to not use it for a university's public website is either laziness or incompetence.
You surely must be aware that content like headers and even URL paths (and other parts of the URL) are confidential over HTTPS.
Why should I allow an employer, an abusive spouse, an abusive parent, a parole officer, a detective looking to charge me with a crime, a gang looking to intimidate me, know which content I'm accessing from a website? All it takes is something like a wireshark application somewhere between (inclusive) my network and the server's network, and they will full have access to everything I've requested from the server and everything it has responded with, including all metadata. No warrants needed.
Like I said in another comment: "Why should we make any personal details about our lives public information if it doesn't need to be? Do you go around announcing all the things that you do in your life that are seemingly harmless? Sometimes revealing information to the public that one would think is harmless can end up doing a lot of harm, both to you and others. Privacy matters, a lot."
You surely must be aware that content like headers and even URL paths (and other parts of the URL) are confidential over HTTPS.
Why should I allow an employer, an abusive spouse, an abusive parent, a parole officer, a detective looking to charge me with a crime, a gang looking to intimidate me, know which content I'm accessing from a website? All it takes is something like a wireshark application somewhere between (inclusive) my network and the server's network, and they will full have access to everything I've requested from the server and everything it has responded with, including all metadata. No warrants needed.
Like I said in another comment: "Why should we make any personal details about our lives public information if it doesn't need to be? Do you go around announcing all the things that you do in your life that are seemingly harmless? Sometimes revealing information to the public that one would think is harmless can end up doing a lot of harm, both to you and others. Privacy matters, a lot."
> Do you go around announcing all the things that you do in your life that are seemingly harmless?
you must not like twitter much
you must not like twitter much
[deleted]
Don't feed the troll
Going against my better judgement and feeding the troll: While public key cryptography is Computer Science, HTTPS most definitely has nothing to do with Computer Science theory.
Why’s it /so/ disappointing? I/We would definitely appreciate if you could elaborate. I’m not saying https is pointless, but why is it such a big deal for a site like this?
And how is self signed better? If anything I’d say it’s worse! It creates a false sense of security.
And how is self signed better? If anything I’d say it’s worse! It creates a false sense of security.
Sure I'd be glad to elaborate. Why should we make any personal details about our lives public information if it doesn't need to be? Do you go around announcing all the things that you do in your life that are seemingly harmless? Sometimes revealing information to the public that one would think is harmless can end up doing a lot of harm, both to you and others. Privacy matters, a lot.
A self-signed certificate used for HTTPS still protects the client/server from snooping by a unaffiliated party, even if it doesn't protect from a MITM intercepting and responding to the request in the case where the client hasn't already added this self-signed certificate to their trusted CA store.
A self-signed certificate used for HTTPS still protects the client/server from snooping by a unaffiliated party, even if it doesn't protect from a MITM intercepting and responding to the request in the case where the client hasn't already added this self-signed certificate to their trusted CA store.
There are many rationales already written in many places. https://https.cio.gov/everything/ for instance. Or https://doesmysiteneedhttps.com/ .
Please explain your reasoning. Why would this site need HTTPS?
I don't think any explanation about a particular site is needed. I came to believe that we in HN all agreed that mass surveillance is bad and that promoting HTTPS everywhere is the least we can do make surveillance more difficult.
Just as no one would want government agents following them around as they go about their day attending university lectures, and just as we wouldn't be happy with that agent asking us "Why, what do you have to hide?", we also shouldn't be comfortable with having our visit to resources on stanford.edu be open to surveillance by every node on the network. In a world where even example.com uses TLS, we can surely expect the same from all Stanford subdomains.
Just as no one would want government agents following them around as they go about their day attending university lectures, and just as we wouldn't be happy with that agent asking us "Why, what do you have to hide?", we also shouldn't be comfortable with having our visit to resources on stanford.edu be open to surveillance by every node on the network. In a world where even example.com uses TLS, we can surely expect the same from all Stanford subdomains.
Just to push back on your first paragraph, there is no "we in HN". HN is composed of individual people with various degrees of belief in "HTTPS everywhere" and "mass Surveillance is bad", especially since many people here benefit directly or indirectly from money from mass surveillance.
there are many we's in hn emerging from the headlines we choose to click on.
All sites should be using HTTPS. Your phone doesn't audibly broadcast your emails as you send them, your snail mail doesn't come in completely transparent envelopes, and your doors have locks on them. It's minimal security to prevent the injection/filtering of information via MITM and consistent identity (for whatever that's worth).
Take just a moment to think about what the site could look like from China without HTTPS, if the CCP was interested:
Chapter 12 Propositional Logic
Chapter 13 Responsible State Guidance
Chapter 14 Using Logic to Design Computer Components
Chapter 15 Predicate Logic
Now it appears that a notable US institution supporting CCP-sponsored oversight, because someone was too lazy to use a self signed cert.
Take just a moment to think about what the site could look like from China without HTTPS, if the CCP was interested:
Chapter 12 Propositional Logic
Chapter 13 Responsible State Guidance
Chapter 14 Using Logic to Design Computer Components
Chapter 15 Predicate Logic
Now it appears that a notable US institution supporting CCP-sponsored oversight, because someone was too lazy to use a self signed cert.
> Your phone doesn't audibly broadcast your emails as you send them
Funnily enough I used to know a blind woman who would use the iOS screen reader at like 4x speed when doing email.
> your snail mail doesn't come in completely transparent envelopes
You mean like post cards?
> and your doors have locks on them.
Fair =)
Funnily enough I used to know a blind woman who would use the iOS screen reader at like 4x speed when doing email.
> your snail mail doesn't come in completely transparent envelopes
You mean like post cards?
> and your doors have locks on them.
Fair =)
not ironic at all, you're just confusing (theoretical) "Computer Science" with "Software Engineering" industry best practices.
I feel like in the absence of an overwhelming justification, your comment is just derailing the topic and attracting unnecessary attention.
Why is it important for this particular site to use https or tls?
-- start with binary and work your way through hardware and logic gates
-- start off with theory like turing machines, first order predicate logic and work your way up
-- start off with a hello world, and slowly iterate over programming (in a post internet world, this is especially popular) with loops, if/then statements and so on
But, perhaps aging myself, this book is close to my idea of the traditional introduction.