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

statistics)

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

Notes

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)