Designing an introductory computer science course: Part 1
This course attempts to teach programming methodology from an engineering viewpoint, as well give an insight into theoretical computer science.
Guidelines:
- Teach programming, and not the programming language. Discuss abstract ideas in class, and ask students to write implementations in a language of their choice. Avoid building language-specific patterns (for example, the double-for loop for generating prime numbers in C got stuck in my head). Discuss various different implementations AFTER the students have tried it themselves.
- Discussions should span several programming paradigms. Initially, cast problem statements to strongly indicate a paradigm. For example “Go over numbers from 1 to 10 and print those that are even” versus “Define an even number and print even numbers <= 10″. Later, let students figure it out themselves.
- Develop a hacker mindset- give students incomplete solutions written by other students and ask them to complete it.
- For routine assignments, prepare a huge problem set of ascending difficulty to randomly pick from, along the lines of Project Euler. Problems should cover algorithms, pure math, computational geometry, and dynamic programming.
- Conduct collaborative programming sessions where students learn to implement from each other. No single instructor will be able to provide such a vast variety of implementations.
- Prepare a reading list for software engineering, including articles on editing (introduction to specialized editors such as Vim and Emacs), debugging, versioning, testing, and profiling. It’s important to make students write large programs collaboratively in steps, so that they will be able to appreciate the importance of these tools.
- Prepare another reading list for theoretical computer science. Also give students sneak peeks into the latest work in every field. The purpose of this exercise is to get students excited, so that they can work independently to eventually discover their research interests.
- Finally, it all boils down to grading. If you’re going to ask students to evaluate things like (i++) + (++i) in the exam, it’s clear that you’re expecting students to know programming language intricacies, and not programming methodology.
lecture1.pdf (130 KB)
Tags: common lisp, functional programming, haskell
September 30th, 2009 at 7:21 pm
Excellent! I wish I had attended such a course when i started learning programming! One suggestion I would like to add is that along with programming, on a side-track and at a lower priority perhaps, teach your students how to use a programming editor. While not strictly necessary, it makes a huge difference in productivity down the road. You could integrate this with your step 6.
Encourage working on “projects” rather than small assignments, i.e any assignment that will span over at least a week. Introduce modularity into the assignments so that one assignment can hook into another to enhance usability. Give practical examples of design patterns using these assignments.
Other than that, I think your 8 points are remarkably well-drafted. Some friends and I are planning on teaching a “programming and tools for programming” course in our college, I think these points have created a good road-map for me :)
September 30th, 2009 at 7:37 pm
It looks like you are trying to put in too many courses together. Watch out. It might turn out to be my +2 Computer Science course. C++, Java, HTML, Staroffice all rolled into one. Needless to say my classmates never got beyond the for loop in both C++ and java and were clueless about anything more than in html…
I absolutely appreciate that you want to include SE skills in the course. But imho, SE is a tool. It does not justify independant training. The students must be given the programs to write.
The next day, the teacher should give them a demo of how he commits each of their programs to a repo.
The same day, he should ask them to make a few subtle changes and then generate a patch. Patching is very essential.
The fourth day involves patching and committing again.
Also, the students must be taught small languages like sed/awk and m4. They should be made to realize that different languages are good for different purposes. It is as pointless writing a blog tool in C as is writing an implementation of ld in java.
September 30th, 2009 at 8:25 pm
@vedang: Thanks! I’ve included the editor in point 6, as you suggested. I totally agree with your note about making students work on “projects”. Apart from helping them realize the importance of SE tools, it can be used to teach several SE aspects, including design patterns. Good luck with your course!
@Ashok: I think you might have misunderstood what I said. The objective of the course is not to teach everything, but rather teach students how to think in an abstract way. By not tying it down to a single tool/ programming language, I’m trying to eliminate the simple problem of students memorizing code, as opposed to understanding concepts. I’m currently preparing some slides to make this more concrete; you might want to check back when I’m done.
October 1st, 2009 at 9:58 am
Nice!
Your ideas are very refreshing. I think the idea of teaching the practice/art of programming in a way that is language-invariant is something that is lacking in most curricula.
I would like to add another point to your list (although I’m not sure if it qualifies as another point) :
Now I largely use programming for scientific and numeric computing rather than app development purposes. Correct me if I’m wrong, but if you were to compare two programs for solving a given problem, all differences between the two programs can be attributed to either : (a) A newer, more efficient algorithm being used (b) implementing the best algorithm out there in a more efficient manner.
(a) is obvious to any layman i.e. a better algorithm generally means a better program.
I think it is (b) that needs to be taught more rigorously in the curriculum. Maybe when a student writes a program in a given language, a prof/TA who is well-versed in the language should tell a student why his particular implementation is slower, what is the more optimal way of implementing the algorithm, and also explain why the given problem is better solved in a different language.
Of course, implementing the above suggestion I think is hard in any university as finding a set of people who are well-versed in different languages for teaching is a hard task.
Secondly, I think numeric/scientific computing must be taught as an independent module of the course, separate from software engineering. Most newbies lack formal exposure to the art of numeric computing. For example, many people just jump onto MATLAB and start writing large inefficient M-functions or M-files, without realizing that MATLAB is an interpreted language. Though MATLAB is suited for quickly checking how an algorithm works without getting down and dirty with detail, if you are finally carrying out research or doing a project, and need to call on a given algorithm a number of times, nothing beats C or FORTRAN in execution speed (I can personally vouch for this. This summer, I wrote this M-function for carrying out a particular kind of wavelet transform. The final code called this function 20000 times. The first version of my code used some in-built MATLAB routines, which took 15 minutes to execute 20000 times. Then, I wrote my own M-function, which took 60 seconds to execute 20000 times. When I finally recoded it as a compiled MEX-function, it took ~ 3 seconds to execute 20000 times!). Scientific computing is something where the point (b) makes a lot of difference.
And by the way, if your statement “the double-for loop for generating prime numbers in C got stuck in my head” refers to an implementation of the Sieve of Eratosthenes, it is a very efficient method that scales pretty well with N (where N is the largest natural number upto which you wish to compute all primes). I know that your pdf lecture is in a very preliminary stage, but I hope that you will add some more optimizations from the sieve method (for example, for checking if 27 is prime, if 2 doesnt divide 27, then neither will 4,6,8…26).
October 1st, 2009 at 10:01 am
Interesting approach. Don’t be so pessimistic about the way things are currently though. I’d like to point out that our PDS course in the first year was taken in a very similar vein. The instructor stressed that he was teaching us programming and not C. Although this wasn’t entirely true, it was largely followed.
Also, you’ve spelled “remainder” as “reminder” in a couple of places. You might want to correct that.
October 1st, 2009 at 5:54 pm
you’re definitely gonna have to take a judgment call over whether this is going to be an introductory course to theoretical or practical CS.. it’s currently rather fuzzily defined around exactly what aspects of theoretical CS it’s incorporating, and you’re committing to SE, so well a practical CS101 it appears to be… Which is cool, the way our insti (and like ALL indian unis and several american colleges) goes about it is purely using programming languages as a “vessel” so they can convey their concepts of algorithms and computational efficiency and abstraction. (at the same time, they’d inundate us with stupid questions in the exam about ++i^1 and stuff, so I really wonder what they’re trying to get at, but nvm all that)
Unless you’re teaching formal semantics of programming languages (like in your slides I’m guessing?), everything is translated into procedures, sets, boolean expressions, mathematical functions and datastructures aimed at designing for an imaginary input of ‘n’ elements where n has so-and-so properties or is astronomically large; or replicating numerical patterns and whatnots, so clearly here the programming language takes a back seat. In most cases, it won’t matter whether you got the job done in one line with a careful phrasing of the problem, or if you plainly wrote out a loop and tested each case, so long as the complexities match.
I guess, target learning outcomes you want out of students taking this course.. do you want them to be able to design and implement new seam-carving techniques (albeit with klunky yet functional code), or do you want them to start seeing code as art and maybe bump up the average quality of code in the industry? To the theoretical scientist, programming’s mostly just a tool to execute his vision, it’s probably not worth his while to marvel at the conciseness and elegance of his code (except when it comes to shaving an order of magnitude off his time complexity)
October 1st, 2009 at 6:34 pm
I cannot agree with your viewpoint.
One can go on to teach abstract concepts – but one can never be clear on them unless one does the programming part. And I don’t think it is a very pragmatic approach to allow the students to write a program in a programming language of their choice. Here are some questions that popped up in mind…
1. How does one evaluate the programs if there is no standardization?
2. Since it is an introductory course – do you think it is advisable to go for Computational Geometry and stuff?
3. Are you assuming that the student has exposure to programming languages before?
Good luck in designing the course!
October 1st, 2009 at 11:58 pm
[...] Designing a CS course. I like: http://artagnon.com/2009/09/designing-an-introductory-computer-science-course-part-1/ [...]
October 2nd, 2009 at 12:10 am
Like I told you before, something like this is going to need a radical shift in how we perceive the goals of education. Here we complain that India’s curriculum is too theoretical, and then we’re taking theory to the next level — abstraction.
This is going to put almost all the focus on the student’s thinking and creativity — making *them* do all the hard work. I don’t think this should be a first year curriculum.
October 4th, 2009 at 3:46 pm
@Vishaka: Thanks for your wonderful feedback! Here are responses to individual points you raised:
>> “if you were to compare two programs for solving a given problem…”
Hm. This is right as far as just numerical/scientific computing is concerned, but more generally, there are tons of other differences- for example actors versus message-passing object systems.
>> “Secondly, I think numeric/scientific computing must be taught as an independent module of the course, separate from software engineering”
Definitely. This is just the first lecture.
>> “nothing beats C or FORTRAN in execution speed”
Well, no. This is one massive misconception that many people seem to have. C and FORTRAN and very low-level languages where the user has to write out every single optimization as it’s getting compiled to assembly. Raw assembly would ofcourse be much faster; just that the user has to be that much smarter. Higher-level languages were so that users can focus more on the problem, and less about how it’ll compile to assembly. As compilers for these languages get smarter, it has been proven that they can optimize the code much better than humans. For example, I can ask Glasgow Haskell Compiler to optimize my compiled code to such an extent that, you’d have to end up reading a lot of x86 assembly and write long n’ dirty spaghetti C code to be able to match that. I’ll probably write a full-blown post on this sometime.
>> “refers to an implementation of the Sieve of Eratosthenes”
Well, no. Actually, I was referring to the naive implementation. And yes! I’m planning to prepare extensive lecture notes on just computer algorithms. That should cover optimizations. In the first lecture, I just want the student to be able to grasp the basic concepts.
@sidzoo: Thanks for the encouragement! Yes, there are some glaring inaccuracies- I made this out in a hurry. I’ll upload the latest revision (a complete rewrite) in a few hours.
@Maldy: Do I have to? After all, this is only an introductory course to computer science- it’s for the students to decide whether they want to do research or just become programmers. Getting the right mix can be very difficult, really.
>> “do you want them to start seeing code as art and maybe bump up the average quality of code in the industry?”
Very relevant. @Aditya has raised very similar concerns. What is the objective of the course? To put it abstractly, I want to teach students how to think and discover their interests in theoretical computer science/ programming. Even I for example, have discovered my love for theoretical computer science only recently. But you’re right, I have to have a concrete objective- this requires extensive discussion.
@Mainak: I’m not attempting to teach abstract concept _without_ a programming language. Just that I don’t want to tie it down to a single programming language or programming paradigm.
1. You’re right- I have to figure out some standard way of evaluating programs. If the evaluation requires a very talented professor, the adoption of the course will be very low.
2. I thought we could introduce the students to just the basics. Either way, I only cited “Computational Geometry” as an example.
3. Absolutely not (although the current revision seems to indicate otherwise). I’ll upload a complete rewrite of this course in a few hours- maybe your opinion will change then.
@Aditya: Yes, this requires extensive discussion. On IM later.
October 5th, 2009 at 1:08 am
I haven’t read the PDF yet, I’ll do so from work.
1. Teach programming, and not the programming language. Discuss abstract ideas in class, and ask students to write implementations in a language of their choice. Avoid building language-specific patterns (for example, the double-for loop for generating prime numbers in C got stuck in my head). Discuss various different implementations AFTER the students have tried it themselves.
I suggest asking the students to do the same basic exercise(s) in a bunch of different languages. This should be a simple exercise, such as printing the first 10 elements of a list, for instance. Using a list lets you introduce the concepts of a variable, a list, an array, and a linked list.
Then extend the same thing to n elements, allowing you to add functions into the mix.
3. Develop a hacker mindset- give students incomplete solutions written by other students and ask them to complete it.
How about giving the students some tests, and ask them to write code which passes those tests? Given input x, the output should be y. Given input of type T, output should be z, or an exception otherwise …
6. Prepare a reading list for software engineering, including articles on editing (introduction to specialized editors such as Vim and Emacs), debugging, versioning, testing, and profiling. It’s important to make students write large programs collaboratively in steps, so that they will be able to appreciate the importance of these tools.
I would suggest making the use of a text editor mandatory, without the use of graphical IDEs, even for languages like Java or C++. Students are NOT learning to use IDEs, they need to understand the abstract concepts. Programmers are heavy text users, and it’s best if they learn to use their tools well.
7. Prepare another reading list for theoretical computer science. Give them insights into the latest work in every field.
This is overwhelming, especially for a student. Instead of the newest stuff, how about making them read a bunch of classic papers instead?
8. Finally, it all boils down to grading. If you’re going to ask students to evaluate things like (i++) + (++i) in the exam, it’s clear that you’re expecting students to know programming language intricacies, and not programming methodology.
Just FWIW, if this was C, the correct answer to (i++) + ( ++i ) is undefined.
More later.
October 5th, 2009 at 1:13 am
http://blog.objectmentor.com/articles/2009/02/26/10-papers-every-programmer-should-read-at-least-twice for point 7.
October 5th, 2009 at 1:32 am
@Devdas: Thanks for the awesome feedback :)
>> “Using a list lets you introduce the concepts of a variable, a list, an array, and a linked list.”
I’ve taken a totally different (and arguably shocking) approach to this problem. You’ll see when you read the PDF.
>> How about giving the students some tests, and ask them to write code which passes those tests?
Excellent idea. Test-driven development is definitely a great addition to the course.
>> “I would suggest making the use of a text editor mandatory”
I didn’t mention it because I’ve seen how horribly wrong this can go- in our first year, we were made to use Emacs (I used ViM and nobody objected). Many students still haven’t learnt anything beyond copy-pasting in Emacs. I know for a fact that they’d be MUCH happier on an editor like Gedit now. Realization has to come from within- you can encourage, but I believe that forcing has certain ill effects.
>> “This is overwhelming, especially for a student. Instead of the newest stuff, how about making them read a bunch of classic papers instead?”
Right, my bad. I didn’t phrase that properly. I meant that we should give them a bunch of good classical papers, and peeks into the newest stuff. The purpose of this exercise is to get students excited so that they can work independently to eventually discover their research interests.
>> “(i++) + ( ++i ) is undefined”
Right. My point exactly. To be able to answer the question, the student should have read the C standard very carefully.