INFO0902 - Data structures and algorithms

Random CS quote

Simplicity is prerequisite for reliability.

Edsger W. Dijkstra, How do we tell truths that might hurt? (1975)

Informations

Schedule

Project Tutorial 12 Feb. 2016

Statement for project 0
Code

Tutorial: Let's C
Jean-François Grailet's page for the C tutorial

Ex. 19 Feb. 2016

Exercise session 1: Pseudo-code and recursion

Deadline 25 Feb. 2016 Optional project deadline
Project Ex. Feedback 26 Feb. 2016

Statement for project 1
Code

Exercise session 2: Analysis tools

Feedback on project 0

Ex. 4 Mar. 2016

Exercise session 2: Analysis tools

Ex. 11 Mar. 2016 Exercise session 3: Stacks, Queues, Lists, Vectors and Sequences
Project Ex. 18 Mar. 2016

Statement for project 2
Code
Check out the FAQ for the 2nd project

Exercise session 4: Heaps, Priority queues and Trees

Deadline 25 Mar. 2016, 23h59 Don't forget to submit your result for the first project on the submission platform
Q&A 25 Mar. 2016 Question and Answers on the projects
/ 1 Apr. 2016 Easter holiday
Ex. 8 Apr. 2016

Exercise session 5: Dictionaries

Project Ex. 15 Apr. 2016

Statement for project 3
Code

Bring an internet-enabled device with you.
Exercise session 6: Data structures and dictionnaries
Exercise session 7: Problem solving: brute force and divide-and-conquer

Deadline

15 Apr. 2016, 23h59

17 Apr. 2016, 23h59

Check out the FAQ for the 2nd project

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

[EDIT 7 Apr.] Deadline pushed back to 17 Apr.

Ex. 22 Apr. 2016 Exercise session 8: Problem solving (dynamic programming and greedy algorithms)
Ex. 29 Apr. 2016

Exercise session 8: Problem solving (dynamic programming and greedy algorithms)

/ 06 May 2016

Theoretical course only

Ex. 13 May 2016

13:30 - Exercise session 9: Graphs

15:30 - Correction of some exercises from previous exam. + Q&A

Deadline

13 May 2016, 23:59

15 May 2016, 23:59

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

[EDIT 12 May] dealine extended

Project 6 Jul. 2016

Statement for the second session project
Code

Deadline 14 Aug. 2016, 23h59

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

General FAQ

It's been fixed! Apparently, the platform does not manage floating points. I've performed the rounding before re-submitting the marks this time.

Projects

FAQ for the 3rd project

Basically, you have to read the file line by line (just as in the 2nd project) and split the line according to the ; delimiter. You then have to convert from string to interger.
It must be the shifts that the original file underwent ; the key printed must be the same that was originally used to cipher the text.
R=5.
l_max must greater than the longest word in the original text. A value of 20 should be enough.
You have more time now (5 minutes for an individual test).

FAQ for the 2nd project

The actual comparison mechanism does not matter as long as it spans a total ordering of the strings. However, the most logical choice is the lexicographical ordering. Take a look at the fonction strcmp defined in string.h.
If freeContent is set to
  • false: the function must free all the memory associated to the BST but not the string themselves. This ensures that a user can free the BST and still use the strings that were put in (this is the default expected behavior). This also makes it possible to delete all the words, since only one is present in the BST for every identical words.
  • true: the function must free both the memory associated to the BST and the strings it contains. This is a shortcut provided to the user.
This is most probably because you are passing a variable of type SequentialSet** to the intersect function whereas the compiler is expecting const SequentialSet** (i.e. the const is missing). For some reason, the compiler is unable to infer the const.
Consequently, you should cast it explicitely: intersect((const SequentialSet**) myseqSetArray, nbSets);
This is not required. However, the function must be correct and will be tested on trees known to be (un)balanced.

Debugging

A few useful tips for debugging

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-platform 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 March 02 2017 09:43