GUG TY CSE syllabus

GUG · Third Year B.Tech. Computer Science and Engineering · NEP 2020

Design and Analysis of Algorithms

STPCCCSE503 · Semester V · 4 credits · IE 10 + mid-semester 10 + ESE 80

4 credits with its lab.

All notes for this subject
  1. Unit 1: Introduction

    9 hours

    Algorithms and pseudocode; performance analysis: space and time complexity; asymptotic notation: big-O, omega and theta; recurrences; iterative sorting and searching algorithms.

    Examined in the 80-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
    • Analysis of selection and insertion sort
  2. Unit 2: Divide and Conquer and the Greedy Method

    9 hours

    Divide and conquer: the general method and the analysis of binary search, quick sort and merge sort. The greedy method: job sequencing with deadlines, the fractional knapsack, minimum-cost spanning trees, single-source shortest paths and Huffman codes.

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

    • Divide and conquer
    • Analysis of binary search
    • Quick sort
    • Merge sort
    • The greedy method
    • Activity selection and job sequencing
    • Fractional knapsack
    • Kruskal's and Prim's minimum spanning trees
    • Dijkstra's single-source shortest paths
    • Optimal merge patterns and Huffman coding
  3. Unit 3: Dynamic Programming

    9 hours

    The general method; longest common subsequence, matrix chain multiplication, optimal binary search trees, the 0/1 knapsack, all-pairs shortest paths and the travelling salesperson problem.

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

    • Dynamic programming
    • Longest common subsequence
    • Matrix chain multiplication
    • Optimal binary search trees
    • 0/1 knapsack
    • Floyd-Warshall all-pairs shortest paths
    • Travelling salesperson by dynamic programming
  4. Unit 4: Backtracking and Branch and Bound

    9 hours

    Backtracking: the n-queens problem, sum of subsets, graph colouring and Hamiltonian cycles. Branch and bound: the travelling salesperson problem and the 0/1 knapsack by LC and FIFO branch and bound.

    Examined in the 80-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
    • 0/1 knapsack by LC and FIFO branch and bound
  5. Unit 5: NP-Hard and NP-Complete Problems

    9 hours

    Basic concepts; non-deterministic algorithms; the NP-hard and NP-complete classes; Cook's theorem.

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

    • Non-deterministic algorithms and Cook's theorem
    • P, NP and NP-complete problems
    • NP-completeness reductions: vertex cover, 3-CNF SAT, clique and Hamiltonian cycle

Unit contents are summarised from the official GUG syllabus . AiCanCode.org is not affiliated with Gondwana University, Gadchiroli.