Tuesday, October 11, 2016

Ideal courses for a comp sci dept/I'm glad we don't do it

I once heard it said:

In our data structures course we read Knuth and ignore the proofs

In our algorithms course we read Knuth and ignore the code.

And indeed, there are many topics where the theory-part is in one course and the programming is in another.

With that in mind, here is a different way to offer courses (some depts already do some of this).

1) A course in Algorithms AND Data Structures. Actually I have seen this title on courses but its usually just a theory course. I mean you REALLY PROOF and CODE. Might need to be a year long.

2) Crypto AND Security. You learn crypto and security together and do both. If you only did the crypto relevant to security it might be a semester long and in fact it might already be being done. But I am thinking of really combining these courses--- code and prove. Might be a year long.

3) Formal lang Theory and Practice of Compilers. You do DFA, NDFA, CFG, but also do compiler design. If you also want to do P, NP, and decidability (spell check thinks that decidability is not a word!) then might not quite connect up with compilers, then again in might with theorems like: CFG equivalence is undecidable. Might be a year long.

4) Machine learning AND Prob/stat.

PROS: Theory and Practice would be more united.

CONS: Having year-long courses is hard for the students scheduling their courses. Would having just one semester of any of the above courses make sense?

CONS: Harder to find someone to teach these courses. I'll confess that I prefer to teach formal lang theory without any programming in it.

CAVEAT: I think theorists coming out now know more of the practical counterpart of their area than I did and perhaps than people of my generation did.

CAVEAT: A much less radical thing to do is to put more security in to crypto, more about compilers into Formal Lang Theory, etc. But thats a bit odd now since we DO have a course in security, and a course in compilers. Even so, seems to be a good idea and this I know many schools are doing.


  1. Out of the examples described probably the Algo+DS with proof+code is the most common. I've gone through classes where algorithms (e.g. sorting) were also studied empirically by adding counters and plotting the number of operations executed (both for synthetic and for real input). I thought that this was a nice complement to the theoretical analysis, and also a good pretext to practice programming, but in retrospect it may not have been the most efficient use of time.

  2. Maybe I'm stating the obvious here, maybe, on the contrary, it's just the typical mind fallacy, but I was under the impression that the route usually taken is the one used by my university with regard to subjects which feature both theory and implementation like the ones you enumerated (I would add: logic programming; graph theory; architecture together with assembly language; computational geometry et al.). That being: the professor lecturing the theory with proofs and the TA teaching the implementation details with code at the lab (with the added caveats that the professor may sometime take the lead in selecting the lab curriculum, leaving not much freedom to the TA and sometimes the professor themself may teach the lab). I am now actually curious how close this is to the usual approach.

  3. Security is more than just crypto! But if you mean doing crypto theory along with crypto implementation, then this is already the way it is taught in many places, including (to some extent) at UMD.

    Regarding data structures, I think the term is overly broad. In my undergrad data structures course we implemented things like linked lists, doubly linked lists, and binary search trees, for which the "proofs" that they work are trivial. So maybe you are referring to an advanced data structures course? But algorithms are about more than data structures...

  4. Algorithms course with projects, otherwise known as depressing on two fronts; the inability of many students to work through proofs and analysis, and their inability to implement a program to demonstrate the use of an algorithm even with several semesters of programming courses under their belts.