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
• Lecture 2a Complexity Videos
• Youtube Live Q&A Session
• Course 2b Abstract Data Types and Proof of Programs Slides
• Lecture 2b Abstract Data Types and Proof of Programs Videos
• Youtube Live restructuration 2020 Q&A Session
• Restructuration 2021 Q&A Session

Exercises: week 1

1. Time Complexity simple MCQ
2. Space Complexity MCQ
3. Array Search
4. Merge Sort
5. Largest Sum Contiguous Subarray

Exercises: week 2

1. Recursion Fibonacci
2. Bubble Sort Invariant
3. Recursion Hanoi Tower
4. Longest Valley in an Array
5. Implement a stack with a queue
6. Implement a circular linked list
7. Implement a queue with two stacks
8. Implement an array list