Quantum Algorithms
Monday, March 06, 2006
A Better CS Degree?
Reading a recent post on Can't Count Sheep got me reflecting on my own CS degree (obtained nearly 6 years ago). My course work seemed to be about half practical and half theoretical, which added up to very little. I have no one to blame but myself for what I didn't learn, but my ideal degree would cover a lot more fundamentals and a lot fewer applications. I'd say it's more valuable for a CS graduate to be comfortable with Knuth than object-oriented Java.

My ideal CS curriculum
My ideal CS degree is basically an algorithms degree, with abstract problem solving as an overarching sub-text. Programming languages and mathematics are taught for the sole purpose of enhancing understanding of algorithms.

Topics like databases, compilers, AI, networking, graphics, operating systems, object-oriented programming, robotics, etc are not included. (Undergraduate HCI will be moved to the communications department.) Yes, on one level most of these types of courses are about special classes of algorithms and data structures. But it's important that more fundamental notions are well understand first before writing FTP clients and OpenGL based games. My view is applications should be learned on the job, through projects, or in a masters program, but should not displace fundamentals.

The curriculum is divided into 6 sequential lots. Classes in a lot may be taken in parallel, and there are no electives. Each lot, excepting the first, requires a project. At least 2 of the projects undertaken by each student must be software systems, and at least 2 must be theoretical research projects. The students may choose their own projects, but they are supervised by grad students and have various deliverables. Students may work individually or in groups of 2 or 3, but proportionally more is expected out of multi-person groups. Projects are also required to be increasingly sophisticated as students advance.

Most classes would involve components of theoretical coursework (i.e. problem sets) plus programming with both Scheme and C. The types of programs required would not be large and complex, but instead short and very challenging. Both C and Scheme are emphasized because they encourage thinking in two very different perspectives. Programming is included even for traditionally theoretical courses.

I thought it would be better to err on the side of too much math and not enough EE or Physics (actually none).

First lot:
00] Intro to programming with C (like Stanford's 106x when it was C based)
01] Intro to programming with Scheme (like MIT's 6.001)
02] CS Math 1 (discrete mathematics) (i.e. Stanford's CS 103x)
0x] Non-CS specific math (i.e. calculus, linear algebra, basic

Second lot:
10] Deeper C (similar to the first half of Stanford's old CS 107. Also includes enough Unix API to serve later classes, and a small bit of assembly)
11] Introduction to algorithms and data structures (i.e. Stanford's CS 161)
12] CS Math 2 (logic and proofs)
13] Project 1

Third lot:
20] Automata and Complexity Theory (i.e. Stanford's CS 154)
21] Parallel and Distributed Algorithms
22] CS Math 3 (set theory, number theory)
23] Project 2

Fourth lot:
30] Intro to NP Completeness
31] Tree, Graph and Network Algorithms
32] Intro to Information Theory (similar to MIT's 6.050J)
33] Project 3

Fifth lot:
40] Searching and Sorting
41] Intro to Randomized algorithms
42] Intro to Quantum Computing
43] Project 4

Sixth lot:
50] Quantum Algorithms
51] Heuristic Algorithms
52] Provably Correct Programs (using the Z language)
53] Project 5

Course [21] might seem too specialized to be taken so early, but is placed here so later courses can take advantage of parallel and distributed algorithms. Both are becoming more and more important as multi-core processors and networking become ever more pervasive in systems.

Course [22] would include some of the theory covered in intro and mid level database classes.

Course [31] will not be the student's first exposure to graphs and trees, but will be a chance to go deeper than most undergraduate programs go in these topics.

It's a shame that freshman level courses like [32] seem to exist nowhere but MIT.

Course [40] will delve deep into searching and sorting, perhaps using Knuth vol III as a textbook.

Course [51] would include some of the more fundamental algorithms from traditional robotics and AI courses.

I'm not sure if courses like [52] exist anywhere. Even though Z is not commonly used, I think it would be great if a CS degree meant you could write 100% provably correct code, given enough time, if need be.

If someone would feel ill prepared for the job marketplace without being Java experts, they could do something Java related for all 5 of their projects (they could research garbage collection and just-in-time compilation for their research projects, and write Java applications for their 3 programming projects)
Too many math courses, not enough astrophysics ->
PHYSICS: Black Hole Encryption
David Voss

