Data Structures

The syllabus, and from Fall 2018 onward, the official UC-Davis catalog, both recommend taking ECS 36C (called ECS 60 until Fall 2018) or ECS 32B (both are courses on data structures), before taking the undergraduate theory of computation course, ECS 120. They do not recommend taking them concurrently, but instead first completing and passing ECS 36C/32B before taking ECS 120.

Despite this recommendation, there are a few reasons why ECS 36C/32B is not an official prerequisite for ECS 120:

  1. Usually ECS 36C/32B is made a prerequisite for another course if the latter course has programming assignments, whereas traditionally ECS 120 does not involve programming.
  2. In principle ECS 20, Discrete Mathematics, contains all the relevant concepts needed for ECS 120. In practice, a data structures course is the way that most computer scientists start to really become comfortable with those concepts, since that course nicely blends something they are familiar with (programming) with the terminology, concepts, and formal reasoning of discrete math. (There are other ways to be prepared for a theory of computation course without having mastered data structures. For instance, most Mathematics majors tend to have seen enough formal definitions and proofs that they find a course in theory of computation easier than the average computer science student, even if they have not taken a data structures course.)
  3. It's been that way for many years, and bureaucracy and inertia at a large university makes it difficult to change things. If you saw some of the inner workings of the university, you'd be appalled at how many of the policies are there not because it is the best way to do things, but simply because that's way was it was done yesterday.

My advice for majors in computer science and computer engineering, who generally come into the course without much training in formal mathematics, is that they should come in with significant training in programming, particularly the kind of structured programming done in a course on data structures.

Most computer science programs at other universities require a data structures course as a prerequisite for a theory of computation course. We teach the same material as those other universities, so my opinion is that if it's a good idea for students outside of Davis to take the courses in that order, it's also a good idea for students at Davis.

One reason is that most of the challenge of a course like ECS 120 is learning your way around formal definitions and the idea of proofs and formal reasoning itself. It is easier to learn these tricky concepts if you can draw on your intuition from programming. During this course, we will cover new concepts, but these concepts will be defined in terms of objects like graphs, trees, lists, and other discrete objects. Now technically, these are covered in the Discrete Math course, ECS 20. But generally, computer scientists end up far more comfortable with those concepts after spending a whole data structures course writing programs to manipulate such discrete objects.

I should also point out that I'm NOT saying I will teach this course in a different way than other instructors, or previous quarters, with ECS 36C/32B being more critical with me now than with other instructors in the past. I teach the same material as any other ECS 120 instructor. But my expert opinion is that the material itself is, and has always been, and always will be, easier to learn after you have taken ECS 36C/32B, whether you take ECS 120 from me or from someone else. My efforts to make ECS 36C/32B an official prerequisite haven't worked, so in lieu of that, I'm just telling you how I would do things myself if I were a student (and how most other computer science students throughout the country already do them).

That said, ECS 36C/32B is not an official prerequisite. It is possible to succeed in the course without having taken a data structures course. Many people do it.

But the general trend is that students do better in this course if they have already passed ECS 36C/32B. The following chart shows average performance in ECS 120 over 10 years, grouping the students in many different ways that are difficult to compare directly. But for students who start at UC-Davis, the trend is clear. If they have completed ECS 60 (the name of ECS 36C until Fall 2018), they do better in ECS 120 by half a letter grade on average ("Concurrent" means taking 60 and 120 at the same time, which as you can see, doesn't help any more than simply not taking ECS 60):

trends.png