SUK TY CSE (AI&ML) syllabus

SUK · Third Year B.Tech. Computer Science and Engineering (Artificial Intelligence and Machine Learning) · NEP 2020

Computer Algorithms

AIML3101 · Semester V · 3 credits · ISE 10 + mid-semester 30 + ESE 60

  1. Unit 1: Divide and Conquer

    7 hours

    Algorithm specification, recurrence relations, performance analysis and randomised algorithms; binary search, maximum and minimum, merge sort, quick sort, shell sort and Strassen's matrix multiplication.

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

    • Recurrences: substitution and recursion-tree methods
    • Divide and conquer and the master theorem
    • Merge sort and quick sort analysis
    • Strassen's matrix multiplication
  2. Unit 2: Design and Analysis of Greedy Algorithms

    7 hours

    Knapsack, job sequencing with deadlines, Prim's and Kruskal's spanning trees, optimal storage on tapes and optimal merge patterns; single-source shortest paths: Bellman-Ford, Dijkstra and Floyd-Warshall.

    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
    • Shortest paths: Bellman-Ford and Floyd-Warshall
  3. Unit 3: Dynamic Programming and Applications

    6 hours

    Multistage graphs, all-pairs shortest paths, 0/1 knapsack, reliability design 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
    • Dynamic programming: 0/1 knapsack and LCS
    • Travelling salesperson by dynamic programming
  4. Unit 4: Algorithmic Traversal and Backtracking

    6 hours

    Techniques for binary trees, game trees, B+ trees and red-black trees; BFS and DFS of graphs; backtracking: 8-queens, sum of subsets, knapsack, Hamiltonian cycles and graph colouring.

    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
    • Backtracking and state-space trees
    • N-queens and sum of subsets
    • Graph colouring and Hamiltonian cycles
  5. Unit 5: Foundations of NP-Hard and NP-Complete Problems

    5 hours

    Basic concepts, Cook's theorem, NP-hard graph and scheduling problems.

    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
    • Cook's theorem and polynomial-time reduction
    • Non-deterministic algorithms and NP-hard graph problems
  6. Unit 6: Parallel Algorithms and Computational Models

    5 hours

    Computational models and fundamental techniques: PRAM, mesh and hypercube algorithms.

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

    • Parallel algorithm models
    • 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.