François Pitt <francois.pitt@utoronto.ca>

(Department of Computer Science, University of Toronto)

- Learn some useful algorithm design techniques and data structures.

- Motivated by programming contest questions.
- Selected from standard techniques and data structures.
- Open to adjustments based on interest and prior knowledge.

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)

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)

- 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)

- Wikipedia is a good place to get started.
- Introduction to
Algorithms (2
^{nd}or 3^{rd}edition) by Cormen, Leiserson, Rivest & Stein is known as "the bible" for algorithms and data structures!

However, beware: it is an awesome reference, but**not**a good book for novice programmers to pick up and learn from. - Data Structures and Algorithms with Object-Oriented Design Patterns in Java is a free online textbook that covers most of the topics above.

- The DWITE Online Computer Programming Contest
- The ECOO Programming Contest
(
*ECOO*is the Educational Computing Organization of Ontario) - The University of Waterloo's CCC (Canadian Computing Competition)

- Please don't hesitate to contact me (see my email address above) if you have any questions about algorithms or data structures. I would be very happy to help you out, whether it is with technical details or to discuss issues of pedagogy for this material.
- At the same time, I would also love to hear from you if you have any interesting experiences or ideas to share regarding the material or its pedagogy!

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>

last updated at 08:24 (EST) on Thu 5 Mar 2015

Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.