DBATU SY IT syllabus

DBATU · Second Year B.Tech Information Technology · NEP 2020

Analysis of Algorithms

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

All notes for this subject
  1. Unit 1: Introduction

    7 hours

    Instruction counts and growth functions; why time and space are analysed; O, Θ and Ω notation; solving recurrences by substitution, the master theorem and recursion trees.

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

    • Time and space complexity, asymptotic notation
    • Step-count method and analysing loops
    • Recurrence relations and the master theorem
  2. Unit 2: Divide and Conquer and Greedy Algorithms

    7 hours

    Binary search, finding maximum and minimum, merge sort, quick sort and Strassen's multiplication; greedy knapsack, job sequencing, optimal storage on tapes, optimal merge patterns and single-source shortest paths.

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

    • Finding maximum and minimum by divide and conquer
    • Divide and conquer: merge sort and quick sort
    • Divide and conquer matrix multiplication
    • Greedy: activity selection and fractional knapsack
    • Job sequencing with deadlines
    • Optimal storage on tapes
    • Optimal merge patterns
    • Shortest path algorithms
  3. Unit 3: Dynamic Programming

    7 hours

    Multistage graphs; all-pairs shortest paths; 0/1 knapsack; the travelling salesperson problem; longest common subsequence.

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

    • Multistage graphs
    • Floyd–Warshall algorithm
    • Dynamic programming: 0/1 knapsack
    • Travelling salesman by dynamic programming
    • Longest common subsequence
  4. Unit 4: Graph Algorithms

    7 hours

    DFS, BFS and topological sort; minimum spanning trees with Kruskal's and Prim's algorithms.

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

    • Graph representation, BFS and DFS
    • Topological sort
    • Minimum spanning trees: Prim's and Kruskal's
  5. Unit 5: Backtracking, Branch and Bound, and NP Theory

    7 hours

    N-queens, sum of subsets and graph colouring; the branch-and-bound strategy; P, NP, NP-hard and NP-complete problems and reduction.

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

    • Backtracking: N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
    • Branch and bound
    • P, NP, NP-hard 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).