Sunday, February 12, 2012

DAA eBook

Algorithm design is a specific method to create a mathematical process in solving problems.

Mathematics for Algorithmic

    Functions and Relations
    Vectors and Matrices
    Linear Inequalities and Linear Equations

Greedy Algorithms

    Knapsack Problem
        O-I Knapsack
        Fractional Knapsack
    Activity Selection Problem
    Huffman's Codes
    Minimum Spanning Tree
    Kruskal's Algorithm
    Prim's Algorithm
    Dijkstra's Algorithm

Divide & Conquer Algorithms
Dynamic Programming

    Matrix-chain Multiplication
    Knapsack Problem DP Solution
    Activity Selection Problem DP Solution

Amortized Analysis

    Aggregate Method
    Accounting Method
    Potential Method
    Dynamic Table

Hash Table
Binary Search Tree
Graph Algorithms

    Breadth First Search (BFS)
    Depth First Search (DFS)
    Topological Sort
    Strongly Connected Components
    Euler Tour
    Generic Minimum Spanning Tree
    Kruskal's Algorithm
    Prim's Algorithm
    Single Source Shortest Path
        Dijkstra's Algorithm
        Bellman-Ford Algorithm

String Matching

    Naïve String Matching
    Knuth-Morris-Pratt Algorithm
    Boyer-Moore Algorithm


    Bubble Sort
    Insertion Sort
    Selection Sort
    Shell Sort
    Heap Sort
    Merge Sort
    Quick Sort

Linear-Time Sorting

    Counting Sort
    Radix Sort
    Bucket Sort

Computational Geometry
Computational Complexity

    Information-Theoretic Argument
    Adversary Argument
    NP-Completeness And Reduction

Approximate Algorithms

    Vertex Cover
    The Traveling Salesman Problem

Linear Programming

--> Download Link <--

>> click here for DAA notes