Antonio Mucherino's Teaching pages


These webpages collect some didactic material that I have been preparing for my courses. They contain slides for my lectures, as well as some assignments proposed to my students. Notice that the material below is organized by topic, not by course. This way, students (and whomever interested) can easily find supplementary material for their preferred topics.


Advanced Programming

   This is a new course, given for the first time in the second semester of the academic year 2023-24. For the very first time, I'm collecting all didactic material (including codes) related to this class in a GitHub repository!


Operating Systems and Computer Networks

   This section contains the didactic material related to some courses that I'm currently giving at University of Rennes 1, where the main focus is on Operating Systems and Computer Networks. For some colleagues, these two topics cannot be separated, because strictly related, and I agree, myself I'm putting them together in this section. However, for organization reasons at my University, I cannot always teach these two topics in one single course. If you are one of my students to which I'm only teaching about Operating Systems, you may want to give a look at the material concerning the Computer Networks as well.

   The Operating System part is generally organized as shown in the following tree structure.

Operating Systems

   This course begins with the notion of bit of information and it develops, step by step, mainly from a theoretical point of view, the various components of a computer machine. We will construct a few logic circuits for implementing basic operations (such as logic and arithmetic operations), but also for temporarily storing data. We will "develop" our first processor, which will actually initially resemble to a very primitive processing unit. We will then include cache memories and independent cores, in a way that our processor will look more and more like a real modern processor. Memory management is an important issue in modern computers, because of their multi-tasking nature: a large part of this course will in fact be devoted to the main principles behind the implementation of the virtual memory.

   Logic circuits are at the basis of the several operations that our processors can perform. In many situations, we do not need to worry about them, in the sense that those logic circuits are already implemented in the CPUs at hardware level, and it may look like that knowing about them may simply reduce to personal curiosity. But actually there exist situations where an implementation at software level of logic circuits can potentially improve the performances of our programs.

Assignments on data representation and logic circuits:
  • A collection of simple exercises on logic circuits: LogiCircuits.pdf

  • Some exercises where logic operations performed directly in the CPU registers allow us to implement SIMD operations by vector instructions: SIMDonRegisters.pdf

  • A Java assignment about an ad-hoc binary representation that can be devised for a particular application: carImmatriculation.pdf; the Java class mentioned in the text can be downloaded here: carImmatriculation.java.

   Memory actually appears at several levels in our computer machines. The CPU itself is equipped with a very little memory that we call the registers, where the data need to transit in order to be processed. The virtual memory instead contains the data related to the programs that are currently running on the machine. See these handcrafted slides for some information on the main principles governing the implementation of virtual memory in modern computer machines. Between the CPU registers and virtual memory, there are other levels of memory. We can in general talk about cache memory, which has the main task to keep, in a place where the CPU can have a fast access to, the data that will most likely be requested by CPU for performing its next instructions.

Assignments on cache memory and virtual memory:
  • Can we conceive our programs so that they can have an optimal access to the cache memory? CacheAccessOpt.pdf

  • Some of the main concepts about virtual memory are summarized at the beginning of the following document: vMemory.pdf. The same document contains some exercises on the topic.

   Another important concept in Operating Systems is their multi-tasking, or multi-threading, nature. Since the very beginning, several attempts have been done to give at least the illusion to the final user that the computer machine is able to perform several tasks at the same time. Nowadays, this is not anymore just an illusion: our more recent CPU devices are composed by several cores, which are able to perform operations independently from each other, by allowing therefore for a primitive kind of parallelism. Things can happen in parallel on our computer machines, even when equipped with only one processor.

Assignments on multi-threading:
  • An assignment with some simple exercises about algorithmic complexity: AlgComplexity.pdf.

  • An assignment about semaphores and deadlocks: Semaphores.pdf.

  • What changes if instead of running our programs on the cores of a single CPU, we try to run them on a GPU device? This is a Java assignment (so no need to write for real the code in GPU environment) where we'll try to give a (at least partial) answer: Sierpinski.pdf; the Java class to be completed can be downloaded here: TextGraphics.java.
Computer Networks

   The part about Computer Networks begins with a short schematic and historical view of such networks. Emphasis is given to the lowest network layers, because closer to the Operating System.

  • An Introduction to Computer Networks.

    The various layers of the OSI model are presented, from the lowest (the physical layer) to the highest (the application layer), with a quick comparison with the IP/TCP model. The basic idea behind the encapsulation of the data is finally presented.

Assignments on computer networks:
Human-machine interaction

Finally, we give some emphasis to the way users can interact with the computer machines, and in particular with the Operating Systems. Whenever you're reading this webpage on your laptop or smartphone, the medium that allows you to establish the "communication" is your browser. Another, more efficient, and bi-directional, way to communicate with the computer machine is via the shell provided by the Operating System.

  • Bash Scripting.

    This lecture introduces Bash scripting. It starts with a presentation of Bash as a interpreted programming language, and it continues with an overview of commands and some scripts for interacting with the file system. Many simple examples are provided, and attention is also given to the efficiency of the proposed implementations. Among the others, commands such as "bc" and "awk" are presented.

Notice that these same slides were used in the past to teach Bash Scripting to non-informaticians. They may look a little naive to the more expert reader. Some exercises on Bash scripting are proposed in this document (a translation in French of the document is also available).

