Like in most CS programs, Berkeley undergraduates usually take CS 170, officially named "Efficient Algorithms and Intractable Problems" (Even though intractable problems are maybe 20% of the course. Unofficially, the course has a much better title of "CS Theory" on some of the department webpages). Despite being part of the CS program, this class requires almost no coding; the only coding assignment is a final project which only accounts for 5% of the final grade, and the nature of the assignment is very unlike the rest of the work in the class (when I TA'd, I think less than 10% of students used an algorithm technique they used on a homework to tackle the assignment).
Instead, as the alternate title for the course suggests, it's a course on the theoretical aspects of CS. Namely, students learn about different techniques for designing algorithms and towards the end some other parts of CS theory. In an average week, a student will learn about a technique like dynamic programming, divide and conquer, etc. and then use it solve homework and test questions of the form "here's a problem, write an algorithm that solves it quickly, prove your answer is correct." Briefly speaking, it's a class where you code on paper, blissfully ignoring the many issues of real code, and just focus on designing good algorithms.
Recently, I've been of the mind that the removal from coding may actually be a net negative (Part of this may have to do with the exciting news that Jelani Nelson, a theoretical computer scientist who has a background in participating in coding competitions and coaches the Harvard ICPC team, recently joined Berkeley). That is, I think that there are many pedogogical gains to be made at a minor cost by turning maybe 20-30% of the homeworks into coding problems instead of math problems. The intent isn't to replace the proof-based problems, but rather accompany them: Maybe e.g. a question is cut from the all-proofs homework, and then students are asked to instead spend that time coding up their on-paper solutions to the remaining problems.
Transfer skills from other courses
The main benefit of switching to a more coding-focused model is that I think many CS majors who make it to the theory courses have a lot of coding classes on their transcript already, and ideally a lot of CS fundamentals they got from those classes, and these fundamentals should transfer over but don't, but maybe would if we used coding to draw them out.
My experience from TAing undergraduate theory is that students don't know how to debug on-paper algorithms very well (which is not necessarily their fault, especially at a school like Berkeley where the reality is there are too many students for the amount of resources we have it's more likely we just can't do a good job teaching all of them). Sometimes, they just don't think their solution is wrong; they write a proof that they don't have the experience to tell is "hand-wavey", and feel like their incorrect algorithm is correct. The fact that some number just go to office hours and effectively ask TAs to debug for them rather than learn how to tell when they're correct doesn't help.
These same students usually take some number of coding classes where they are required to debug much more intricate programs (e.g. the dynamic programs we ask them to write can usually be implemented in ~10 lines of Python using barely anything besides lists and for loops, much shorter than a single method in an average project in the intro coding class). They should be familiar with the idea of generating test cases, running through code step-by-step to find issues, etc. These techniques aren't 1-to-1 applicable to debugging on-paper algorithms, but I think some of the fundamentals behind them still are. For example, finding examples that trick your code is a skill that definitely transfers to verifying paper algorithms, and comes up a lot in research (and if anything is even more important; when a correct algorithm can take years to show is correct, you want to be able to quickly show your incorrect algorithms are incorrect).
I think something about the proof-based class setting leads students to fail to apply the iterative refinement approach to coding they learn in other classes to designing algorithms and writing proofs. Maybe it's that in order to know your algorithm is correct you need to know your proof is correct, and then it seems like turtles all the way down, instead of a bunch of green passes on unit tests. My hope is that by adding coding portions to small algorithmic problems, students are encouraged to transfer over some of the debugging skills they learn in other classes to the theory setting, and then have more time to develop the skills more unique to the theory class rather than relearn the transferable skills. If we structure the questions so they are encouraged to write code before proofs, maybe by the time they're sure their code is correct, they'll also have an idea about how to prove it's correct as well.
Besides this reason, I think there are several smaller benefits:
Bridge the gap between theory and practice
A (I think somewhat misguided) criticism of computer science theory and encouraging/requiring industry-minded students to take theory classes is that theory is somewhat removed from practice and what someone may be doing in a day-to-day SWE job. If I am right about this being misguided, we should be able to give students concrete examples that show how the algorithmic techniques are used in practice by the companies they're hoping to work for (for example, maybe we have a homework problem on the greedy algorithm for max-cut, and then we ask them to implement and run it on a real-life data set to solve a community detection problem that a SWE for a social media company). This comes with the pedagogical benefit that students will be happier and more motivated to learn something if they are convinced it is practical.
Prepare for coding interviews
When they're optional, many students take algorithm design classes because the homework problems in them are the closest analog to questions in coding interviews. If they're taking them for this reason, then we may as well mimic the coding interviews somewhat by having students actually code.
Theoreticians do code (sometimes)
Even for people who are trying to go to grad school in CS theory, even if they are not going to work on research in algorithms, coding can be a great tool for just testing conjectures. If they're already in the CS major, taking the CS class, they may as well learn how to use the computer part of computer science to test theoretical ideas.
Easier to grade
This is far from the most important point to me, but after the initial hurdle of setting up autograders, coding questions are easier to grade than hand-written proofs. One worry is that an important part of algorithms classes is getting the right runtime. For most algorithms students are asked to design in these classes, the runtime is something like linear or quadratic, and so a test case of size 10^5 would run pretty quickly for the right answer but still be reliable in distinguishing between students who get the best runtime and those that use simpler but slower algorithms (whereas distinguishing between e.g. cubic and quartic runtimes might be a bit harder to do).
Downsides
There are admittedly a few downsides I see to trying to shift to a more coding-based theory class. First, there is the need to setup the infrastructure for the coding aspects of the class. But, this is a non-recurring time investment that e.g. one could hire some undergraduates to figure out over a summer. Second, theory TAs might not be the best at TAing for coding assignments. But again, the coding aspects should be small compared to assignments in other classes, and will ideally only use very simple coding primitives, so chances most of the issues with code will be theoretical rather than coding issues.
The main downside I can think of is that the more time students spend on coding, the less time they spend on the theory they're supposed to learn. Like most of math, CS theory is something you learn by applying it over and over, and rarely do ideas stick the first time, so we might be sacrificing a lot of understanding by exposing students to fewer examples in order to have them to code as well. My counterarguments for why this might not really be too huge a downside are
1) while students may get exposure to less examples, they will likely get more out of each example,
2) students, especially those on the lower end of the grading curve (who maybe are trying to get the assignments done rather than doing them as a learning exercise), probably aren't actually getting much more out of doing many many examples if they weren't deeply connecting with the first few.
3) if students do have time and want more problems to work on, it shouldn't be that hard to supply them with some,
4) for topics like divide and conquer and dynamic programming, there's really only 3 or 4 core examples that need to be understood to solve 99% of the problems a student might see.
No comments:
Post a Comment