Objectives

At the end of this part each student will be able to:

• make the distinction between the notations \(\mathcal{\sim}\), \(\mathcal{O}\),

  \(\mathcal{\Theta}\), and \(\mathcal{\Omega}\), know their properties and definitions;

• describe precisely the properties of the abstract types stack and queue;

  as well as the various types of chained lists;

• distinguish between an abstract data type and its implementation

• implement and evaluate an implementation of a stack by a simply or doubly chained list;

• use unit tests (with JUnit) to test and prove the correct operation of a program

• use the various collections present in the Java language, with the help of the documentation.

To read

Reference book:

• Chapter 1, section 1: some reminders of Java and programming in general

• Chapter 1, section 2: Data Abstraction

• Chapter 1, section 3: Stacks, queues, bags, linked lists

• Chapter 1, section 4: Algorithm analysis

As well as this document summarizing the different notations of Complexity.

Slides

• Slides introduction

• Slides exercices

• Slides restructuration