.. _module3:


************************************************************************************************************
Module 3 | Arborescent data structures, Object Oriented Programming (inheritance, polymorphism, delegation)
************************************************************************************************************

Objective
=========

By the end of this module, students will be able to:

* Use and implement arborescent and recursive data structures (trees, lists, ...)
* Understand and implement traversal algorithms over trees and lists (prefix, infix, suffix)
* Be able to analyze the time complexity of algorithms over arborescent data-structures
* Understand serialization of arborescent data structures

Resources
=======================================


Slides (keynote)

* `Lecture 3a Arborescent and Recursive ADT Slides <https://www.icloud.com/keynote/0dDho7r2GPnohjW_2NfxvU_lg#cours3a-arborescent-structures>`_
* `Lecture 3a Arborescent and Recursive ADT videos <https://www.youtube.com/playlist?list=PLBMhFQpVgBPlQ8pjcSNXOeKLvM4KmvCfh>`_   
* `Youtube Live 2020  <https://youtu.be/W1BWLaev50c>`__  Q&A Session  
* `Object Oriented Programming Concepts Slides <https://www.icloud.com/keynote/0E9PWUKqyuydFjSsl-2FnedwQ#3b-object-oriented-programming>`_
* `Object Oriented Programming Concepts video <https://www.youtube.com/playlist?list=PLBMhFQpVgBPmeKn28eZYHTMdVv2CmzRBx>`_    
* `Youtube Live 2020  <https://youtu.be/Cj2-aJFw9k0?t=306>`__  Q&A Session 


Files used in the slides:

* RecursiveList.java :download:`java <RecursiveList.java>`
* RecursiveTree.java :download:`java <RecursiveTree.java>`
* BinaryExpressionTree.java :download:`java <BinaryExpressionTree.java>`


Exercises: week 1
=======================================

1. `Equality test between trees <https://inginious.info.ucl.ac.be/course/LEPL1402/TreeSame>`_
2. `Inorder traversals <https://inginious.info.ucl.ac.be/course/LEPL1402/TreeInorder>`_ 
3. `Combining two trees <https://inginious.info.ucl.ac.be/course/LEPL1402/TreeCombineWith>`_ 
4. `MCQ on time complexities <https://inginious.info.ucl.ac.be/course/LEPL1402/complexityMCQ2>`_ 

Restructuration 2021
--------------------

* :download:`Slides <./2021-10-21-Restructuration.pdf>`
* Source code of tree comparison: :download:`Node.java <./part1_code/exercise1/Node.java>` and :download:`Tree.java <./part1_code/exercise1/Tree.java>`
* Source code of in-order traversal: :download:`Traversal.java <./part1_code/exercise2/Traversal.java>`
* Source code of `decision trees <https://inginious.info.ucl.ac.be/course/LEPL1402/DecisionTree/DecisionTree-IaDkpoRQcUYIIOEmJgmw.zip>`_: :download:`DecisionTree.java <./part1_code/exercise3/DecisionTree.java>`


Exercises: week 2
=======================================

1. `Comparator vs Comparable <https://inginious.info.ucl.ac.be/course/LEPL1402/ComparatorvsComparable>`_
2. `Inheritance : Fill the gaps (Small Exercise) <https://inginious.info.ucl.ac.be/course/LEPL1402/Inheritance>`_ 
3. `Abstract class <https://inginious.info.ucl.ac.be/course/LEPL1402/AbstractClass>`_ 

Restructuration 2021
--------------------

* :download:`Slides <./2021-10-28-Restructuration.pdf>`
* `Youtube Live <https://youtu.be/L-q6rjgWffQ>`__
* Source code of the `physics solver <https://inginious.info.ucl.ac.be/course/LEPL1402/PhysicsSolver>`_: :download:`PhysicsSolver.java <part2_code/PhysicsSolver.java>`


Design exercise
----------------


Implement this interface with three different classes `Circle, Square, Triangle`.

.. code-block:: java

   public interface Shape {
  		public void draw();
  		public void erase();
   }

* Each method should print something to the console like "drawing a circle".
* Now implement one class RandomShape that randomly draw a circle, a square or a triangle by flipping a coin.
* What are the OOP principles that you are using here ?
* Can your design easily be used to also include rectangles in the RandomShape ?