INFO0902 - Data structures and algorithms

Informations

Schedule

Ex. 6 Feb. 2015 Exercise session 1: Pseudo-code and recursion
Tutorial 13 Feb. 2015 Tutorial: Let's C
Ex. 20 Feb. 2015 Exercise session 2: Analysis tools (first part)
Project Ex. 27 Feb. 2015

Statement for project 1
Code

Exercise session 2: Analysis tools (second part)

FAQ 6 Mar. 2015 FAQ on the first project
Ex. 13 Mar. 2015

Exercise session 3: Stacks, Queues, Lists, Vectors and Sequences

Exercise session 4: Heaps, Priority queues and Trees

Project Ex. 20 Mar. 2015

Statement for project 2
Code
Presentation for project 2

End of exercise session 4
Exercise session 5: Dictionaries

Deadline 23 Mar. 2015, 23h59 Don't forget to submit your result for the first project on the submission platform
FAQ 27 Mar. 2015 FAQ on the second project
Ex. 3 Apr. 2015

End of exercise session 5
Exercise session 6: Data structures and Dictionaries

Ex. 15 Apr. 2015, 9:30 am Exercise session 7: Problem solving (brute force and divide-and-conquer)
Ex. 17 Apr. 2015 Exercise session 8: Problem solving (dynamic programming and greedy algorithms)
Supplementary exercises on dynamic programming and greedy algorithms
Deadline 22 Apr. 2015, 23h59 Don't forget to submit your result for the second project on the submission platform
Project Ex. 24 Apr. 2015

Statement for project 3
Code
Edited Mon. 11 May

End of exercise session 8

Ex. Feedback 8 May 2015

Exercise session 9: Graphs
Feedback of project 2

FAQ Deadline 15 May 2015, 23h59

Check out the FAQ for the 3rd project
Don't forget to submit your result for the third project on the submission platform

Project 1 Jul. 2015

Statement for the second session project
Code

Deadline 14 Aug. 2015, 23h59

Don't forget to submit your result for the third project on the submission platform

Projects

FAQ for the 3rd project

Concerning the greedy approach

Yes, as long as your solution is really greedy! But don't forget that a portion of the mark is dedicated to the greedy's superior complexity with respect to the dynamic programming solution.

Concerning the dynamic programming-based approach

May I add some arguments to ErrMin(n, k)?

For example, I would like to have a function ErrMin(i,j,k) which computes the error of quantizing the values between i and j in k levels.

Yes. However, it is possible to formulate directly ErrMin(n, k). If you think you need both the start and the end of the range, we encourage you to have a look a the simplification used in the cutting rod problem (slide 356 and 357).
If you don't find a solution for ErrMin(n, k), one of the form of ErrMin(i,j,k) will be accepted without penalty.
In the formulation of ErrMin(n, k), you might need another function e(i, j) which computes the optimal error of quantizing the range [i, j[ by a single value.

Miscellaneous

Apparently, there is a disagreement on the PGM standard between GIMP (which generated those images) and the library we provided you: the version number (1.1) in GIMP's comment seems to be the origin of the problem. Either remove it (by opening the file with a text editor) or download the files again (the images should now be okay).
  • You can vizualize it directly in PGM with GIMP
  • You can vizualize it after conversion in a more common format: convert lena.pgm lena.png (for the ms8xx machines)
  • You can plot the error as a function of the number of levels and verify you obtain something coherent
Or you can compare your solution to ours: for lena.pgm on four levels, we obtained
  • v1=55, v2=106, v3=147, v4=194
  • p1=81, p2=127, p3=171
  • A minimum error of 42403084
However, note that you might get other thresholds/values as there might be several optima (the error should be the same, though)

If your warnings look like those:

It is due to the machine size_t length convention. This should not affect your program, though. Nevertheless, if you want to get rid of the warnings you can replace the %lu formaters corresponding to size_t variables by %zu formaters.

In any case, those warnings will not appear during code testing.

Testing machines

The projects must compile on the ms8xx (xx=01..25) machines !

Firstly, you need to create an account through the registration page.

Then you can connect to the machines thanks to SSH with the following command:

  • ssh login@ms8xx.montefiore.ulg.ac.be
where you need to replace login by your actual login and xx by a machine number (xx=01..25). SSH will open a terminal on the remote machine. For windows user, the PuTTY utility will mimic SSH behaviour (an illustrated step-by-step tutorial can be found here).

Several solutions are available to ship source code to and from the ms8xx machines.

  • FileZilla: a graphic, cross-plateform FTP client (an illustrated step-by-step tutorial can be found here)
  • scp: a command line utility to transfert file from/to remote hosts (it works much like the cp command)
  • rsync: a command line utility to synchronize remote files
  • sshfs: a command line utility to "mount" a remote directory
Those utilities might need some configuration/getting-used-to. A few hints to help you out:
  • Read the man page (so you can say you have)
  • Try the help flags -h, --help (you might even get useful information)
  • Google your questions or get a succinct tutorial (others have stumbled on the same difficulties, let them help you)
  • Script the data transferts, compilation steps, testing suite (human memory is the most expensive)

Oh, and be sure to chmod your home folder to prevent others from messing with your files.

Misc.

The Enigma Tower Riddle

The riddle requires the player to light on the nine plates by moving around the 3x3 plate grid.

Last modified on July 01 2015 15:11