SGBAU TY CSE (DS) syllabus

SGBAU · Third Year B.E. Computer Science and Engineering (Data Science) · NEP 2020

Design and Analysis of Algorithm

6DS232PC · Semester VI · 3 credits · IE 40 + ESE 60

All notes for this subject
  1. Unit 1: Algorithm Analysis and Iterative Design

    6 hours

    Algorithms and loops, efficiency, estimating and specifying execution time, Big-O, Big-Ω and Big-Θ, an overview of strategies, and design using recursion.

    Examined in the 60-mark end-semester paper

    • What makes a good algorithm
    • Space and time complexity
    • Asymptotic notations: big-O, omega and theta
    • Analysing non-recursive algorithms
    • Recurrences: substitution and recursion-tree methods
  2. Unit 2: Divide and Conquer

    6 hours

    The divide-and-conquer strategy, multiplication algorithms and their analysis, the triangulation and convex-hull problems, the drawbacks of divide and conquer, and timing analysis.

    Examined in the 60-mark end-semester paper

    • Divide and conquer and the master theorem
    • Strassen's matrix multiplication
    • Convex hull and large-integer multiplication by divide and conquer
  3. Unit 3: Greedy Methods

    6 hours

    The greedy strategy, the knapsack problem, job sequencing with deadlines, minimum spanning trees by Prim's and Kruskal's algorithms, and Dijkstra's shortest paths.

    Examined in the 60-mark end-semester paper

    • Greedy method: fractional knapsack and Huffman coding
    • Job sequencing with deadlines
    • Minimum spanning trees: Prim's and Kruskal's
    • Dijkstra's algorithm with priority queues
  4. Unit 4: Dynamic Programming

    6 hours

    Dynamic programming, multistage graphs, the travelling-salesman problem, matrix-chain multiplication, the longest common subsequence, optimal polygon triangulation and single-source shortest paths.

    Examined in the 60-mark end-semester paper

    • Multistage graphs
    • Travelling salesperson by dynamic programming
    • Matrix chain multiplication and optimal BSTs
    • Dynamic programming: 0/1 knapsack and LCS
    • Shortest paths: Bellman-Ford and Floyd-Warshall
  5. Unit 5: Backtracking

    6 hours

    Combinatorial search, search and traversal methods, the backtracking strategy and framework, and typical state-space trees and their applications.

    Examined in the 60-mark end-semester paper

    • Backtracking and state-space trees
    • N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
  6. Unit 6: Algorithm Efficiency and Complexity Classes

    6 hours

    Polynomial and non-polynomial algorithms, worst- and average-case analysis, the efficiency of recursion, the complexity of sorting algorithms, and time–space trade-offs.

    Examined in the 60-mark end-semester paper

    • P, NP and NP-complete problems
    • Best, worst and average-case analysis
    • Merge sort and quick sort analysis

Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).