INFO0902 - Data structures and algorithms

Random CS quote

Writing in C or C++ is like running a chain saw with all the safety guards removed.

Bob Gray

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 True/false: questions a, b and e + Question 4 on Binary Search Trees True/false: questions a, b and d Question 5: partition problem
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

There is a problem with my marks for the first project.

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

What is a Makefile? How do you write it?

There is plenty of doc. on the net. A few pointers:
A quick overview
A more in-depth material

How do you parse CSV files?

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.

In which direction the shifts from the `shifts` program must be given?

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.

What are the `R` and `l_max` values corresponding to ciphered.txt?

R=5.
l_max must greater than the longest word in the original text. A value of 20 should be enough.

I get timeout error when I submit my project.

You have more time now (5 minutes for an individual test).

FAQ for the 2nd project

I have some memory leaks in the submission report but not on the ms8xx machines, what can I do?

Relax. The ms8xx machines are the sole judges.

How should strings be compared?

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.

In `freeBinarySearchTree`, what is the purpose of `freeContent`?

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.

I got a warning about `passing 'SequentialSet *...' to parameter of type 'const SequentialSet ' (aka 'const struct SequentialSet_t ') discards qualifiers`

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);

Should my tree be balanced?

This is not required. However, the function must be correct and will be tested on trees known to be (un)balanced.

I got the following warning:
`main.c:188:5: warning: format ‘%zu’ expects argument of type ‘size_t’, but argument 2 has type ‘int’ [-Wformat=] printf("Tree height : %zu\n", getHeight(bst));`

The warning is due to the printf function. Changing %zu to %d should turn it off.

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.

Submission platform (Cicada)
Mark criteria
Pseudo-code LaTeX package of the reference book
A working example of the LaTeX package and its result

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)