.. _module2:


*************************************************************************************************************************************
Module 2 | Complexity, Recursive Programming, Arborescent data structures, Basic algorithms, Invariants and proof of correctness
*************************************************************************************************************************************

Objective
=========

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

* Use (and explain) spatial and temporal complexity concepts, along with the mathematical tools used to describe them
  (big-Oh/Omega/Theta notations and definitions).
* Analyse complex algorithm and derive their complexity
* Code a binary search
* Code the merge sort algorithm
* Explain the RAM model
* Use recursive programming
* Use arborescent data structures (trees, lists, ...)
* Use invariants to show both correctness and complexity of an algorithm


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


* `Lecture 2a Complexity Slides <https://www.icloud.com/keynote/0bLkKAW-hohVQRrH29TBVJfuA#cours2a-complexity_-_copie>`_
* `Lecture 2a Complexity Videos <https://www.youtube.com/playlist?list=PLBMhFQpVgBPm-UBVWpi9rYET2sXuXtCob>`_
* `Youtube Live  <https://youtu.be/Kij2Z6aqUQE>`_  Q&A Session
* `Course 2b Abstract Data Types and Proof of Programs Slides <https://www.icloud.com/keynote/0rn26lkOFEQaPybTU6oGOZTsw#cours2b-invariants-recursion>`_
* `Lecture 2b Abstract Data Types and Proof of Programs Videos <https://youtu.be/yUIeckjGRKM>`_
* `Youtube Live restructuration 2020  <https://youtu.be/eTf77e2EmVk?t=450>`_  Q&A Session
* `Restructuration 2021  <https://youtu.be/lD9MPvXNv8U>`_  Q&A Session 


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

1. `Time Complexity simple MCQ <https://inginious.info.ucl.ac.be/course/LEPL1402/ComplexityMCQ1>`_
2. `Space Complexity MCQ <https://inginious.info.ucl.ac.be/course/LEPL1402/ComplexitySpaceMCQ>`_
3. `Array Search <https://inginious.info.ucl.ac.be/course/LEPL1402/ComplexityArraySearch>`_
4. `Merge Sort <https://inginious.info.ucl.ac.be/course/LEPL1402/MergeSortImplementation>`_
5. `Largest Sum Contiguous Subarray <https://inginious.info.ucl.ac.be/course/LEPL1402/MaximumSumSubarray>`_

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

1. `Recursion Fibonacci <https://inginious.info.ucl.ac.be/course/LEPL1402/Fibonacci>`_
2. `Bubble Sort Invariant <https://inginious.info.ucl.ac.be/course/LEPL1402/BubbleSortInvariant>`_
3. `Recursion Hanoi Tower <https://inginious.info.ucl.ac.be/course/LEPL1402/HanoiTower>`_
4. `Longest Valley in an Array <https://inginious.info.ucl.ac.be/course/LEPL1402/valley>`_
5. `Implement a stack with a queue <https://inginious.info.ucl.ac.be/course/LEPL1402/StackWithQueue>`_
6. `Implement a circular linked list <https://inginious.info.ucl.ac.be/course/LEPL1402/CircularLL>`_
7. `Implement a queue with two stacks <https://inginious.info.ucl.ac.be/course/LEPL1402/QueueWithStacks>`_
8. `Implement an array list <https://inginious.info.ucl.ac.be/course/LEPL1402/MyArrayList>`_