PAHSU TY CSE syllabus

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

Design and Analysis of Algorithms

CSEPCC-07 · Semester V · 3 credits · ISE 30 + ESE 70

  1. Unit 1: Introduction

    8 hours

    Algorithm specification and pseudocode conventions; recursive algorithms; performance analysis: space and time complexity, worst-, best- and average-case complexity, asymptotic notations and performance measurement.

    Examined in the 70-mark end-semester paper

  2. Unit 2: Divide and Conquer

    7 hours

    The general method; binary search; finding the maximum and minimum; quick sort, selection sort and merge sort.

    Examined in the 70-mark end-semester paper

    • Divide and conquer
    • Analysis of binary search
    • Finding maximum and minimum by divide and conquer
    • Quick sort
    • Merge sort
    • Analysis of selection and insertion sort
  3. Unit 3: The Greedy Method

    8 hours

    The general method; the knapsack problem; job sequencing with deadlines; Prim's and Kruskal's minimum-cost spanning trees; optimal storage on tapes; optimal merge patterns; single-source shortest paths.

    Examined in the 70-mark end-semester paper

    • The greedy method
    • Fractional knapsack
    • Activity selection and job sequencing
    • Kruskal's and Prim's minimum spanning trees
    • Optimal storage on tapes
    • Optimal merge patterns and Huffman coding
    • Dijkstra's single-source shortest paths
  4. Unit 4: Dynamic Programming

    8 hours

    The general method; multistage graphs; all-pairs shortest paths; optimal binary search trees; 0/1 knapsack; reliability design; the travelling salesperson problem; flow shop scheduling.

    Examined in the 70-mark end-semester paper

    • Dynamic programming
    • Multistage graphs
    • Floyd-Warshall all-pairs shortest paths
    • Optimal binary search trees
    • 0/1 knapsack
    • Reliability design
    • Travelling salesperson by dynamic programming
    • Flow shop scheduling: Johnson's rule
  5. Unit 5: Backtracking

    7 hours

    The general method; the 8-queens problem; sum of subsets; the knapsack problem; Hamiltonian cycles; graph colouring.

    Examined in the 70-mark end-semester paper

    • Backtracking
    • N-queens problem
    • Sum of subsets
    • Hamiltonian cycles by backtracking
    • Graph colouring by backtracking
  6. Unit 6: NP-Hard and NP-Complete Problems

    7 hours

    Tractable and intractable problems; computability and the halting problem; the classes P and NP, NP-complete and NP-hard; standard NP-complete problems and basic NP-hard problems.

    Examined in the 70-mark end-semester paper

Unit contents are summarised from the official PAHSU syllabus . AiCanCode.org is not affiliated with Punyashlok Ahilyadevi Holkar Solapur University (PAHSU).