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

Exercises: week 1

  1. Equality test between trees
  2. Inorder traversals
  3. Combining two trees
  4. MCQ on time complexities

Restructuration 2021

Exercises: week 2

  1. Comparator vs Comparable
  2. Inheritance : Fill the gaps (Small Exercise)
  3. Abstract class

Restructuration 2021

Design exercise

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

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 ?