ACSE 2015: Algorithms and Data Structures

Saturday 28 February 2015
François Pitt <francois.pitt@utoronto.ca>
(Department of Computer Science, University of Toronto)

What to expect

Goal

Topics

Algorithms

General techniques for solving problems

Brute Force:
A.k.a. "try every possibility"
(Brute Force on Wikipedia)
Graph Traversal:
Systematic way to carry out a task for each node in a graph
(Depth-First Search on Wikipedia; Breadth-First Search on Wikipedia)
Dynamic Programming:
Solving recursive optimization problems efficiently
(Dynamic Programming on Wikipedia)
Greedy Algorithms:
Repeatedly make short-sighted decisions
(Greedy Algorithms on Wikipedia)
Divide-and-Conquer:
Using recursion to solve problems
(Divide-and-Conquer Algorihtms on Wikipedia)

Data Structures

General ways to organize data and manipulate it efficiently

Heaps and Priority Queues:
To store and process items in FIFO order, with priorities
(Heaps on Wikipedia; Priority Queues on Wikipedia)
Hash Tables (incomplete):
To store and process unordered items efficiently
(Hash Tables on Wikipedia)

Going Further...

Balanced Search Trees:
To store and process ordered items
(Self-Balancing Search Trees on Wikipedia)
Disjoint sets (a.k.a. union/find):
Useful to solve Minimum Spanning Tree problem
(Union-Find on Wikipedia)
Linear programming:
Changing a problem's representation in order to solve it
(Linear Programming on Wikipedia)
Amortized analysis:
When worst-case analysis is misleading
(Amortized Analysis on Wikipedia)
NP-completeness:
How to tell problems cannot be solved efficiently
(NP-Completeness on Wikipedia)

General references

Programming contests

Contact me!


© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Creative Commons License Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.