What happens to the quantum information ingested by a black hole? In 1997, Thorne and Hawking argued that information swallowed by a black hole is forever hidden, despite the fact that these dense objects do emit a peculiar kind of radiation and eventually evaporate. Preskill countered that for quantum mechanics to remain valid, the theory mandates that the information has to be released from the evaporating black hole in some fashion. Although Hawking conceded in 2004, the disagreement between Preskill and Thorne still stands.

Smolin and Oppenheim now find that one of the main assertions made about black holes may be flawed. It is often assumed that as the black hole evaporates, all of the information gets stored in the remnant until the very end, at which point the information is either released or else disappears forever. Instead, Smolin and Oppenheim suggest that the information is distributed among the quanta that escape during evaporation, but is encrypted and thus effectively locked away.

The catch is that it can only be accessed with the help of the quanta released when the black hole disappears, in much the same way as a cryptographic key unlocks a coded message. The result offers a link between general relativity and quantum cryptography. -- DV

Smolin and Oppenheim, Phys. Rev. Lett. 96, 081302 (2006).
Sounds like a crappy degree. Remember, this is undergrad. You are oversimplifying the field. Most professors would have a real beef with your assessment. The practical applications are necessary to make valid the theoretical underpinnings. You discredit much of the important parts of the field. What about software design? OO is part of design, and a solid grasp is essential to become a proficient programmer. Knowledge of NP completeness hardly ever comes in handy in industry, or most of academia for that matter, and "understanding Knuth" as you say will not ultimately lead to better programmers necessarily. I guess there's a reason they don't hire inexperienced otaku lackeys to design curricula.
Thanks for the comment, but no thanks for the silly ad-hom crap.

What you seem to be missing is that this a proposed "Computer Science" degree. Literally. Not a software engineering degree, not a Java programming certification course.

OO design is important in the real world, but anyone who can't easily pick up OOP on their own wouldn't be admitted :P Plus you truly learn OOP by bulding large software systems, not by getting a few lectures about "is-a vs. has-a". Students can build OO systems for their independent projects.

"The practical applications are necessary to make valid the theoretical underpinnings."

