SUK TY CSE (DS) syllabus

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

Computer Algorithms

DS3204 · Elective II · Semester VI · 3 credits · ISE 10 + mid-semester 30 + ESE 60

One of the Elective II options.

  1. Unit 1: Divide and Conquer

    6 hours

    Algorithm specification, flow charts and design techniques; recurrence relations, performance analysis and asymptotic notations; binary search, maximum and minimum, merge sort and quick sort.

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

    • Asymptotic notations: big-O, omega and theta
    • Recurrences: substitution and recursion-tree methods
    • Divide and conquer and the master theorem
    • Merge sort and quick sort analysis
  2. Unit 2: The Greedy Method

    7 hours

    Fractional knapsack, job sequencing with deadlines, Prim's and Kruskal's minimum-cost spanning trees, optimal storage on tapes, optimal merge patterns, Huffman codes 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

    • Greedy method: fractional knapsack and Huffman coding
    • Job sequencing with deadlines
    • Minimum spanning trees: Prim's and Kruskal's
    • Optimal storage on tapes
    • Optimal merge patterns
    • Dijkstra's algorithm with priority queues
  3. Unit 3: Dynamic Programming

    8 hours

    The general method compared with divide and conquer; multistage graphs, all-pairs shortest paths, 0/1 knapsack and the travelling salesperson problem.

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

    • Multistage graphs
    • Shortest paths: Bellman-Ford and Floyd-Warshall
    • Dynamic programming: 0/1 knapsack and LCS
    • Travelling salesperson by dynamic programming
  4. Unit 4: Basic Traversal and Search Techniques

    7 hours

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

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

    • BFS, DFS and topological sorting
    • Problem reduction and AND-OR graphs
  5. Unit 5: Backtracking and Branch and Bound

    7 hours

    4- and 8-queens, sum of subsets, knapsack, Hamiltonian cycles and graph colouring by backtracking; branch and bound and job sequencing with deadlines.

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

    • Backtracking and state-space trees
    • N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
    • Branch and bound: FIFO and least-cost search
  6. Unit 6: NP-Hard and NP-Complete Problems

    7 hours

    Basic concepts and NP-hard graph problems; parallel algorithms: computational models and the PRAM, mesh and hypercube.

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

    • P, NP and NP-complete problems
    • Non-deterministic algorithms and NP-hard graph problems
    • The PRAM model and shared-memory algorithms

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