DBATU SY Computer syllabus

DBATU · Second Year B.Tech Computer Engineering · NEP 2020

Design and Analysis of Algorithms

25AF1245PC401 · Semester IV · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60

All notes for this subject
  1. Unit 1: Introduction to Algorithms

    7 hours

    Properties and expression of algorithms; performance analysis and order of growth; asymptotic notation; recurrences by substitution, iteration, recursion tree and the master theorem; heap sort.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Asymptotic notation: Big-O, Omega and Theta
    • Growth of functions
    • Recurrences: substitution, iteration and recursion tree
    • The master method
    • Heap sort
  2. Unit 2: Divide and Conquer

    7 hours

    Binary search, merge sort, quick sort and Strassen's matrix multiplication.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Divide and conquer
    • Analysis of binary search
    • Merge sort
    • Quick sort
    • Strassen's matrix multiplication
  3. Unit 3: Backtracking and Branch and Bound

    7 hours

    N-queens, Hamiltonian cycles, sum of subsets and graph colouring by backtracking; travelling salesperson and the 15-puzzle by branch and bound; the two compared.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Backtracking
    • N-queens problem
    • Sum of subsets
    • Graph colouring by backtracking
    • Hamiltonian cycles by backtracking
    • Branch and bound
    • 15-puzzle and TSP by branch and bound
  4. Unit 4: Greedy Algorithms

    7 hours

    The greedy method; optimal merge patterns and Huffman coding; knapsack; activity selection; job sequencing with deadlines; minimum spanning trees; single-source shortest paths.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • The greedy method
    • Optimal merge patterns and Huffman coding
    • Fractional knapsack
    • Activity selection and job sequencing
    • Kruskal's and Prim's minimum spanning trees
    • Dijkstra's single-source shortest paths
  5. Unit 5: Dynamic Programming and NP-Completeness

    7 hours

    Characteristics of dynamic programming versus divide and conquer; longest common subsequence; matrix-chain multiplication; Bellman–Ford and Floyd–Warshall; the classes P, NP and NP-complete and polynomial-time reduction.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Dynamic programming
    • Longest common subsequence
    • Matrix chain multiplication
    • Bellman-Ford algorithm
    • Floyd-Warshall all-pairs shortest paths
    • P, NP and NP-complete problems

Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).