I seriously disagree. You wouldn't say the same thing about physics or mathematics, would you?
Sure I would. Otherwise it's trite mental masturbation.
What I suspect is ignorant snobbery. Computer science is a broad field, and as an undergrad, we had the choice of "specializing" in areas we found interesting through electives. Talk to virtually any computer scientist. Of course, you won't get that much out of OO, for example, just by lectures, but that same applies to anything. Mathematics is not a spectator sport either. In order to have any sort of understanding or ability in math, you need to practice it as well. And don't tell me OO is so plain and simple. That's just plain irritating to hear. I could say that about fields in physics and math; OO has a beauty to it as well. I am not talking about a Java certification either (not that there is anything wrong with them, but I digress), and the fact that you mentioned Java and not say Smalltalk, just shows how much exposure you have to this area. When I was learning Smalltalk, it was a mind opening experience. And having a clear understanding of OO or functional programming is not at all trivial. Please do not discredit other people's work. This kind of arrogance will not get you far. I believe that both the theorectical and practical sides of computer science are just are just as important, and heaving this kind of drivel just makes me want to pull out my hair. Both add meaning to each other, each is a testament to the other, one does not live without the other in some vacuum. I believe mathematician M.A. Armstrong called approaches such as yours poor forms of intellectual entertainment. It very much reminds me of how some artists try desperately to sound like philosphers.
Sounds pretty much like the courses I had to take at ETH Zurich. The first two years are the same for everyone (doesn't matter if you want to become a theorist or a software architect):

-Introduction to programming (using Eiffel)
-Logic (mainly theoretical course, but teaches also Prolog)
-Analysis I
-Linear Algebra
-Probability theory and statistics

-Datastructures and algorithms
-Analysis II
-Discrete Math
-Digital technique

-System programming (in C)
-Computer architecture
-Information theory (so there are other universities than MIT which teach IT :-)
-Theory of computation (Turing machines, P vs. NP, etc.)
-Introduction to electrical engineering
-Introduction to Computational

-Operating systems
-Computer networks
-Software architecture
-Formal methods and functional programming
-Introduction to Database systems
-Scientific Computation

Although the courses in the second year seem to be pretty practical they focus on concepts and try to give you an overview of the field of computer science.

The next two semester I could pretty much choose the courses I wanted to take.

semester 5:
- Scientific computation (advanced)
- Distributed systems
- Randomized algorithms
- Introduction to quantum computation
- Information security and cryptography

semester 6:
- Theory of computation (advanced, more an algorithm class which tries to give an overview over the different fields in the area of theoretical computer science)
- Computer architecture (advanced)
- Approximation algorithms
- Cryptographic protocols
- Graph Algorithms

I was pretty satisfied by this course selection and I think that it is a good idea to make the first two years the same for everyone with mandetory courses. What I missed were projects.
> Computer science is a broad field,
> and as an undergrad, we had the
> choice of "specializing" in areas > we found interesting through
> electives.

That's great, but that won't be part of my ideal degree. "Specializing" as an undergrad is bound to be superficial. You need more depth of knowledge to truly appreciate applications.

A physics undergrad who wants to specialize in string theory isn't going to be doing much string theory for many years. I don't see why CS students shouldn't be as thoroughly prepared before specializing.

> Of course, you won't get that much
> out of OO, for example, just by
> lectures, but that same applies to
> anything.

But it applies especially to OO. Unlike subtler mathematical ideas, understanding the basics of OOP is fairly easy. Mastering it takes years of applied effort. I wasn't belittling OOP, I'm just saying it's a misplaced topic to teach undergrads.

> and the fact that you mentioned
> Java and not say Smalltalk, just
> shows how much exposure you have
> to this area.

No it doesn't. I mentioned Java because it is the language du jour in undergrad CS cirriculums. Smalltalk is rare and getting rarer as the few schools that use are dropping it. There's hundreds of languages I could have or should have mentioned. But Java is the most popular.

> And having a clear understanding
> of OO or functional programming
> is not at all trivial.

Never said it was. OO has it's place, but not at the core of a computer science education.

> Please do not discredit other
> people's work. This kind of
> arrogance will not get you far.

Not wanting to teach something could hardly be construed as arrogance or discrediting anything. Relax.

> heaving this kind of drivel just
> makes me want to pull out my hair.

Pull away.

> Both add meaning to each other,
> each is a testament to the other,
> one does not live without the
> other in some vacuum.

Well said. But there is also a time and place to learn each one. Fundamental theory first, applications later.
dlockfree: That does sound pretty close to what I have in mind. I'd personally remove the Physics and EE intro, but the rest of it looks like real CS and not fads or superficial applications. I wouldn't expect less from Einstein's alma mater.
This is very interesting - in a lot of ways it's like the curriculum I have actually studied in college, though I'm actually coming out with a math degree. I've studied more math (Real and Complex Analysis, Abstract Algebra, Geometry, Mathematical Logic) and missed out on bits of the later parts of your curriculum, but it's really, really close to what I've done.

I go to a school where there is no computer science department, and thus all of the "computer science" courses I've taken have actually been math courses. I don't exactly think I've somehow satisfied the requirements for a undergrad degree in CS, but I am hoping to persuade some CS PhD programs to let me in anyway. I like the idea of a CS degree as fundamentally distinct from software engineering or what have you, though it is kind of strange for me to actually have this degree given the current expectations of graduate programs.

Some specific thoughs:
I found that understanding object oriented programming helped me when I got to my programming languages class. The concept of an object helped ease in things like functions being first order in SML (or really in lambda calculus). Would you really not want to teach this? Or just teach it conceptually, leaving out many of the details of implementation?

Most of my classes have had some programming projects, but we weren't really taught to program so much as sent off to make something that worked in the language of our choice. Often we would modify existing code, so the projects were smaller but more focused on the theoretically significant bits. Would the theory courses have programming components?

I'm kind of surprised that you leave automata to the third sequence - this was actually the first thing I learned in college CS class, concurrent with an overview of very simple programming structures (variables, loops, etc) in java. What's the rational for this?
CSC 465 in Toronto (UfT) is pretty much [52].

link: http://www.artsandscience.utoronto.ca/ofr/calendar/crs_csc.htm#CSC465H1

Taught by E.C.R.Hehner: http://www.cs.toronto.edu/~hehner/
Post a Comment

<< Home

Powered by Blogger