INFO0902 - Data structures and algorithms
Controlling complexity is the essence of computer programming.
Brian Kernigan
Informations
Schedule
/ | 09 Feb. 2018 | |
Ex. Project Tutorial |
16 Feb. 2018 |
Exercise session 1: Pseudo-code and recursion More Sierpinsky's triangle-like shapes Tutorial: Let's C |
Deadline |
22 Feb. 2018 | |
Feedback Ex. | 23 Feb. 2018 |
Exercise session 2: Analysis tools |
Project Ex. | 02 Mar. 2018 |
Exercise session 2: Analysis tools (second part) |
/ | 09 Mar. 2018 | |
Ex. | 16 Mar. 2018 | Exercise session 3: Stacks, Queues, Lists, Vectors and Sequences |
Deadline Project Ex. |
23 Mar. 2018 |
Don't forget to submit your result for the first assignment on the submission platform Assignment 2: 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 |
Deadline |
22 Apr. 2018 |
Don't forget to submit your result for the second assignment on the submission platform |
Project Ex. |
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 |
Break |
Deadline Ex. |
18 May 2018 |
Assignment:
Exercise session 9: Graphs |
Project |
04 Jul. 2018 | |
Deadline |
14 Aug. 2018 |
Don't forget to submit your result for the 2nd session assignment on the submission platform |
FAQ for the second assignment
.h
file. It is an encapsulation mechanism.
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).
If you go for the array representation, it is discourage to represent the heap as an array of
HeapReference
.
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).
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.
FAQ for the third assignment
Compression error: 87756716
, it relates to the error introduced by the compression as calculated by Eq. (1) of the statement.
In other words, the program is working fine.x
In contrast, a non-analytical solution could be to
- Search exhaustively the optimal value.
- Devise an iterative procedure which would reduce the error on the optimal solution at each step.
size_t
type. You can include stddef
. A new version of the code has been uploaded to the website and the submission platforms uses the correct version.
- Choosing an interval randomly
- Placing the threshold in the middle
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
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-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 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
- Mark criteria
- Pseudo-code LaTeX package of the reference book
- A working example of the LaTeX package and its result