Showing posts with label teaching. Show all posts
Showing posts with label teaching. Show all posts

31 October 2014

Dynamic Dispatch

In which I explain how to solve puzzle questions involving dynamic dispatch.

05 October 2014

Nitpicking Distance

I recently wrote down what I thought is a completely standard definition of distance on graphs. I was asked if I'm sure that the definition is well-behaved. Well … let's see.

13 September 2014

The Effect of Discouragement

How many books will one write? (Or blog posts, for that matter.)

11 September 2014

Beta Function

How to compute $\int_0^1 dp\, p^k(1-p)^{n-k}$ without symbol manipulation.

04 July 2014

The Education Funnel

About the difficulty of national tests, and pass rates.

03 October 2013

Nature and Computation

Physicists look for the simple rules of our world; computer scientists look for the possible worlds that come out of simple rules.

19 March 2010

Adding is in Nature’s definition

Below is one of the funniest and at the same time saddest course descriptions I ever saw.

As an undergrad, I took a course of Tudor Niculiu. I believe the course was supposed to be on OOP, but the lectures gave us some sort of introduction to philosophy. Luckily, there was no exam—we just had to write a small C++ program. Then we had to print the program (poor trees!) and go to an oral examination where the lecturer wanted to see, apparently, if we have any idea about how the program works.

A colleague once told me that "Niculiu used to be normal, but then he had an accident that affected his brain." If that's true, then it is quite sad. In any case, I have trouble understanding how someone who describes his course as follows is allowed to teach in what is supposed to be one of the best colleges in Romania.

Algorithms and Data Structures:

Adding is in Nature’s definition. However, the inverse operation, subtraction, needs negative numbers. We close mathematically the Nature to an integer that opens the physics for recognizing the limits of the Reason - electrons, in the meanwhile, attracting marvelous engineering solutions for different technologies. Electronics is among the most advanced engineering sciences; therefore, it has to be practiced by the most conscient human beings. Recurrent addition is multiplication, a most important parameter for the Nature. Mathematics closes the integers to the multiplication inverse, defining the rational numbers. These are not more than the naturals, but we can do many useful things with the Reason, from strategy to computer. So "what else do we need?" say too many, forgetting that the limits of the, so-called, pure Reason are caused by the fact that it bounds itself to close the Adaptability to discrete/ sequential operations. Thanks God, neither mathematicians, nor physicists accept all-happiness. They discover in three ways - order, algebra, analysis - which assisted all of them to think together, the power of continuum and that of the patience. In this context, “mathematicians and physicists” means the theorem, natural laws, or even new approach discoverers, and more, the engineers that understand the essential of mathematics and of physics.

To his credit, in the first part there's a glimmer of the (nice!) axiomatic way of defining numbers.

27 September 2009

There is no segfault: sort of an answer

[edit: updated link to dead cat]

My attempt at answering my own puzzle.

But first I should acknowledge that the title comes from the song There is no dead cat. Second, I should note that my presentation of what induction means is unnecessarily redundant: The base case is included in the induction step given that there is a smallest element. (And, yes, that’s my strange sense of humor.)

OK, now the challenge: Under which conditions can we conclude P(n) for all n∈ S given that ∧k≠ n P(k) implies P(n) for all n∈ S?

Read literally the question is not interesting: “Under which conditions p implies q?” has the obvious and useless answer “q, since p ∧ q implies q.” So, why is this an interesting question? Because we reduce the former to the later whenever P(n) has the form “the piece of code n is OK,” for some value of OK, one example being “does not dereference a null pointer.” Another reason that makes the question interesting to me is that I feel we are justified in looking at code one function at a time to assess whether it “goes wrong” but I don’t know it, because I never read or gave a coherent explanation: The matter is always treated as “obvious” as far as I can tell. Also, I formulated the problem in more general terms so that the answer has a chance of being useful in a different setting than program verification. Finally, I vaguely remembered reading that modular reasoning about a system is a form of coinduction: After reading a little about coinduction I’m not so sure anymore. (I looked at slides introducing coinduction in Coq by Yves Bertot and at blogs like n-category and a neighborhood of infinity. Reading through this tutorial is slow.)

The intuitive reason why we can analyze program pieces one at a time is that any counterexample is an execution that has one place where null is dereferenced. A bit more precise: An execution is a sequence of states. A state is a pointer to the next program statement to be executed plus the content of the memory (that is, a map from variables to values). The wrong state is special. The assumption ∧k ≠ n P(k) amounts to “ignore executions that go to the wrong state after executing a statement of a module k ≠ n.”

Problem. Can we use modular reasoning to put upper bounds (other than zero) on the number of errors that can occur in an execution? For example, is it possible even in principle to conclude that “this program may break its contract at most three times during its execution” without doing a global analysis? I suspect not.

Is there a useful way to generalize the answer with “executions”? Since I’ve been reading about model theory I’m inclined to view the program as a theory whose models are its executions. In this language the trick is that we can systematically explore parts of a model where a formula may not hold, assuming that in all other parts it does hold.

For the record, I’m not satisfied with my answer.

21 September 2009

There is no segfault

A short puzzle related to induction.

To prove that all elements of a set S have a property P we can use induction:

  • [induction step] we show that the elements of size s have the property P, assuming that all elements of size <s have it, and
  • [base case] we show that the smallest elements have the property P

For example, if S is the set of natural numbers and the size of a natural number is itself, then we can prove that 2Σk≤nk=n(n+1) by showing that:

  • [base case] 2Σk≤0k=0, and
  • [induction step] 2Σk<nk=n(n-1) ⇒ 2Σk≤nk=n(n+1)

As another example, if S is the set of (non-empty) binary trees in which each node either is a leaf or has exactly two children then we can show that the number of leafs is one more than the number of non-leafs by induction. In this case the size is the number of nodes in the tree. If we denote by l(t) the number of leafs in the tree t and by k(t) the number of non-leafs, then the statement we want to prove is l(t)-k(t)=1 for all trees t. Induction says that it suffices to show:

  • [base case] l(•)-k(•)=1, and
  • [induction step] (l(t1)-k(t1)=1 ∧ l(t2)-k(t2)=1) ⇒ l((t1,•,t2))-k((t1,•,t2))=1

