Learning Outcomes

Understand how this course is organized and basic concepts in algorithmic analysis

You understand

how this course is organized
how to succeed in this course
how to specify a computational problem
why is analysis of algorithms needed
how to analyze the correctness of algorithms
how to analyze the running time complexity of analysis
how computational model affects the analysis

Referencing modules: Introduction

Apply algorithmic analysis & design principles to a problem

You are able to

select a computation problem to work on
analyze a problem and its complexity
analyze several algorithmic solutions to the problem
use one or more appropriate models of computation in the analysis
implement the algorithmic solutions in a programming language
design experiments to evaluate algorithmic solutions
select and/or generate input data for the algorithmic solutions
analyze empirical results to get a deeper understanding of the algorithmic solutions and/or the problem

Referencing modules: Project

Understand sorting algorithms and their analysis

You understand

the sorting problem and its lower bound
comparison-based sorting algorithms: Selection Sort, Insertion Sort, Merge Sort, Heapsort, Quicksort
non-comparison-based sorting algorithms: counting sort, radix sort, bucket sort
Worst case analysis versus average case analysis
how to make lower bound arguments
how to solve recurrence relations
how sorting relates to the order statistics problem

Referencing modules: Sorting

Understand amortized analysis and their application to heap data structures

You understand

amortized analysis: aggregate, accounting, potential methods
binomial heaps
fibonacci heaps

Referencing modules: Heaps

Understand search trees algorithms and their analysis

You understand

binary search trees
red-black trees
interval trees
B trees and B+ trees

Referencing modules: Trees

Understand algorithm design methods

You understand how to design and analyze algorithms using

bruteforce or exhaustive search method
divide and conquer method
dynamic programming method
greedy method
iterative improvement method

Referencing modules: Algorithm Design Methods

Understand hashing-based algorithms

You understand

different hash table algorithms
different collision resolution methods and their analysis
universal hash functions and their construction
perfect hashing

Referencing modules: Hashing

Know how to design and analyze graph algorithms

You know how to

represent graphs using data structures
matrices and graphs duality
design algorithms that operate on graphs
traverse graphs using DFS & BFS
find strongly Connected Components
find Minimum Spanning Trees
find Single Source Shortest Paths
find All Pairs Shortest Paths

Referencing modules: Graph Algorithms

Understand NP-Completeness and how to deal with NP-hard problems

You know how to

analyze the hardness of problems
represent problems as strings in a particular language and encoding
represent decision problems as language recognition
represent algorithms as language recognizers
recognize and prove NP-hard problems
perform polynomial-time reductions
design approximation algorithms for NP-hard problems

Referencing modules: NP-Completeness