Data Structures and Algorithms

Author: ClaudioGomes

Created: 2022-09-22 10:23pm

Edited: 2022-09-26 10:58pm

Description:

This mini course basically furnishes the students with the tool to answer the question: how many resources will I need for my algorithm?
It provides the basic tooling to compare algorithms in an idealized way, regardless of how fast computers have become: the bigOh notation.
The bigOh notation is essentially an algebra of worst case estimates.

Intended Learning Outcomes:

Explain the rationale behind the definition of the bigOh notation
Demonstrate graphically why some simplifications can be made in the bigOh notation
Demonstrate mathematically, applying the definition, what the bigOh of a given algorithm is.
Know the most common bigOh expressions for the most common algorithms.

Resources		Tasks		Supports
Chapter 2, Section 3.1	→	Explain to a peer what the intuition behind the definition of BigOh is. ↓	←	F2F Class time
Video: introduction to bigO notation		Analyze complexity of a few simple loop based algorithms. ↓	←	Discussion forum
Chapter 2. Section 3.2		Apply definition to multiple example expressions to derive the bigO of them. These expressions contain summations and other common arithmetic operations. ↓	←	F2F Class time
Chapter 2. Section 3.3 Thumb rules for bigO notation		Analyze complexity of more complex algorithms, containing function calls and sequential loops. ↓	←	F2F Class time
Wikipedia pages for common computer science problems.		Pick a known problem, code the algorithm, and determine its complexity. Explain and justify to a Peer. ↓	←	F2F Class time, Peers from group work.
Chapter 2. Section 5.2		Analyze complexity of recursive algorithms (the naive way) ↓	←	F2F Class time, Peers from group work.
Video lecture on the master theorem.		Analyze complexity of recursive algorithms using the master theorem. ↓	←	F2F Class time, Peers from group work.
Resource		Pick a known recursive problem, code the algorithm, and determine its complexity. Explain and justify to a Peer.	←	F2F Class time, Peers from group work.