# Best Students’ Projects 2020/21

A selection of best projects designed by some of the brightest students I worked with in 2020/21

PONG Game (M.B. 1E-SA 2020/21) – Scratch Download

Maze Ball (S.P. 1E-SA 2020/21) – Scratch Download

Fibonacci Spiral (T.S. 2E-SA 2020/21) – Scratch Download

La Crittografia nella II Guerra Mondiale (A.P. 5E-SA 2020/21) – Ppt Download

# A Simple Proof of Zorn’s Lemma

Just a personal rephrase of JONATHAN LEWIN’s simple proof of the Zorn Lemma, which I would really like to remember… so let’s work out all the details…

(… The proof is simple in the sense that it needs neither transfinite induction, nor Ordinals, just the Axiom of Choice (**AC**) and elementary extremality arguments …)

Theorem (Zorn’s Lemma). Suppose is a partial order in which every chain is bounded from above. Then has a maximal element.

Def. If is a chain (*i.e.* total order) and , then is named the ** initial segment** of in .

Proof. Suppose has *no* maximal element, towards a contradiction. If is any chain in , let be an upper bound of . Since has no maximal element, there exists such that . So, admits a ** strict upper bound**. By

**AC**, there is a choice function which assigns to every chain a strict upper bound .

The sought contradiction will be that of finding a chain such that . This is catalysed by the following notion of *conforming* subset.

Def. Say that a subset is **conforming **if the following two conditions hold:

- is a well order (i.e. is a
*chain*such that*every*subset of has a*least*element); - for every , it holds .

Comparability Lemma. If are conforming and , then one of these two sets is an initial segment of the other.

Proof of Comparability Lemma. Since we can assume w.l.o.g. .

Let .

Then . So the *Claim* reduces to show .

Towards a contradiction, assume .

Let .

Let .

*Closure Lemma*. Given any , if and then:

- (by definition of and )
- (since , so by definition of , thus too, and by definition of )

so .

With this, we can show that . Indeed, follows already by definition of , so the actual claim is that . Let , then (by def. of ), so ; also (by def. of ); finally, it is not possible that , otherwise by *Closure Lemma* it would be against own definition. Therefore, . Since and , then .

Also, . Indeed, (by definition) so but , therefore (by definition of at this point).

Since , and since , we cannot have (because by definition). Therefore, , and we conclude , against definition of .

This implies that , *i.e.* , closing the proof of the Comparability Lemma.

By the Comparability Lemma, it is clear that the union of all conforming subsets of is conforming. Thus, if is a strict upper bound, then is conforming too. Since is the union of all conforming sets, then , contradicting that is a *strict* upper bound of .

So has one maximal element.

# Instantaneous Reaction-Time in CSTNs on JLAMP

These days an extended version of our paper “*Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks” *has been accepted for publication (to appear during March 2020, https://doi.org/10.1016/j.jlamp.2020.100542) in:

Journal of Logical and Algebraic Methods in Programming, Elsevier

# Sorting with Forbidden Intermediates goes to DAM

An extended version of our paper “*Sorting with Forbidden Intermediates (Searching (s,t)-Paths avoiding Forbidden Vertices in Hypercube Graphs)*” has been accepted for publication in international journal (https://doi.org/10.1016/j.dam.2019.10.025):

**Discrete Applied Mathematics, Elsevier **

**(journal of combinatorial algorithms, informatics and computational sciences)**.

Joint work with *Stéphane Vialette* (CNRS and UPEM, Paris, France), *Anthony Labarre* (UPEM, Paris, France) and *Romeo Rizzi* (Univ. Verona, Italy)

# Linear Time Safe-Alternating DFS and SCCs

An alternating graph is a directed graph whose vertex set is partitioned into two classes, existential and universal. This forms the basic arena for a plethora of infinite duration two-player games where Player and alternate in a turn-based sliding of a pebble along the arcs they control.

We study alternating strongly-connectedness as a generalization of strongly-connectedness in directed graphs, aiming at providing a linear time decomposition and a sound structural graph characterization. For this a refined notion of alternating reachability is introduced: Player attempts to reach vertices without leaving a prescribed subset of the vertices, while Player works against. This is named *safe alternating reachability*. It is shown that every alternating graph uniquely decomposes into safe alternating strongly-connected components where Player can visit each vertex within a given component infinitely often, without having to ever leave out the component itself.

Our main result is a linear time algorithm for computing this alternating graph decomposition.

Both the underlying graph structures and the algorithm generalize the classical decomposition of a directed graph into strongly-connected components.

The algorithm builds on a linear time generalization of the depth-first search on alternation, taking inspiration from Tarjan 1972 machinery.

Our theory has direct applications in faster solving well-known infinite duration pebble games. Dinneen and Khoussainov showed in 1999 that deciding a given Update Game costs time, where is the number of vertices and is that of arcs. We solve that task in linear time. With this the complexity of Explicit McNaughton-Muller Games also improves from cubic to quadratic.

Download: manuscript.