INFO0902 - Data structures and algorithms

Random CS quote

There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.

C.A.R. Hoare



/ 09 Feb. 2018
16 Feb. 2018

Exercise session 1: Pseudo-code and recursion

YouTube More Sierpinsky's triangle-like shapes

Statement for project 0

Tutorial: Let's C

22 Feb. 2018

Optional project deadline

Feedback Ex. 23 Feb. 2018

Feedback on project 0

Exercise session 2: Analysis tools

YouTube Big O notation

Project Ex. 02 Mar. 2018

Statement for project 1

Exercise session 2: Analysis tools (second part)

/ 09 Mar. 2018
Ex. 16 Mar. 2018 Exercise session 3: Stacks, Queues, Lists, Vectors and Sequences
23 Mar. 2018

Don't forget to submit your result for the first assignment on the submission platform

Assignment 2:

  • Statement
  • Code
    • Heap.h updated on 28th Mar.
    • Heap.h updated on 16th Apr.

Exercise session 4: Heaps, Priority queues and Trees (first part)

Ex. 30 Mar. 2018

Exercise session 5: Dictionaries--binary search trees

/ 7 Apr. 2018

Easter holiday

/ 13 Apr. 2018

Easter holiday

22 Apr. 2018

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

20 Apr. 2018

Assignment 3:

Exercise session 6: Dictionaries--hash tables

Ex. 27 Apr. 2018

Exercise session 7: Brute force and dynamic programming

Ex. 04 May 2018

Exercise session 8: Divide and conquer and greedy algorithms

/ 11 May 2018


18 May 2018

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

FAQ for the second assignment

This design choice is left to you. Note, however, that the concept of median cannot be present in the heap implementation; the implementation must be general.
It is a structure whose definition (i.e. the fields it comprises) is not exposed in the .h file. It is an encapsulation mechanism.
As its name suggests, the purpose of the HeapReference is to reference an element of the heap. Since the HeapReference is opaque, you are free to choose what information to store inside (in the Heap.c file).
The only requirement is to be able to access an element in constant time. The content of the HeapReference depends on the representation you chose for the heap (array of pointer-based structure).
Not necessarily. It you opt for the pointer-based representation, you could implement the heap that way. However, it should prove easier to create another structure to represent the heap nodes.
If you go for the array representation, it is discourage to represent the heap as an array of HeapReference.
Your heap cannot have a bounded size. If you decided to implement the heap as an array, it must be extendable. A common way of doing this is to start with an empty array of arbitrary size (though not too large), and to double its length each time it is about to be filled.
Given the opacity of HeapReference, you cannot swap elements of a HeapReference array. What you can swap, however, is pointers to HeapReference. We therefore suggest you to use an array of the following structure:
struct heap_queue_item {
    HeapReference* ref; // a single reference to an element of the heap,
                        // obtained by calling referenceArrayAlloc(1)
    size_t heap;        // 0 if the ref points to the max heap, 1 if it points to min heap
Such structure allows you to swap the HeapReference (by swapping the HeapReference pointers) when needed.

Again, you can choose to represent your heap as an array or a pointer-based structure. If you choose the array representation, here is how you could implement it.

First, let us consider what information we need to store both in the Heap and HeapReference structures.

In Heap, we obviously need to have an array to represent the heap structure (let us call it heapArray). For the HeapReference, a first idea would be to simply keep an index to the array cell of the element. This however is not a good idea because the elements in heapArray might change positions on heap update (heapAdd, heapReplace), therefore invalidating the references.

We need to go for a different solution. The problem with a single heap array is that element might change position. Therefore, a solution would be to have a second array (let us call it indexes) of which each cell would store the index of a given element in heapArray and we would have to ensure that, in the indexes array, the position of an element does not change. The HeapReference could then simply keep the index of the element in the indexes array (see image below).

heap implementation

Note that to be able to implement the heapAdd and heapReplace operations correctly, you also need to know where is located an element in indexes given its position in the heap.

Finally, in the Heap structure, we need to store the size of the heap (number of elements stored inside of it), the capacity of the heap (total number of elements that can be stored in the current allocated arrays) and whether it is a max- or a min-heap.

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.


Testing machines

The projects 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
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.


Last modified on April 23 2018 16:34