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 |
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
End of exercise session 4 |
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 |
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 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
|
Project | 1 Jul. 2015 | |
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
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.
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.
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
- 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
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
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
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
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 thecp
command)rsync
: a command line utility to synchronize remote filessshfs
: a command line utility to "mount" a remote directory
- 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.
- Submission platform (Cicada)
- Mark criteria
- Pseudo-code LaTeX package of the reference book
The Enigma Tower Riddle
The riddle requires the player to light on the nine plates by moving around the 3x3 plate grid.
- The simulator (Java 8) from exercise session 9
- An illustrating video (up to 10:12)