CmSc 250 Intro to Algorithms
Lecture Notes
Based on
Mark Allen Weiss
,
Data Structures and Algorithm Analysis in Java.
Addison-Wesley, 2nd edition, 2007. ISBN 0-321-37013-9
Mathematical review
(
PPT frames
) (
PPT printable
)
Basic Algorithm Analysis
Big-Oh notation
(
PPT frames
) (
PPT printable
)
Running time calculations
(
PPT frames
) (
PPT printable
)
Logarithms in running time
(
PPT frames
) (
PPT printable
)
Summary of Big-Oh notation
Data structures
Lists and Stacks
(
PPT frames
) (
PPT printable
)
Queues
(
PPT frames
) (
PPT printable
)
Trees
(
PPT frames
) (
PPT printable
)
Binary search trees
, (
PPT frames
) (
PPT printable
)
Digital / Radix trees
(
PPT frames
) (
PPT printable
)
AVL trees
(
PPT frames
) (
PPT printable
)
Hash tables
Hash functions, Hash tables
(
PPT frames
) (
PPT printable
)
Collision resolution: Separate chaining
(
PPT frames
) (
PPT printable
)
Collision resolution: Open Addressing. Extendible hashing
, (
PPT frames
) (
PPT printable
)
Priority Queues
(
PPT frames
) (
PPT printable
)
Applications of Priority Queues - the Selection Problem
(
PPT frames
) (
PPT printable
)
Sorting Algorithms
Insertion Sort
(
PPT frames
) (
PPT printable
)
Shell Sort
(
PPT frames
) (
PPT printable
)
Heapsort
(
PPT frames
) (
PPT printable
)
Recurrence relations
Mergesort
(
PPT frames
) (
PPT printable
)
Quick Sort
(
PPT frames
) (
PPT printable
)
External Sort
Review of sorting algorithms
Elementary Graph Algorithms
Graphs: Basic concepts
(
PPT frames
) (
PPT printable
)
Graphs: Topological sort
(
PPT frames
) (
PPT printable
)
Shortest Path Algorithms
(
PPT frames
) (
PPT printable
)
Spanning Trees, Prim's algorithm, Kruskal's algorithm
(
PPT frames
) (
PPT printable
)
Scheduling Networks
(
PPT frames
) (
PPT printable
)
Breadth-First and Depth-First Search in a Graph
(
PPT frames
) (
PPT printable
)
Applications of Depth-First Search: Connectivity
(
PPT frames
) (
PPT printable
)
Applications of Depth-First Search in a Graph - Eulerian Graphs
Summary of Graph Algorithms
(
PPT frames
) (
PPT printable
)
Algorithm Design Techniques (Summary)
(
PPT frames
) (
PPT printable
)
Backtracking
(
PPT frames
) (
PPT printable
)
Complexity Issues
(
PPT frames
) (
PPT printable
)
Conclusion
Created by
Lydia Sinapova