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
Unit 1: Divide and Conquer
7 hoursAlgorithm 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
Unit 2: Design and Analysis of Greedy Algorithms
7 hoursKnapsack, 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
Unit 3: Dynamic Programming and Applications
6 hoursMultistage 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
Unit 4: Algorithmic Traversal and Backtracking
6 hoursTechniques 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
Unit 5: Foundations of NP-Hard and NP-Complete Problems
5 hoursBasic 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
Unit 6: Parallel Algorithms and Computational Models
5 hoursComputational 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.