CmSc 250 Lecture notes

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) (PDF)
Basic Algorithm Analysis
- Big-Oh notation (PPT frames) (PPT printable) (PDF)
- Running time calculations (PPT frames) (PPT printable) (PDF)
- Logarithms in running time (PPT frames) ( PPT printable) (PDF)
  Summary of Big-Oh notation (PDF)
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

Shell Sort

Heapsort

Recurrence relations
Mergesort

Quick Sort

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 )

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