Algorithms Directory

Lecture Notes

Title

Author

Description

Data Structures and
Algorithms
(No
Frames)

John Morris

Complete data structures and algorithms course. This course is taught at the University
Of Western Australia. The course teaches the following topics : Objects and ADTs,
Constructors and destructors, Data Structure , Methods, Pre and postconditions
C conventions, Error Handling, Arrays, Lists, Stacks, Stack Frames, Recursion, Sequential
Searches, Binary Search , Trees, Complexity, Queues, Priority Queues , Heaps, Bubble
, Heap Sort, Quick Sort , Bin Sort, Radix Sort, Searching Revisited, RedBlack trees,
AVL trees, General nary trees, Hash Tables, Dynamic Algorithms, Fibonacci Numbers
, Binomial Coefficients, Optimal Binary Search Trees, Matrix Chain Multiplication,
Longest Common Subsequence, Optimal Triangulation , Graphs , Minimum Spanning Tree
, Dijkstra's Algorithm , Huffman Encoding , FFT , Hard or Intractable Problems,
Eulerian or Hamiltonian Paths , Travelling Salesman's Problem

Sorting and Searching
Algorithms
(No Frames)

Thomas Niemann

A small guide on the following topics : Arrays, Linked Lists, Timing Estimates,
Insertion sort, Shell sort, Quicksort, Hash Tables, Binary Search Trees, RedBlack
Trees, Skip Lists, External Sorts, BTrees.

AVL Trees
(No Frames)

Brad Appleton

A tutorial on AVL trees. The tutorial is part of a freely available public domain
AVL tree library written in C++. The full C++ source code distribution may be found
in the tutorial.

Animated
Algorithms

Woi Ang, Chein Wei Tan, Mervyn Ng

Collection of animated algorithms of the following algorithms : Insertion Sort,
QuickSort, Bin Sort, Radix Sort, Priority Queue Sorting, Hash Tables Searching,
Optimal Binary Search Tree, Huffman Encoding, Dijkstra's Shortest Path, Minimum
Spanning Tree ( MST ).


Downloads

Title

Author

Description

Algorithms CMSC 251

Dave Mount

A book on the following topics : Course Introduction, Analyzing Algorithms: the
2D Maxima Problem, Summations and Analyzing Programs with Loops, the 2D Maxima
revisited and Asymptotics, Asymptotics, Divide and Conquer and MergeSort, Recurrences,
Medians and Selection, Long Integer Multiplication, Heaps and HeapSort, HeapSort
Analysis and Partitioning, QuickSort, Lower Bounds for Sorting, Linear Time Sorting,
Introduction to Graphs, Graphs, Graph Representation and BFS, All Pairs Shortest
Paths, Floyd Warshall Algorithm, Longest Common Subsequence, Chain Matrix Multiplication,
NP Completeness: General Introduction, NP Completeness and Reductions

Algorithms COMP 3001

Antonios Symvonis

A collection of lecture notes covering the following topics: Administrivia, Introduction
to algorithms, Introduction to algorithms (cont), Graphs, Breadth First Search,
Depth First Search Topological Sorting, Divideandconquer (Intro), Matrix multiplcation,
The Greedy method; Activity selection problem, Huffman Codes, Singlesource shortest
path problems, Minimum Spanning Trees, Dynamic Programming; Matrix chainmultiplcation,
Longest Common subsequences, AllPairs shortest paths, On lower bounds, Sorting
in Linear time, Acyclicity testing, Strongly connected components, MST:Kruskal's
Alg, Single source shortest paths:BelmanFord alg, SPs in DAGs, Maximum flow. The
FordFulkerson method, Cuts on Network flows, Planar graphs, Colouring of Planar
graphs, Approximation Algorithms, Approximation Algorithms (cont), Heuristics, Pseudopolynomial
algorithms

Data Structures CMSC 420

Dave Mount

A document covering many data structures topics. Great for most university courses.
The document has 117 pages.

Design and Analysis of Computer
Algorithms CMSC 451

Dave Mount

A book on the following subjects : Asymptotics and Summations, Divide and Conquer
and Recurrences, Sorting, Dynaminc Programming, Longest Command Subsequence, Chain
Matrix Multiplication, Memoization and Triangulation, Greedy Algorithms, Huffman
Coding, Activity Selection and Fractional Knapsack, Definitions and Representations,
BreadthFirst and DepthFirst Search, Topological Sort and Strong Components, Minimum
Spanning Trees and Kruskal's Algorithm, Prim's and Baruvka's Algorithms for MST's,
Dijkstra's Shortest Path Algorithms, Bellman Ford and Floyd Marshall shortes path,
NPCompleteness : Languages and NP, Reductions, Cook's Theorem and Other Reducations,
Clique, Vertex Cover and Dominating Set, Hamiltonian Path, Approximation Algorithms
: VC and TSP, Set Cover and Bin packing, the kcenter problem, Recurrences and Generating
Functions, Articulation Points and Biconnected Components, Network Flows and Matching,
The 01 Knapsack problem, Subset Sum & Approximation.

Graph Theory

Prof. Even

A book covering many graph theory topics.

Advanced Algorithms

Johan Hastad

A document on the following topics : notation and basics, primality testing, factoring
integers, discrete logarithms, quantum computation, factoring polynomials in finite
fields, factoring polynomials over integers, Lovaszs lattics basis reduction algorithm,
multiplication of large integers, matrix multiplication, matrix flow, Bipartite
matching.

Complexity Theory

Johan Hastad

A document containing on following topics: recursive functions, efficient computation,
hierarchy theorems, the complexity classes L, P and PSPACE, nondeterministic computation,
relations among complexity classes, complete problems, constructing more complexityclasses,
probabilistic computation, pseudorandom number generators, parallel computation,
relativized computation, interactive proofs.

Linear Programming

Johan Hastad

A short document on linear programming.



