BAMU TY IT syllabus

BAMU · Third Year B.E./B.Tech Information Technology · 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; Analysis Framework

    15 hours

    What makes a good algorithm; space and time complexity; Big-O, Omega and Theta; worst, best and average cases (linear versus binary search); analysing non-recursive algorithms, setting up recurrences, and the substitution and recursion-tree methods.

    Examined in the 60-mark end-semester paper

    • Time and space complexity, asymptotic notation
    • Step-count method and analysing loops
    • Recurrence relations and the master theorem
    • Linear and binary search
  2. Module 2: Divide-and-Conquer and Greedy Techniques; Dynamic Programming

    15 hours

    Divide and conquer with merge sort, quick sort and Strassen's multiplication; the greedy method with fractional knapsack, Huffman coding and Prim's and Kruskal's MSTs; dynamic programming with memoisation and 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 and quick sort
    • Divide and conquer matrix multiplication
    • Greedy: activity selection and fractional knapsack
    • Huffman coding
    • Dynamic programming: 0/1 knapsack
    • Longest common subsequence
    • Matrix chain multiplication
    • Bellman-Ford algorithm
  3. Module 3: Graph Algorithms and Advanced Search Techniques; Backtracking and Branch and Bound

    15 hours

    BFS and DFS, topological sorting and Dijkstra's algorithm with priority queues; backtracking for N-queens, sum of subsets, graph colouring and Hamiltonian cycles; branch and bound, FIFO versus least-cost search, and the travelling salesperson problem.

    Examined in the 60-mark end-semester paper

    • Graph representation, BFS and DFS
    • Topological sort
    • Shortest path algorithms
    • Backtracking: N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
    • Branch and bound

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