Home Teaching Publications CV GnuPG public key

Teaching / [FEB22012] Programmeren (2011)

This is the course page for Programmeren (Econometrics), academic year 2011-12, block 1.

Lecture notes and slides

The lecture notes are available for download /here/. The econometrics study association (Econometrisch Dispuut) has agreed to print them for you for a small fee less than what you would pay for printing them yourself. The prints should be done on 2011-09-08, so I recommend using the PDF until then and then buying a paper copy from them.

The lecture slides are here:

Exercises

Exercises will be posted here and in blackboard. The answers _must_ be submitted via blackboard. When submitting your answer, include all the matlab source files (the script- and function files with the .m extension) in a zip, and upload that through blackboard's exercise completion functionality. Note that although the Matlab environment is handy in testing individual lines of code by writing them directly in the command prompt, the solution you submit must consist solely of the source files (the ones of .m extension) that are executable independently.

I recommend getting used to the command prompt of matlab as it includes functionalities commonly available in text-based user environments (for example, browsing command history with up- and down arrows). Note that you can use the command prompt also for showing function documentation with command help (e.g. 'help fprintf'), and for finding function names with lookfor (e.g. 'lookfor print').

Exercises in pdf:

There are 10 exercises (first, third and fourth, and fifth weeks 2, second and sixth 1). Each exercise awards maximum 5% of the final grade, so the maximum possible to be achieved from the exercises is 50%. The other 50% comes from the written exam. The exercises are graded according to the following scheme:

Up to 4% from completing the exercise succesfully. Code that does not run awards _always_ 0% from the whole exercise - do not submit crap. If you manage to complete only part of the exercise, submit it and state clearly in comments which part you did and which not
1% for code clarity (functions, indenting, comments, variable names)

Exam

The exam will be a standard one with three essay questions. Note that you are _not_ allowed to bring with you any extra material to the exam: only a pen(cil), a sharpener, and an eraser are allowed. An example exam including sample answers can be found /here/.

Other material

Data files used in the exercises:

Additional learning material for pre-master students:

Book used in inleiding and voortgezet programmeren is C. Horstmann: Java Concepts, 6th ed., Wiley. Sections 1-6 and 12 compose the material required as pre-knowledge for this course.
Internet is full of tutorials to programming in all possible languages. For example, see Wikiversity.
Fun (at least IMHO) mathematical programming assignments can be found in the Project Euler. These are good learning material also for others than the pre-master students.

Errata

1. lecture: I showed an example of adding together '1' and 1, and told that the answer is 49. The correct answer is 50 ('1' = 0x31 = 49, and 49 + 1 = 50).
1. exercise: Beta should be a p by 1 vector and _not_ a n by 1 vector (there is a beta for each regressor and not for each respondent).
2. exercise: the "error" is not actually the error but it should converge to -777.
3. exercise: the random array in the example [2 3 4 1 6 5 7 9 2] has length 9, though it should be 10 (e.g. [2 3 4 1 6 5 7 9 2 3]).
4. exercise: you probably (?) cannot make Strassen's algorithm faster than the naive one. If you cannot, there's no need to plot the n_0.
6. exercise: question 2 (d) says "If \sigma_{i-1} - \sigma_{i} > -\epsilon", but this should be "If \sigma_{i-1} - \sigma_{i} < -\epsilon"
6. exercise: When applying the gravity model (question 1), \Delta_{ii} should always equal 0
7. exercise clarification: the components (sign, fraction, exponent) are all integers (or bit strings). For fraction, the value to be returned is the series of bits that are the multipliers (0 or 1) of the 2^-i's in the IEEE754 double precision (64-bit) floating point representation.
8. exercise: the last "endfor" of the pseudo-code should be "endwhile".
9. exercise: the deleteAfterNode should have signature deleteAfterNode(L, prevNode) for making it work with circular lists (when deleting the first node, you need set L.first to be the second node, i.e. the new first one).
9. exercise: the computational tests are said to be done for n \in {5,..,20}, k \in {1,...,5}, but for n=5,k=5 the results are a bit counterintuitive (as the algorithm starts by shooting the first, less than k=5 indices will survive). If you want, you can also make the computational tests for n \in {6,...,20}.
10. exercise: page 2, last paragraph says "It requires the starting Point head and the query point (i.e. root)". The root should be an example of a starting point, not of a query point (though it can be that as well).
10. exercise: Algorithm 1, line 9: the "-" should be "+" (median index + 1).
10. exercise: Algorithm 2, line 4: difference between head and q = q - head.
LN-TT-22012-1:

Sec.2.2: the insertion sort analysis should everywhere have line 9 instead of line 8 (line 8 has no computation in it). This also applies to the lecture slides of the second lecture.
P.8: the sparse matrix representation should be ([3, 4, 2], [5, 1, 1]).
P.11, 2nd paragraph from bottom: "memory memory" should be just "memory".
Derivation of the complexity of naive recursive matrix multiplication algorithm is not completely correct, though the asymptotic bound is the right one. The correct derivation will be presented at the lecture.
P.16, program listing of countSum: the method should have return type int (not void), and the array.length should be without '()'.
P.26: the array representation of the heap in Fig. 5.10 should be [9 7 5 6 4 1].
P.28, algorithm comment should be: % Returns node with the given key , or NaN if such does not exist.
Figure 5.9: the nodes with keys 5 and 1 are in incorrect order: 1 should be the left child of 4, and 5 the right one.
P.30, heapInsert: the first line should be i = length(H) + 1;
P.31: heapify should have H = heapify(...) assignment in the recursive call at the last if-branch. The &'s when comparing against endIndex should be &&.
P.33: "The term divide and conquer comes form" should be "from".
Figure 6.2: the caption should be "Iterations of heapSort on heap [7 4 6 3 2 1]".
P.40, best-case analysis of quicksort: the second line should be O(n log n).
P.41, analysis of the 9-to-10 partitioning of QS: the second and third lines should have "O" instead of "T".