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
- Learn some useful algorithm design techniques and data structures.
Topics
- Motivated by programming contest questions.
- Selected from standard techniques and data structures.
- Open to adjustments based on interest and prior knowledge.
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
- 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)
Contact me!
- 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.