﻿ Algorithms and Data Structures Tutorials and Lecture Notes

# 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 post-conditions 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, Red-Black trees, AVL trees, General n-ary 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, Red-Black Trees, Skip Lists, External Sorts, B-Trees. 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 2-D Maxima Problem, Summations and Analyzing Programs with Loops, the 2-D 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, Divide-and-conquer (Intro), Matrix multiplcation, The Greedy method; Activity selection problem, Huffman Codes, Single-source shortest path problems, Minimum Spanning Trees, Dynamic Programming; Matrix chain-multiplcation, Longest Common subsequences, All-Pairs shortest paths, On lower bounds, Sorting in Linear time, Acyclicity testing, Strongly connected components, MST:Kruskal's Alg, Single source shortest paths:Belman-Ford alg, SPs in DAGs, Maximum flow. The Ford-Fulkerson method, Cuts on Network flows, Planar graphs, Colouring of Planar graphs, Approximation Algorithms, Approximation Algorithms (cont), Heuristics, Pseudo-polynomial 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, Breadth-First and Depth-First 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, NP-Completeness : 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 k-center problem, Recurrences and Generating Functions, Articulation Points and Biconnected Components, Network Flows and Matching, The 0-1 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 complexity-classes, probabilistic computation, pseudorandom number generators, parallel computation, relativized computation, interactive proofs. Linear Programming Johan Hastad A short document on linear programming.