Multi-threading projects 2022-23

   This year, a large part of the course will be focused on the project: all lab time-slots (6 in total, 12 hours) will in fact be devoted on your work on the project. All projects will have to be implemented in sequential and in multi-threading.

   You are free to choose any topic from the list below. Some topics are didactical, others are closer to open problems in scientific research. As the difficulty level of your project increases, some conditions are adapted, as for example you may work on your project with more partners. Whichever is the topic you will choose, there is no need to worry about your project grade: it's the work in the lab that will be mainly evaluated, and not the final result (even though, for the didactical topics, we expect to get a perfectly working implementation at the end of the semester).

   The project topics are described in a few lines below. It's up to you to find additional information about these topics before starting with the implementation work. Even when not explicitely written, it will be necessary to provide a multi-threading implementation of your code, together with an initial sequential version. If you have any questions, please do not hesitate to ask your teacher!

   The list of topics:

  • Project 1:

    An extension of the AirSimulation assignment (see above). The idea is to double-check the provided code, to verify the feasibility of the assignment, and to add more tasks to the assignment. In particular, we wish to add an exercise where the evacuation of the airplane is simulated, where the access to the emergency exits will be controled by semaphores having a variable number of permits. We expect in the end to have a new version of the assignment, as well as a detailed correction (min_grade=0/20,max_partners=1).

  • Project 2:

    Karger's algorithm is a randomized algorithm for finding the min-cut of a connected graph. We wish to implement it in Java, in sequential and in multi-threading. The code will have to be organized in a way that the operations on the graphs are performed by an independent Java class, whereas the algorithm itself is implemented in another class. Extensive tests with several graphs are expected to be submitted with the code (min_grade=2/20,max_partners=1).

  • Project 3:

    Numerical differentiation is often used in implementations because it does not require the explicit computation of the function gradient. However, a main drawback is that many formulae for numerical differentiation require several function evaluations, this way increasing the time complexity for the differentiation. The idea in this project is to compare some formulae for numerical differentiation, in sequential and in multi-threading. You may work in Java; but implementations in C are also accepted (min_grade=3/20,max_partners=2).

  • Project 4:

    The binMeta package collects Java implementations, under a common interface, of meta-heuristic searches. In this project, the idea is to enrich the package with two additional objective functions, the ones related to the bin packing and set covering problems. Your implementations need to be compatible with the interfaces provided in the Java package (min_grade=3/20,max_partners=2).

  • Project 5:

    We are interested in performing a wide search on C or Java implementations of numerical methods for the computation of the top-k eigenvalues and eigenvectors of a given matrix. Your search needs to focus on both sequential and multi-threading implementations. Then, an extensive comparison of the implementations needs to be performed on a given benchmark. You'll have to implement all codes that cannot be found online, e.g. the multi-threading versions (min_grade=4/20,max_partners=2).

  • Project 6:

    We wish to devise a general binary representation for graphs. In other words, given a graph G, represented by a proper Java class (which may contain List types for its vertices etc), we want to convert this internal representation in a simple sequence of bits, and vice versa. After an accurate search on the Internet, please write your codes in Java (min_grade=5/20,max_partners=3).

  • Project 7:

    MDjeep is a software tool for distance geometry (watch this YouTube video, and then read my research page). This software tool is able to solve distance geometry problems for which the search space can be represented as a binary tree. However, because of some approximation errors on the available distance values, it is necessary to associate small continuous regions to every node of the tree, instead of simple singletons. In the current implementation, the spectral projected gradient method is used to deal with such continuous regions, which are approximated by ad-hoc 3D boxes. In this project, we wish to replace the gradient method with a Gauss-Newton method, in order to benefit of better convergence properties. This project needs to be entirely written in C (min_grade=6/20,max_partners=4).

Notice that the min_grade would drop if you were not present at any lab, or if your teacher realized that you were not enough engaged in the project work.

Operating Systems course evaluations

   This year your final grade will depend on two main factors: your performance at class quizzes (this is an example of quizz given at the exam in December 2019 for the Operating Systems class, but please consider that the course program has evolved a lot since 2019) and the project grade.


Programming

Below are the slides I have used for some lectures that I gave in the past years.

  • Algorithmics and C basis.

    This is a quick introduction to algorithms, with some basic examples in C programming language. Some more advanced concepts, such as the procedural programming, the pointers in C and software libraries, are also mentioned.

  • C++ in 90 minutes.

    A quick introduction to the C++ programming language.


Operational research

I was teaching Operational Research quite a lot at the very beginning of my career. Below I'll try to collect some old assignments that I had prepared for my classes (as I rediscover them again in my archives).

  • This is a linear modeling assignment: CarreMagique.pdf (only in French at the moment, sorry...). You're supposed to use AMPL to solve it, together with your preferred linear solver. Some AMPL files can be downloaded here: CarreMagiqueAmpl.tar.gz.


Numerical analysis

I'm currently affiliated to a department of Computer Science where there is no much space, in the proposed teaching programs, to numerical analysis. Here below a collection of slides for some short lectures I was giving some years ago.

  • Notions of Numerical Analysis.

    This lecture gives some quick notions of Numerical Analysis. It includes short discussions about linear systems, the problem of finding roots of real-valued functions, interpolation, numerical integration and optimization.


Bioinformatics

Teaching the topics related to performed research activities is very important for a researcher. Below some slides with a short introduction to bioinformatics, which soon then focus on my main research activities (last update on October 2016).

  • Algorithms in Bioinformatics.

    The main focus of this lecture is on the Molecular Distance Geometry Problem (MDGP, see my research page) and on a new approach for its discretization. The discretization allows us to solve the problem by employing a branch-and-prune (BP) algorithm. However, particular assumptions, that are strongly based on the order on which the atoms of a molecule are considered, need to be satisfied for performing the discretization ...

Some exercises on distance geometry and the discretization assumptions are proposed after the lecture.


Other info

The full list of courses that I'm giving during the current academic year can be found on my cv.
The full list, with syllabus, of the other classes I gave in the past: visit this page.


Back Home