SUK TY CSE syllabus

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

Computer Algorithms

CSE3102 · Semester V · 4 credits · ISE 10 + mid-semester 30 + ESE 60

3 lectures and 1 tutorial a week, 4 credits.

  1. Unit 1: Divide and Conquer

    8 hours

    What an algorithm is, algorithm specification, recurrence relations, performance analysis and randomised algorithms; divide and conquer: the general method, binary search, finding the maximum and minimum, merge sort, quicksort, the selection algorithm and the analysis of divide-and-conquer algorithms.

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

    • Recurrences: substitution, iteration and recursion tree
    • Randomised algorithms: Las Vegas and Monte Carlo
    • Divide and conquer
    • Analysis of binary search
    • Finding maximum and minimum by divide and conquer
    • Merge sort
    • Quick sort
  2. Unit 2: The Greedy Method

    6 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 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • 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
  3. Unit 3: Backtracking

    5 hours

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

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

    • Backtracking
    • N-queens problem
    • Sum of subsets
    • Hamiltonian cycles by backtracking
    • Graph colouring by backtracking
  4. Unit 4: Dynamic Programming

    6 hours

    The general method; multistage graphs; all-pairs shortest paths; 0/1 knapsack; reliability design; the travelling salesperson problem.

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

    • Dynamic programming
    • Multistage graphs
    • Floyd-Warshall all-pairs shortest paths
    • 0/1 knapsack
    • Reliability design
    • Travelling salesperson by dynamic programming
  5. Unit 5: Basic Traversal and Search Techniques

    7 hours

    Techniques for binary trees and game trees; techniques for graphs: breadth-first and depth-first search and traversal; AND/OR graphs; connected components and spanning trees; biconnected components and depth-first search.

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

    • Game playing and minimax
    • Connected components with BFS and DFS
    • Problem reduction and AO* search
    • Biconnected components and articulation points
  6. Unit 6: NP-Hard and NP-Complete Problems

    4 hours

    Basic concepts; an introduction to NP-hard graph problems.

    Examined in the 60-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

Unit contents are summarised from the official SUK syllabus . AiCanCode.org is not affiliated with Shivaji University, Kolhapur.