Scribd Logo
Upload

Welcome to Scribd!

  • 382 views

    Design and Analysis of Algorithms

    Uploaded by

    Neema
    This document outlines the units and topics covered in the Design and Analysis of Algorithms course. The five units cover introduction to algorithms, divide and conquer, greedy, dynamic programming, backtracking, branch and bound, and NP-hard and NP-complete problems. Specific algorithms discussed include merge sort, quick sort, binary search, binary tree traversal, matrix multiplication, Prim's, Dijkstra's, knapsack, and traveling salesman problems. The associated lab covers implementations of quick sort, binary search, tree traversal, dynamic programming algorithms, backtracking, and branch and bound algorithms.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Design and Analysis of Algorithms

    Uploaded by

    Neema
    382 views2 pages
    This document outlines the units and topics covered in the Design and Analysis of Algorithms course. The five units cover introduction to algorithms, divide and conquer, greedy, dynamic programming, backtracking, branch and bound, and NP-hard and NP-complete problems. Specific algorithms discussed include merge sort, quick sort, binary search, binary tree traversal, matrix multiplication, Prim's, Dijkstra's, knapsack, and traveling salesman problems. The associated lab covers implementations of quick sort, binary search, tree traversal, dynamic programming algorithms, backtracking, and branch and bound algorithms.

    Original Title

    DESIGN AND ANALYSIS OF ALGORITHMS

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines the units and topics covered in the Design and Analysis of Algorithms course. The five units cover introduction to algorithms, divide and conquer, greedy, dynamic programming, backtracking, branch and bound, and NP-hard and NP-complete problems. Specific algorithms discussed include merge sort, quick sort, binary search, binary tree traversal, matrix multiplication, Prim's, Dijkstra's, knapsack, and traveling salesman problems. The associated lab covers implementations of quick sort, binary search, tree traversal, dynamic programming algorithms, backtracking, and branch and bound algorithms.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    382 views2 pages

    Design and Analysis of Algorithms

    Uploaded by

    Neema
    This document outlines the units and topics covered in the Design and Analysis of Algorithms course. The five units cover introduction to algorithms, divide and conquer, greedy, dynamic programming, backtracking, branch and bound, and NP-hard and NP-complete problems. Specific algorithms discussed include merge sort, quick sort, binary search, binary tree traversal, matrix multiplication, Prim's, Dijkstra's, knapsack, and traveling salesman problems. The associated lab covers implementations of quick sort, binary search, tree traversal, dynamic programming algorithms, backtracking, and branch and bound algorithms.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 2

    DESIGN AND ANALYSIS OF ALGORITHMS

    Subject Code: MC9223

    UNIT I INTRODUCTION 10
    Fundamentals of algorithmic problem solving – Important problem types –
    Fundamentals of the analysis of algorithm efficiency – analysis frame work –
    Asymptotic notations – Mathematical analysis for recursive and non-recursive
    algorithms.

    UNIT II DIVIDE AND CONQUER METHOD AND GREEDY METHOD 12


    Divide and conquer methodology – Merge sort – Quick sort – Binary search – Binary
    tree traversal – Multiplication of large integers – Strassen’s matrix multiplication –
    Greedy method – Prim’s algorithm – Kruskal’s algorithm – Dijkstra’s algorithm.

    UNIT III DYNAMIC PROGRAMMING 12


    Computing a binomial coefficient – Warshall’s and Floyd’ algorithm – Optimal binary
    search tree – Knapsack problem – Memory functions.

    UNIT IV BACKTRACKING AND BRANCH AND BOUND 14


    Backtracking – N-Queens problem – Hamiltonian circuit problem – Subset sum problem
    – Branch and bound – Assignment problem – Knapsack problem – Traveling
    salesman problem.

    UNIT V NP-HARD AND NP-COMPLETE PROBLEMS 12


    P & NP problems – NP-complete problems – Approximation algorithms for NP-hard
    problems – Traveling salesman problem – Knapsack problem.

    REFERENCES:

    1. Anany Levitin “Introduction to the Design and Analysis of Algorithms” Pearson


    Education 2003.

    2. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, “Introduction to


    algorithms” Prentice Hall 1990.
    MC9229 ALGORITHMS LAB
    LTPC
    0032

    1. Quick Sort
    2. Binary Search
    3. Binary Tree Traversal
    4. Warshall’s Algorithm
    5. Dijkstra’s Algorithm
    6. Prim’s Algorithm
    7. Knapsack Problem – Dynamic Programming
    8. Subset Sum Problem – Backtracking
    9. Travelling salesperson problem – Branch and Bound
    10. Strassen’s matrix multiplication

    You might also like