INFO0902 - Data structures and algorithms

Random CS quote

When there's a will to fail, obstacles can be found.

John McCarthy

Informations

Schedule

Assignment	08 Feb. 2019	Optional assignment: Statement for assignment 0 Code
Ex.	15 Feb. 2019	Exercise session 1: Pseudo-code and recursion
Deadline	21 Feb. 2019	Optional assignment deadline
Feedback Tutorial Assignment	22 Feb. 2019	Feedback on assignment 0 Tutorial: Let's C Assignment 1: Statement Code Check out the FAQ for this first assignment
Ex.	01 Mar. 2019	Exercise session 2: Analysis tools (first part) Big O notation
Ex.	08 Mar. 2019	Exercise session 2: Analysis tools (second part)
Ex.	15 Mar. 2019	Exercise session 3: Stacks, Queues, Lists, Vectors and Sequences
Assignment Ex.	22 Mar. 2019	Assignment 2: Updated on 05th of April (Maze.h) Statement Code check out the FAQ for the second assignment. Exercise session 4: Heaps, Priority queues and Trees
Deadline	24 Mar. 2019	Don't forget to submit your first assignment on the submission platform
Ex.	29 Mar. 2019	Exercise session 5: Dictionaries--binary search trees
Ex.	05 Apr. 2019	Exercise session 6: Dictionaries--hash tables
/	7 Apr. 2019	Easter holiday
/	13 Apr. 2019	Easter holiday
Assignment Ex.	26 Apr. 2019	Assignment 3: Statement Code Data Exercise session 7: Brute force and dynamic programming (first part)
Deadline	28 Apr. 2019	Don't forget to submit the second assignment on the submission platform check out the FAQ for the second assignment.
Ex.	03 May 2019	Exercise session 7: Brute force and dynamic programming (second part)
Ex.	10 May 2019	Exercise session 8: Divide and conquer and greedy algorithms
Deadline	16 May 2019	Don't forget to submit the third assigment on the submission platform
Ex.	17 May 2019	Exercise session 9: Graphs Mock exam
Assignment	05 Jul. 2019	Assignment bio-info: Statement Data
Assignment	09 Jul. 2019	Statement for 2nd session assignment Code
Deadline	18 Aug. 2019	Don't forget to submit your result for the 2nd session assignment on the submission platform
Deadline	25 Aug. 2019	Don't forget to submit the assignment on the submission platform

FAQ for the first assignment

The `Sort` function takes in array and its length but some of the algorithm works with two indices rather than the length. Can I change the signature of the function?

No you cannot. You have to find a way out.
Although it is technically possible (with some pointer algebra) to use the given signature directly, it might be cleaner to use an static auxiliary function which has the proper signature.

I have warning when compiling the `main.c` file regarding the `%zu` formatting.

This is a portability/compatibility issue which happens sometimes. It arrises from the fact that your machine does not encode the size_tvaribles on the same number of bits as it is on ours.
This can either be ignored, or you can change the formatting as need. In any case, the main.c is not used during grading.

I get `TERM environment variable not set` in the submission output.

This error message is due to virtual machine which is used to test the submissions and can been safely ignored.

FAQ for the second Assignment

We can not find an example corresponding to the worst case for the function `MzIsValid`. Is it enough to give an upper bound of the complexity in this case?

Yes. Depending on your implementation, the exact analysis of the worst case of the function MzIsValid can be difficult. In this case, it is enough to provide an upper bound of the complexity without providing an example of a maze corresponding to this worst case.

Supplementary material

Visual Algo is a site which illustrates many algorithms and data structures of the course. In addition, in the training section, you are able to create online quizz on those topics to test your knowledge.

Misc.

Testing machines

The Assignments must compile on the ms8xx (xx=01..24) 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
Mark criteria
Pseudo-code LaTeX package of the reference book
A working example of the LaTeX package and its result

INFO0902 - Data structures and algorithms

Informations

Schedule

FAQ for the first assignment

The Sort function takes in array and its length but some of the algorithm works with two indices rather than the length. Can I change the signature of the function?

I have warning when compiling the main.c file regarding the %zu formatting.

I get TERM environment variable not set in the submission output.

FAQ for the second Assignment

We can not find an example corresponding to the worst case for the function MzIsValid. Is it enough to give an upper bound of the complexity in this case?

Supplementary material

Misc.

Testing machines

Misc.

The `Sort` function takes in array and its length but some of the algorithm works with two indices rather than the length. Can I change the signature of the function?

I have warning when compiling the `main.c` file regarding the `%zu` formatting.

I get `TERM environment variable not set` in the submission output.

We can not find an example corresponding to the worst case for the function `MzIsValid`. Is it enough to give an upper bound of the complexity in this case?