First semester
Algorithms Design and Complexity
Objectives
Calculate the complexity of an algorithm, identify its complexity class, evaluate the time required for its completion ; Produce an algorithm in Python of lower complexity achieving the same result ; Describe the main components of a computer.
Course outline
Different types of complexity of algorithms and problems ; Big-O, big-Omega, and big-Theta notation ; Iterative algorithms and summation complexity analysis ; Recursive algorithms and induction complexity analysis ; The divide-and-conquer strategy ; Data structures such as arrays, linked lists, stacks, queues, and hash tables ; Proof techniques such as induction, reasoning by contradiction, and the master theorem ; Dynamic programming.
Prerequisites
Rudiment in imperative programming