BAMU TY Computer syllabus

BAMU · Third Year B.E./B.Tech Computer Science and Engineering · NEP 2020

Design and Analysis of Algorithms

PCCT-3 · Semester V · 3 credits · CIA 40 + SEE 60

All notes for this subject
  1. Module 1: Introduction to Algorithms; Analysis Framework

    15 hours

    What makes a good algorithm, space and time complexity, Big-O, Omega and Theta, worst, best and average case (linear versus binary search); analysing non-recursive and recursive algorithms and solving recurrences by substitution and recursion trees.

    Examined in the 60-mark end-semester paper

    • Asymptotic notation: Big-O, Omega and Theta
    • Growth of functions
    • Analysis of binary search
    • Recurrences: substitution, iteration and recursion tree
  2. Module 2: Divide-and-Conquer and Greedy Techniques; Dynamic Programming

    15 hours

    Divide and conquer, the master recurrence, merge sort, quick sort and Strassen's multiplication; the greedy method, fractional knapsack, Huffman coding and Prim's and Kruskal's MSTs; the principle of optimality, memoisation versus tabulation, 0/1 knapsack, LCS, matrix-chain multiplication, Bellman–Ford, Floyd–Warshall and optimal BSTs.

    Examined in the 60-mark end-semester paper

    • Divide and conquer
    • Merge sort
    • Quick sort
    • Strassen's matrix multiplication
    • Fractional knapsack
    • Optimal merge patterns and Huffman coding
    • Dynamic programming
    • Optimal binary search trees
  3. Module 3: Graph Algorithms and Advanced Search Techniques

    15 hours

    BFS and DFS with their complexity, topological sorting and Dijkstra's algorithm with priority queues; backtracking with state-space trees, N-queens, sum of subsets, graph colouring and Hamiltonian cycles; branch and bound, FIFO and least-cost search, and TSP.

    Examined in the 60-mark end-semester paper

    • Dijkstra's single-source shortest paths
    • 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

Module contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).