You may want to take a moment to convince yourself (if you haven't already) that the base case and the induction step are fairly easy to check for both examples above.

But there is another type of induction! Suppose you have a program Q that is a set S of functions and you want to prove the following theorem: Program Q will not dereference a null pointer. One way to approach this task is to prove for each function that it will not dereference a null pointer ("throw NullPointerException" in Java, segfault in C, etc.) assuming that all the other functions in the program do not dereference a null pointer.

However, there is something troublesome about this. Until now we had an order: We think about the first proof by induction as first showing that an identity holds for n=0 then for n=1 then for n=2,... and whenever we get to proving for some value we rely on what was proven "before". But the last proof enjoys no such property: We can happily have a program made out of n functions, each calling all the n functions. Let's put it differently. Say we have four functions: a, b, c, and d. Is it possible for a, b, and c to be OK but d not? No, it isn't, because one of the proof obligations was to show that d is OK given that the others are. But... what's stopping c and d to be both not OK?

Still, I claim the proof is fine. Can you see why it works? What are the general conditions under which such proofs work?

16 March 2009

Summer School on Programming Languages

Here's a summer school that you'll enjoy if you care about programming languages. The location is in the middle of nature (and that's great). The food is quite tasty (at least by my standards). The density of smart people was overwhelmingly cool. In lectures I didn't get bored as I did in all UCD courses and I didn't fell asleep because I didn't understood one word as in most research talks. The density of information was just right: I could follow almost all that was said, but with great effort.

If you are still unconvinced, check out the list of speakers.

24 February 2009

Advice to beginner programmers

This is a slightly edited version of an email I sent to the students in my UNIX programming class. It's a class where they have to write many small C programs as homework to get points.

Dear students,

It is a good time, now that a quarter of the term has passed, to reflect upon your performance in this course (and others) and what you can do to improve. My advice is to focus on two things: attitude and work style.

Attitude

You should program for fun. If you're not having fun then you are doing something wrong. I'm not talking about the type of fun you have when you laugh at a friend's jokes. Don't expect your program to tickle either. It's a different type of fun, that lasts longer and is less spiky. Like other types of fun it ends with pleasure, the pleasure of seeing that your program solves a problem that seemed difficult. Perhaps. Or perhaps it seemed easy at first but then you realized because of the picky WebEval that there was more to do than you realized initially.

The point is: Program for the pleasure of finding things out and for the pleasure of seeing your program doing exactly what it is supposed to. The points will come.

Work style

Don't write random programs in the hope they will work. Submitting code that doesn't compile won't get you any points. Similarly, submitting the reference solution for problem A as a solution for problem B won't get you any points. These kind of practices are hopeless. Better go have a pint if you plan to keep doing it and save yourself some time. Or, better yet, try to listen to the advice I gave you and I repeat below.

Work environment. Start by setting up a work environment. It should at the very least allow you to easily compile, run, and test your program. If these three tasks are hard then you do not have a proper working environment.

Understand the problem. The most important step is to understand what it is that your program should do. Read the problem statement. Reread the problem statement. Reread the problem statement. And once more. Write (on paper) a few other possible inputs and check that you know without doubt what the output should be. If you don't understand the problem then ask. Don't say "I don't understand the problem" because the only answer you'll get is "reread the statement". Instead say "can x be negative?", "is this the correct output for this input?", "do we need to have some background knowledge on this Caesar guy to understand the problem", "is there a time limit?", "when you say that other characters should be ignored, do you mean that they can be interspersed anywhere between the characters that shouldn't be ignored?", and so on.

Find a solution. Once you know what you have to do (and only then) proceed to devise a solution. The easiest way to do so is to solve by hand a few cases and observe what you do. The 'solution' is a description of what you see yourself doing. The description has to be clear and unambiguous. Otherwise it's not an algorithm. Write it on paper as a recipe. If you can't then try harder. Don't just go to the next step because you'll just waste time. Look at other examples. Try to keep track on paper of everything that is going on in your head. Ask yourself what are the smaller steps. How did you know the answer is x? Never settle for "I just know".

Don't bite too much. You know what the problem is and you have your recipe written down? Then it's time to start programming. Your program must compile at all times. If the compiler reports an error, never fix it by randomly changing code in the vicinity of the error. Fixing the code without understanding what was wrong in the first place is worse than not fixing it at all: You missed an opportunity to learn. If you have a big pile of code with >10 errors then it's like trying to learn how to swim by asking someone to drop you off in the middle of the Atlantic. You won't learn to swim. Most likely you'll just die. So don't do it. Write your program incrementally. Keep it compiling. Run it from time to time and check that it does what you expect. This means that you should think about what you expect before running the program. Any mismatch between what you expected to happen and what happened is an opportunity to learn. Don't miss it. Try to understand what is happening.

Whenever you have an issue you can't explain it helps to try to reproduce it on the simplest example. If the issue is a compilation error, then make a copy of your program and then systematically trim down the code in a way that preserves the error. Do this until you get to the smallest possible program that still exhibits the error. That is, there's nothing more you can trim without making the error go away. By the time you get to this step you probably know what was wrong, you can fix the problem in the small example, test, and then repeat the fix in your big program. If the example is tiny and you still don't know what's wrong then ask in the forum (or a demonstrator if you are in the lab).

Tests. You should test your program as it grows by running it. Once it approaches what you think is close to a final solution your testing must become more thorough. Do not just run the program, type in the input, and look at the output on the screen. Write all your tests (inputs and outputs) in files so that you can retest easily after you change the program.

Cover all special cases you can think of with your tests. The "Encode Caesar" problem had shifts -1, 0, 1, 2 (always try these if they are valid input), 26 (because that's the size of the alphabet), 231-1 and -231 (the biggest and the smallest possible input). For each of them you should write the output by hand and see whether the program's output matches. The "Reverse" problem had empty lines, lines with one character, lines with two characters, lines with 500 characters, lines that contain only one character repeated many times, lines that contain palindromes, lines that contain only distinct characters.

Cover extreme cases. Special and small cases are there to check for correctness. You must also check that your program is not horribly slow. Let's put it this way: Will you finish the job of solving one of the biggest test-cases if you do it by hand before you die? If not, then your program is probably horribly slow. Since a computer can do simple operations about 109 times faster than you can and you will live around 100 years (hopefully more) any program that takes more than 3 seconds is horribly slow. To cover extreme cases you may want to download much data (like Gutenberg books for the Caesar problems) or you might want to write a different program, a test generator (for example, for Postfix Evaluator).

Bug finding and killing. What to do if the program does not do what you expect? First, do the easy thing: Run the compiler with all warnings turned on (-W -Wall -pedantic) and get check if any causes the problem. In any case, get rid of them. Then run your program with valgrind to make sure it's not the fault of nasal demons. If it is then try to isolate the problem in the same way as you isolate a compiler error: Trim down a copy of your program. Then time your program (time ./program < test.in > test.out) on a big test case. Try to limit its memory (see limit.c in the forum). It might be too slow or too obese.

If all this fails it's time for serious debugging. There are two basic debugging strategies: (1) read the program carefully and (2) trace your program for particular runs. The latter is easier but as you become more experienced you'll see that the former is much faster for simple bugs. Anyway, how do you trace a particular run of you program? Read the program having in mind a particular input. At each step think what are the values of the variables. If you feel lazy (and that's often a good thing when you are a programmer; we are after all in the business of automating stuff), then put printf statements that print the values of variables at intermediate points and check when their values diverge from what you expect. Another option is to use a tool like gdb that lets you go step by step thru the program.

Labs and textbook. Are the homeworks too hard? Then don't do them. Or rather, do them after you do the labs and you read the corresponding piece from the textbook. K&R is likely the greatest book ever to be published about a programming language. When it first appeared it was a complete revolution compared to the other language books. And a few decades later it still ranks among the best even though almost everybody tries to imitate the style nowadays. So, you have a great textbook: Use it. Read thru Chapter 1 and Chapter 2 and solve the exercises as you find them. They are the same exercises you should be doing in the labs. How to tackle an exercise? For all those that ask you to write code follow the approach outlined above.

Ask in the forum. I am yet to see a programming question in the forum. This would suggest that you have no problem tackling homeworks. Or you are extremely shy. Don't be. Or there's some other secret reason I can't imagine. If you tried to setup you work environment and you hit an issue, ask. If you tried to fix a compile error for 10 minutes, ask and attach the trimmed down version of the code that exhibits the error. If you have a bug reported by valgrind and you can't figure out what's wrong even after you trimmed down your code, then ask.

You ask "where do I get the input from?" and once you receive the answer "from standard input" you go "huh"? Then ask: "and how do I read from standard input?" I would have told you at least to lookup fgets, scanf, getchar. Then you might have asked "ok, now how do I send data to my program when I run it? do I have to type it at the keyboard every time?" And so on. There are so many questions you could have asked but didn't. Unless you ask, I can't read your mind and figure out what stumps you. Again, be specific, as in the examples in this paragraph.

Now read this again.

PS: If you notice a colleague that is looping forever due to the statement above then break them.

09 May 2008

Course feedback

The school organizes for feedback to be collected for every course. Today I got this back for the first course I taught:

Content
+Was the course satisfactory overall? 75%
++Was the course interesting? 89%
-Was there enough time to cover the material? 57%
Was the course well organized, with clear links between lectures?64%
-Was the level of difficulty suitable for you? 57%
++Was the recommended text suitable? 82%
Lecturer
-Was the lecturer's spoken delivery clear? 57%
+Were the visual aids helpful and appropriate? 75%
Was the supplemental material helpful? 68%
Was the material well paced? 68%
+Was the material presented in an interesting matter? 79%
++Did the lecturer inspire you? 86%
Practicals
--Was the feedback and help from demonstrators good? 43%
-Were there enough demonstrators to help the class? 50%
--Did computer facilities work well during the term? 50%
Was the connection between practicals and lectures clear?64%
+Did practicals help you understand course content? 79%
++Was there an appropriate amount of practical work on the course?82%
Other issues
Was someone available if you needed help? 61%
+Was the lecturer helpful in answering questions? 75%
-Were tests/exams fair and appropriate? 57%
+Did you learn a lot from this course? 79%
+Did you put a lot of effort into this course? 79%
Additional comments
a lot of content
best course of the year

The class had 28 students and 7 handed in feedback forms.

The numbers show that if I do this again I need to:

  • establish a tighter relation with the demonstrators
  • improve my spoken English
  • rethink the way the evaluation is done

I am surprised by the last issue: The evaluation was done almost entirely using an automated judge and I thought that the students liked it. Maybe they wanted more MCQs and less programming assignments. Or perhaps they wanted more partial credit for partial solutions.

13 February 2008

Memory allocation 101

A brief summary of my lectures on memory allocation. The students are in their second year and have little to no exposure to Linux and C programming.

An operating system is a program that (1) adds a layer of abstraction on top of the hardware, (2) manages hardware resources, and (3) solves some problems that otherwise would be quite repetitive and boring for programmers. These three different points of view describe the same thing. They are also rather abstract, with not enough technical “meat” to be remembered.

So let's look at one resource in particular, the memory. We shall discuss two different problems, generally referred to by the names memory allocation and virtual memory. (Granted, the latter sounds like the name of a solution, not of a problem.) Let us look at memory allocation.



RAM (random access memory) is one big array of bytes. Imagine that you write a program for a machine that does not have an operating system. Then you would have to think about where in this big array you would place each of your data structures, and you must be careful to keep them disjoint. When programming, people think in terms of data structures—“I need a queue for the requests,” “I'll model friendship with a graph,” “each person will be a graph node,” and so on. The program should correspond to how programmers think. They should be able to say “give me some space to hold one graph node,” if they precisely defined what they mean by `graph node'. They shouldn't be talking about addresses at all in order to accomplish such a simple task.

So that's the first problem: RAMs don't work the way programmers think. It's the operating system's job to make the memory look like it speaks a higher-level language.

The POSIX standard for operating systems says that a programmer should be able to say Node* n = malloc(sizeof(Node)) to get space for holding a Node, and that later on he must say free(n) if that space is to be made available for other stuff. That's pretty good. (Better is possible. Programmers generally don't think about releasing memory so they should not be forced to say free(n). Unfortunately, no widely-used operating system is able to detect when the programmer needs a data structure no more.)

(1) Saying “give me memory to hold a node” is more abstract than keeping track of specific memory addresses. (2) To let programmers use the more abstract language, the operating system must organize (manage) the memory. (3) The problem of keeping track which space is free and which is in use is solved once in the operating system, instead of once in each application.

Now that we know the problem, how do we solve it? As with any problem, it helps to make details explicit. We have at our disposal a big array and there is a sequence of requests to allocate or deallocate memory that we must honor. A request x=allocate(N) means “please tell me where in memory it is safe for me to store N bytes.” A request free(x) means “OK, I'm done with that memory you told me that is safe to use a while ago.” Obviously, if the operating system answers the same for two consecutive allocation requests, havoc will reign—applications would try to use the same space for distinct data structures. So the operating system must keep track of which areas are free and which areas are in use. When someone asks for N bytes we deliver those from a free area and then mark the N bytes as being a used area. When someone says that an area is no longer needed we mark it as free.

We see now two subproblems: (a) How do we keep track of what is free and what is in use? and (b) How do we choose which free area to allocate? In other words we must choose the data structures and the algorithm. Before we do, let's stop and think what we want to achieve—what makes a solution `good'? One thing that comes to mind is speed. We expect allocation requests to be somewhat frequent since all programs need some sort of data structures. It would be bad if a call to malloc takes forever. Another, more important issue, is that we want to not waste memory. It's easy to see how that might happen. If we have lots of free areas but all of them are just slightly smaller than N then we can't honor an allocation request although plenty of memory is available. Intuitively, a free area should either be very small (so it doesn't waste too much space) or big enough to honor allocation requests. So that's the main objective: not to waste memory. We say that we want to keep fragmentation low.

We discussed two data structures for keeping track of the free space. The simplest is to chain the free areas in a linked list. It is common to force such lists to obey the following invariants:

  • p<p→next or p→next=Λ
  • p + p→size ≠ p→next

Here p is a pointer to a free block, and Λ is a special address called `null'. The first invariant says that blocks are chained in increasing order of their addresses; the second invariant adds that there are no adjacent free blocks. Each free block has two fields, next and size; each used block has one field, size. To make things easier later we use a sentinel, a dummy free block of minimal size that starts at address 0 and that is never allocated. In the figure below, green means free, red means in use, and yellow is the sentinel. (In the figure p→next is written as next(p). You should be familiar with both notations.)


Figure 1: Linked list of free blocks

Allocation is done as in figure 2. The pseudocode implements the first-fit policy: Always pick the free block at the smallest address. This policy is one way to implement the following strategy: “Do not let long lived small used blocks prevent the allocation of bigger blocks.” Why? Because under this scheme small blocks will cluster at small addresses. Before continuing, please take a moment to read and re-read the pseudocode until it sinks in.


First-Fit-Alloc(N)
 p:=FIRST
 WHILE p->next != NULL and p->next->size < N+1
   DO p:=p->next
 IF p->next=NULL THEN SIGNAL OVERFLOW
 r:=p->next+1  /* skip the size */
 e:=p->next->size-(N+1)
 IF e<2
   THEN p->next:=p->next->next
   ELSE
     q:=p->next+N+1
     q->next:=p->next->next
     q->size:=e
     p->next->size:=N+1
     p->next:=q
 RETURN r

Figure 2: First-fit allocation

Deallocation is done as in figure 3.


Ordered-Address-Dealloc(q)
 q:=q-1 /* go back to the size */
 p:=FIRST
 WHILE p->next != NULL and p->next < q
   DO p:=p->next
 Glue(q,p->next)
 Glue(p,q)

Glue(p,q)
 IF p+p->size=q 
   THEN p->size:=p+q->size
        p->next:=q->next
   ELSE p->next:=q

Figure 3: Deallocation

Here are a few exercises before you continue.

Exercise 1. Can the two calls to Glue be reversed?

Exercise 2. What modifications would you make to the first-fit allocation pseudocode in order to implement the best-fit policy? The best-fit policy says that you should choose the smallest free block that is big enough.

Exercise 3. Modify the deallocation procedure so that it works in constant time. Hint: use extra bookkeeping information.

Exercise 4. Suppose the memory has 10 words and the following requests are made: A=allocate(3); B=allocate(4); C=allocate(2); deallocate(B); D=allocate(1). What is the size of the biggest available block if first-fit was used? Best-fit? How much space is lost to internal fragmentation if the buddy system is used? (Ignore any space taken by bookkeeping information.)

Finally, another way of keeping track of the free blocks is to have a few lists, one for each size. This way we'll search through a smaller set when trying to find a block that is big enough. Because there are many possible block sizes we'll restrict our attention to those that are power-of-two. So if we have 2n words in memory we would have an array of n+1 linked lists, for sizes 20,21,⋯,2n. This scheme is called the buddy system. It involves maintaining the following invariant:

  • p→size=2k, for some k
  • pmod(p→size) = 0

Whenever two adjacent blocks can be glued while maintaining the above invariants they are glued.

Exercise 5. Write down the pseudocode for allocation and deallocation under the buddy system.

Exercise 6. Why did you use doubly-linked lists in the answer to the previous exercise?

In the buddy system sometimes we allocate blocks bigger that we need. For example, instead of allocating 13 words we would allocate 16. This wasted space is called internal fragmentation; the space wasted because the holes are too small is called external fragmentation. How much internal fragmentation do we expect to have in a system that only allocates blocks with size power-of-two? Let's define fragmentation as being f=U/N−1, where U is how much space is used and N is how much it is needed. Let's make the following assumptions:

  • we allocate blocks with sizes 1,2,3,⋯,2n, with no preference for any of the sizes
  • there is no external fragmentation; that is, if w words are requested then 2⌈lgw⌉ are allocated
  • 2n is large

Under these assumptions we have:

N=1+2+⋯+2n=2n(2n+1)/2≈22n−1
U=1+20×21+⋯+2n−1×2n≈22n+1/3
f≈1/3

Exercise 7. Fill in the holes in the previous derivation.

It's time to summarize. The operating system offers programmers an interface to memory that matches the way programmers think. In order to do so it has to keep track of used and unused memory and make placement decisions that minimize wasted space. It also has to make those decisions fast. We reviewed briefly three possible mechanisms for doing so. None of them is very good. In practice there are lots of tricks used to lower fragmentation and to increase speed, but no fundamentally different approach is known.



Further reading. You should read at least the introduction of Wilson, Johnstone, Neely, Boles, Dynamic Storage Allocation: A Survey and Critical Review because it is a very good exposition of the high-level problem. (Also, you might want to check out Knuth, Fundamental Algorithms, which inspired much of this material.)

The next episode is about virtual memory. Stay tuned.

09 February 2008

Operating Systems course, again

I decided to make public the materials I am using for the operating systems course.

You might ask "what's there to decide?" I tend to have in each lecture about three core slides and I spend 10 minutes explaining each. So a lot of material is not included. In fact, most of what I teach is not included. So I was worried that it might be misinterpreted. I got over it.

30 January 2008

WebEval

As you might now I am now teaching a course on operating systems. This is an optional course, so the School does not impose any constraint on the content. For fairly administrative reasons (meaning "I don't want to talk about it, at least not now") the title remained Operating Systems as it was last year. I decided to structure the course around four important concepts: memory management, file systems, multitasking, and networking (no proper link for the last one: try this and this). Each of these will have four lectures allocated. The course started with two introductory lectures that presented the Linux command line. The assessment system also changed a bit from my last post (again, don't ask). The final exam is worth 20 points; a written report is worth 10 points; finally, 70 points are earned throughout the term by solving assignments that are judged automatically. The harder assignments are labeled projects and students are explicitly asked to collaborate on finding good ideas for the solution (but not on writing the program).

In this post I'll tell you a little about this automatic judge.

I want to be able to give two types of assignments: quizzes and programs. For quizzes it is obvious that judging can be automated: one just has to compare the student's choices with the correct answers. For programs it's not clear how to do the judging. People involved in programming competitions probably already yell inside: "just specify the input/output format (or some similar interface) and use a bunch of tests, comparing the actual output with some reference output." And that's what I did. But I want to point out that this is by no means the only way to judge a program. It just happens to be a good one. Other ways include using theorem provers to see if a program matches a specification, running style checkers, counting various metrics, making the programs compete with each other, and so on. The specific way one chooses to do the automatic judging influences the type of tasks you can pose. One big advantage of the I/O testing idea is that it allows many tasks to be posed in a form amenable to such judging. The other big competitor is the direct competition between programs. I'll let you bash using metrics such as cyclomatic complexity and style checkers for giving scores. Once this system is chosen I had to decide whether I want the IOI scoring or the TopCoder one. I decided to go for the former, which is more lenient: If you pass half of the tests you get half of the points. TopCoder gives you exactly zero points even if only one test fails.

I want the automatic judge to keep track of the scores and I want it to be easily maintainable. That is, I want to do as little work as possible in order to add a quiz or a problem, I don't want to do any work to take a problem down after the deadline, and so on. Basically, I'm lazy. But I care for the students too. I don't want to ask them to install anything or follow some conventions they don't like unless absolutely necessary. So it's decided: it has to be a website running in a browser.

In short: require no software on the client side apart from a browser, judge quizzes automatically, judge programs automatically by running them on the server, keep the scores, make it easy to add/remove quizzes/problems.

Here's how it looks (click to enlarge, and see the available languages ):

It's made out of

  • A client. It renders stuff in the browser area. It does as much as possible without bothering the server. For example, it updates the deadline counter every minute even if it asked the server for a time interval only once, immediately after login.
  • A server. This one distributes work to two modules (classes, actually).
    • Judge. Responsible for compiling, running program, and comparing their output with the reference result.
    • Database. Provides a way to fetch data about problem statements, quizzes questions, accounts, and so on. It also allows storing and reading scores. This is an interface. The work is done by the class FileDatabase, whose name suggests what database technology I use :).

My approach was: get it done quickly. So the following signatures will probably look messy to you. They are here for you to criticize. Here's the interface between client and server (only the client calls into the server).

package org.rgrig.client;

import com.google.gwt.user.client.rpc.*;

/**
 * The interface between the client and the server.
 *
 * The client can ask for quizzes/problems, can ask for the available
 * languages, can log in and out, can ask for a quiz/problem to 
 * be judged, and can ask for the current scores.
 */
public interface WebEvalSrv extends RemoteService {
  /* Ask for (active) problems and quizzes. */
  public Problem[] getProblems() throws ServerException;
  public Quiz[] getQuizzes() throws  ServerException;

  /* Returns the list of available languages. */
  public String[] getLanguages() throws ServerException;

  /* Functions for logging in and out. */
  public String login(String pseudonym, String passwd) throws ServerException;
  public void logout() throws ServerException;

  /* Judging functions. */
  public PbEval judgeProblem(
    String problem,
    String language, 
    String solution) throws ServerException;
  public double judgeQuiz(
    String quiz,
    String solution)
    throws ServerException;

  /* Returns the user scores now. */
  public User[] getScores() throws ServerException;
}

And here's what the database can do.

package org.rgrig.server;

import java.util.*;
import org.rgrig.client.*;

/**
 * Knows how to parse the database info.
 */
public interface Database {
  public Quiz[] getQuizzes() throws ServerException;
  public Problem[] getProblems() throws ServerException;
  public String getQuizAnswer(String quizId) throws ServerException;
  public PbTest[] getProblemExamples(String pbId) throws ServerException;
  public PbTest[] getProblemTests(String pbId) throws ServerException;
  public PbLimit getProblemLimits(String pbId) throws ServerException;

  public String[] getLanguages() throws ServerException;
  public Language getLanguage(String id) throws ServerException;

  public double getScore(String task) 
    throws ServerException;
  public double getScore(String pseudo, String task)
    throws ServerException;
  public User[] getScores()
    throws ServerException;
  public void setScore(String pseudo, String task, double score)
    throws ServerException;

  /** Returns the student ID, or null if the check fails. */
  public String checkLogin(String pseudonym, String passwdHash) 
    throws ServerException;
}

And now the part I'm most excited about. If I want to create a quiz that looks like this

then I have to create a directory with two text files. One contains the questions.

How does one send the output of <tt>cmdA</tt> to the input of
<tt>cmdB<tt>?
 - <tt>cmdA | xargs cmdB</tt>
 - <tt>cmdA | cmdB</tt>
 - <tt>cmdA > cmdB</tt>
 - <tt>cmdA > xargs cmdB</tt>

(Except that the good answer has * instead of -. This quiz is still live so I won't post the good answer right here right now.) The second file looks like this:

start 2008-01-28 11:00
deadline 2008-02-04 11:00
score 1
name Command line basics

And that's it! The problem will appear on the website in between the start date and the deadline, it will be worth 1 point, and the name that appears on the website will be Command line basics.

Creating a problem is just a little more difficult. One has to create two directories with tests (examples and tests). These contain pairs of files test_name.in and test_name.out. The in file is fed to the program and the output is compared with the out file. Examples are different in that they are rendered in the problem statement, the student can see his/her program's output on the examples, and the answer must be correct for examples in order to get any points. Once the program gets the examples right it is run on the real tests and the score is proportional with the number of tests for which the answer is correct.

To develop this stuff I used GWT. The ugly part was that the "hosted mode", which is supposed to help with debugging, didn't really work for me. So I had to restart the web server on my computer often. (I suppose I could have insisted to see why RootPanel.get() return null (only) in hosted mode, but, to my shame, I was not curious enough, and just wanted to get it done quickly). On the good side the RPC is quite easy (and no, I don't too much mind having to write closures to process the returned values). Another good part is that I'm quite happy with how the site looks and so far I had no problems with browser incompatibilities.

While I was developing I was thinking often about what should be on the server and what should be on the client, including for non-security sensitive stuff. I vaguely remember that Links lets you ignore this issue if you choose so. In other words, in Links RPC's are really simple. Now, that's just a vague memory. I hope I'll have time at some point to experiment with it.

In the meantime, would you use such a website for your course?

26 November 2007

nwerc 2007 and a laundry list

During the week-end that started on 17th of November I attended NWERC 2007 as a coach for the University College Dublin team O'Team: Rashid Bhamjee, Eugene Kenny, and Kirill Ignatiev.

Before the story, here's the blurb I sent to the students about this contest, in case you are not familiar with it.

The ACM ICPC is the oldest (1977) and one of the most prestigious algorithmic programing contests for college students. Approximately 1750 universities participate each year. This year's UCD team is: Eugene Kenny, Rashid Bhamjee, Kirill Ignatiev, and coach Radu Grigore. To the best of our knowledge this is the first time Ireland is represented!

The contest has two phases: regionals and the world finals. NWERC is the North-West European region, which includes Belgium, Denmark, Finland, Great Britain, Sweden, Ireland, Iceland, Luxembourg, The Netherlands, Norway, and West Germany.

The main sponsor of the event is IBM. On Saturday, contestants will go on a city tour (Utrecht), will attend a talk describing the Google File System, and will have a Google dinner. The complete program is available online.

On Friday evening we landed in Eindhoven, took a taxi to the train station, a train to Utrecht, and a bus to the University of Utrecht. We arrived 20 minutes before the registration closed. In fact, while I was solving e "Google brainteaser" I was told that the security guy wants to go home so I should turn off the computer. I got two questions wrong as far as I can tell, and there weren't many.

There I met Mihn Dihn, a.k.a. Minny. and he introduced me to other topcoders: starfrog, hungson175 (a.k.a. "The Healer"), jthread, Johan.de.Ruiter, and a few others. Mihn and Son invited us to play pool. Eventually Kirill and I decided not to go. Eugene and Rashid went to town until around 2am, then they tried to solve Rubik's cube and chatted for a couple of hours. At 7am we woke up because Saturday was a busy day. In the morning we attended a talk of ASML. These guys supply lots of the equipment used during the litography phase of building integrated circuits. The presentation was good. Although I don't like analogies to much you have to love this one: To get an idea of the scale we are working on I should tell you that we can print the map of Netherlads in 30 seconds, where each pixel represents an area the size of this microphone I'm speaking into. Then it went on to illustrate other challenges faced by programmers. These fall in two categories:

  1. Software has to deal with everything that goes wrong in the other departaments.
  2. The time needed to develop each new generation of the product grows exponentially and this can't continue.

Here is an example of a problem in the first category: If a laser beam goes thru a lens it gets hot and its optic properties change with temperature. These changes must be predicted (there is simply not enough time to measure) and adjustments done in real time, such as applying mechanical torque on the lens. As for the second problem, they think that the root cause is that the program is written in C. So the solution is to use higher level languages. In particular, they are collaborating with people in academia on automatically refactoring the existent codebase into something that unweaves aspects. Their vocabulary didn't even mention the words "high-level language" in fact, only "aspects". I'm yet unconvinced by the magical power of aspects to reduce interactions between pieces of code that are concerned with different things. But using MATLAB instead of C for numerical calculations sounds like a good idea, and I understand that error-recovery should be implemented in both MATLAB and C and it's not clear how to do it, hence you can label it as research in aspect oriented programming.

After that they presented the system used for judging and we had a test session. The problems were very easy, as expected. Here is an example: It is hard to solve integer equations algebraically and sometimes it's better to try a numeric solution. Consider the equation xp+yp=zp. You must write a program that is given a nonnegative value p, less than 109. If there is a solution with 0<x,y,z<10100 then you should print such a solution; otherwise print "none".

Next comes the Utrecht walk, with a guide. I never had a guided tour of… anything. It was nice. They have a big church in the middle that was partly destroyed by a tornado. In fact, they have lots of churches and they also have something against churches. At least the guide did. They also have modern architecture, such as some university buildings, the mayor's house, and a strange tall metal house built on an 3 by 5 meters area at the corner of a street.

We then got back after having lunch (the sandwiches that Optiver provided were not enough for us. There we had a Google talk about the Google File System. The talk was quite entertaining but with not enough technical meat for my taste. If you read the paper you'll know basically all that we've been told (except the promises that our gmail is safely copied on many computers that Google engineers can access — that is, without the funny parts).

During the evening we played Mafia. I was killed during the second half of the game but I'm happy because I was able to take one of the mobsters with me while I was still a ghost. Before this we took a picture with lots of TopCoders (I believe that grotmol was the highest rated of us.) The picture is blurry, but I'll post it here once I manage to come to school once without forgetting the camera home. (It's harder than it sounds!)

At half past ten the honest citizens triumphed and we went to sleep.

Sunday was the fun day. I was quite nervous, maybe even more than my team. Anyway, they had this nice surprise for the coaches that they gave us computers and the ability to compete realtime. After I solved the easy problem I spent some time thinking about problem G (something with summits and a height map) and failed to solve it. There were at least three easy problems that could be solved: assemble, containers, and towerparking. O'Team only solved towerparking, beating five teams on time. That is an OK result for the first participation. My mistake: I focused too much on solving problems and not enough on their coding skills and on an emphasis on writing correct solutions.

Immediately after the end of the contest we had to hurry back to Eindhoven to catch a plane. I'll ask the three members of O'Team 2007 to guest blog with their thoughts about the contest.

In other news Mikolas, I, and Michal (sorry for the accents guys) got invited to submit a paper about reachability analysis for annotated code to a journal on software engineering. Here are some things we did or we plan to do for that paper:

  • implement it in Boogie which is good for debugging the axioms of VerifiedC (Michal took care of this since he is now at Microsoft Research),
  • implement it in Freeboogie (I'll do this),
  • a better analysis of the algorithm used (see my previous posts that already hint at interesting links with standard problems such as building optimal alphabetic binary trees),
  • make the ESC/Java implementation handle body-less methods (this was the number one request after the presentation at SAVCBS; we want to try at least three ways of doing it, one of which makes a cute use of counterexamples provided by the theorem prover Simplify),
  • a better case study (we said in a few places that "we don't quite know what went wrong"), and
  • better error reporting (give error traces a la Rustan, and guess categories of problems, such as "loop unrolling").

02 October 2007

Car drivers versus computer scientists

Worse, today's national curriculum teaches pupils to use computers but not to understand them. It's training, rather than education. As Mr Rodd's BCS colleague David Evans puts it, it's as if we thought that "educating a nation of car drivers will create an automotive engineering industry."

telegraph.co.uk

19 August 2007

UCD CSIC 2007

On 11th of August we had the 2007 edition of the CSI programming competition. I decided the theme to be Harry Potter. The problems and the reference solutions are available online. We also have pictures. As you can guess from the balloons it was an ACM ICPC style contest. We (at least me and Joe) plan to send a team to the regionals to represent University College Dublin (and Ireland).

In this post I'll say a few things about the problems. I recommend you spend some time thinking about them before reading on.

Problem A was taken straight from the Harry Potter book. The trick is to not start coding until you think it through. Most contestants actually transformed the rules into code. Experienced programmers know that that is a sin. Those kind of rules must be encoded as data, otherwise it is a nightmare to get it right, or to adapt to changes in the rules.

Problem B tests coding skill. Here Java has a huge disadvantage because the standard IO routines are extremely slow compared to the standard IO routines of C. Complaining about this is pointless. First, fast IO can be done in Java at the price of writing C-style code. Second, no one stops you to use C. That aside, my C solution works in a little over 0.3 seconds on the test data (on my computer) so the 60 seconds limit should be enough even for Java, provided that the implementation has the correct complexity. What is the correct complexity? When you are trying to see if the word at index 0 is the start of an evil almost-anagram you look at the words 0, .., n such that they have at least 11 letters. The first important observation is that there is no need to look at 0, ..., n+1. The second important observation is that, when you look at word 1, you can start with 1, ..., n, because 1, ..., n-1 is guaranteed not to have enough letters. Hence, the solution should be O(M+N), where M is the size of the input and N is the size of the reference string, not O(MN).

Problem C is easy for anyone with experience in algorithm contests and hard for others. The solution is a simple BFS.

Problem D is by far the most interesting one. It is more or less taken directly out of an article by Kleinberg, Papadimitriou, and Raghavan on Segmentation Problems. They give a theorem that says that the problem has a O(C3) solution using dynamic programming based on the observation that optimal groups are made of clients that have consecutive optimal prices. They omit the "obvious" proof. I have no idea what solution they have in mind, for mine is O(C2). Since the winnings are (a−b x)x the optimal price is a/(2b) and the maximum winnings are a2/(4b). These formulas hold for individual clients but also for groups of clients, with a and b being sums in the latter case. One approach is to try all possible ways of grouping clients and the use these formulas to get the optimal price and profit for each group. This is too slow. Suppose now that we know the optimal group prices and we try to figure out the groups. Because the winnings are given by a function symmetric around the maximum we should sell to each client using the group price closest to its individual optimal price. This shows that the optimal groups are indeed made out of consecutive clients, when sorted by their individual optimal prices.

27 July 2007

UNIX programming course

On 21 January 2008 the second term of the academic year 2007/2008 will begin in UCD. Normally I don't notice such dates but now it is a bit special because that's when the first course I'll teach starts. Joe will still be the coordinator as far as the university administration is concerned but I'll be responsible for organizing, planning the content, giving the lectures, and so on. The course is entitled UNIX programming (COMP20060, formerly known as Operating Systems). I will follow the main lines of Joe's curriculum last year. Here's what I'll cover, in various degrees.

  1. Introduction to C.
  2. The Open Group Base Specifications, the open version of POSIX.
  3. Core concepts: multitasking, virtual memory, files.

The course is optional, approximatively 30 students attend it, and they are familiar with Java. My emphasis will be on giving them hands-on experience with the C language. The textbooks are:

  1. The C Programming Language, by Kernighan and Ritchie
  2. The Practice of Programming, by Kernighan and Pike

The grading is done as follows:

  • 40% for the final exam
  • 10% for weekly in-class quizzes (that anyone attending the previous lecture should have no difficulty with)
  • 20% for a project to be done in a team of two; it will be a command line tool of some sort
  • 30% for weekly assignments

The weekly assignments will be judged in a completely objective way. Grading will be done by a computer program and students will know beforehand exactly how that computer program works. Also, students will submit solutions electronically, as many times as they want before the deadline, they will get immediate feedback, and only their best solution will be used for the final grade (with no penalty for multiple submissions or for submitting bad solutions). Nevertheless, the deadline shall be strict. When the deadline expires submissions will be automatically disabled and a sample solution will appear on the website.

When they finish the course, I'd like the students to:

  1. feel comfortable using command line in Linux,
  2. feel comfortable reading C code written by someone else, and
  3. know the main functions of an operating system and its high level architecture.

The advice of the head of school was less content, higher quality. The next steps for me are to:

  1. determine more precisely what content I will cover, and
  2. code the infrastructure for judging assignments.

Any feedback is welcome, especially from UCD students that might take this course.

22 June 2007

Programming Assignments

Michael Mitzenmacher started his blog, My Biased Coin, with a series of posts entitled Cuckoo Hashing, Theory and Practice. His last post is about teaching and so it is less informative and more likely to generate noise such as this post. David Eppstein has some thoughts on the matter on his own blog.

So what is the matter? Universities should do a better job connecting theory to practice.

I guess most people would agree with the above. For different reasons. Some will say that universities should produce programmers for the software industry and instead they produce people that hate mathematics and don't know how to program. Universities should just teach students how to program using the modern technologies developed in the industry. These are industry people (mostly managers). Some will say that students that go to CS departments know how to program and generally like computers, but the theory courses fail to make a connection. This is Prof. Mitzenmacher (and some others who teach theory, I suspect). Some will argue that blending theory and practice just makes one's days more fun. This would be Prof. Knuth. No matter what the reason is, I believe there is strong agreement that universities should do a better job in connecting theory to practice and vice-versa. (Of course, university really means CS departament, or, perhaps, we can include math.)

So how should we do it?

Mitzenmacher proposes programming assignments. Eppstein proposes using a real programming language (Python) for writing pseudocode. Mihai (Pătraşcu?) proposes less rigor and a problem-oriented approach. Cristopher Moore proposes having a project that uses a few algorithms (as opposed to many assignments that cover each only one algorithm). Almost all want better textbooks.

Last semester I was a demonstrator for part 2 of a Data Structures and Algorithms course at UCD taught by Simon Dobson. He already had weekly programming assignments. I was somehow unhappy that for part 1 most students submitted huge pieces of code that did not even compile. I felt this is just unacceptable. You can't really enjoy programming if you are just typing stuff without compiling and experimenting. So I developed an evaluation website and adjusted the problems by completely specifying the input/output format. The idea was that students would have to submit something that works. But we ended up giving points for compiling and for working on small tests because, for each assignment, only about five out of one hundred students were able to solve it. I thought the assignments are too hard but Simon disagreed. Overall, I think this was a good experience. My opinion is that the biggest improvement we can do to this course for the next year is to enforce a strict policy in the lab: Only people working on the assignment are allowed. By the end of the last semester virtually all students spent their time browsing the internet, especially on `social' websites. But I digress.

All courses should be fun! Alas, what is fun for one student is not fun for another. Moreover, asking students what is fun doesn't work. They tend to have a wrong idea about it while they are in college (no homeworks, more trips to the nearby pubs, more jokes in the classroom, no Greek letter, no grades, and so on). Probably the best we can do is to ask students their opinions after the course and after graduation. The next best we can do is to tell our own stories and collect them.

The reason I liked programming was that in BASIC I was able to easily draw — much better than I could by hand. I was six and my hand was shaky. On the other hand the circles and the lines on the screen were perfect. Sure, I needed to figure out how the numbers I plug in affect what is drawn, but that was nice — it felt like magic! The reason I liked algorithms was that I tried to solve a problem for one week (shortest path in a graph) and failed. In the process I come up with a backtracking implementation that worked for 20 nodes but all other things I tried failed. I was convinced that it is impossible to deal with graphs that have 40 nodes. I still remember the feeling of awe I had while reading a description of Dijkstra's algorithm from Tannenbaum's Computer Networks book. I went straight to the keyboard and implemented it because I needed to see it. Oh, I forgot to mention that this was actually a real problem that my father had at work and I didn't really know that that data is a adjacency matrix of a graph and that what I am looking for is called shortest path.

Because of my experience I think that problems are good. Give students a small problem that they can handle, to build confidence. Then increase the size of the input and let them try hard. Then show them a solution. Make sure they feel that the solution is within their grasp and they would have `got it' if only they were a bit lucky or more thorough. Except that, well, I don't think this would work in a classroom scenario. It is likely that most students won't solve the `hard' part and the smart ones would use advanced development tools to find a recipe on the Internet before they really try. And really trying is what makes you really appreciate a solution. This is why the usual style of presenting theorems before proofs is good. It gives people a chance to try to find the proofs themselves. Any ideas on how to make this approach usable in classroom?

Now about textbooks. Many complain that CLRS is too theoretical. I thought it was quite entertaining and well written. And it made me write more programs than I would have otherwise. There is a caveat. I didn't use it for a course. (I didn't take any course in algorithms since I studied EE. Well, signal processing algorithms are algorithms, but you get the point.) I bought it after my adventure with Dijkstra's algorithm but somehow kept it on the shelf. I started reading after some guys looked at me in a strange way after I asked them what is Dynamic Programming. While I was solving the exercises I always wrote a program. I actually thought that's implied and there is no way someone would consider only a paper sketch to be a solution.

And finally, about using a real programming language instead of pseudocode. Oh, yes, yes! I like it. That description should come accompanied by a second alternative description, probably in English. I think that not only textbooks and lecturers should use a real programming language instead of pseudocode but even papers! I guess that twenty years ago it wasn't feasible to do so but now there are plenty of programming languages that are about as easy to read as pseudocode. Using a real language makes the presentation more precise. Sometimes no real programming language would look as nice as pseudocode and in those situations I think it is perfectly acceptable to omit some obvious optimizations and special cases that arise from implementation issues. (For example, in Nemerle hashtables that map something to integers insist that you should insert the key before incrementing the value, which makes them less convenient than C++ maps for counting things.)