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.
Unit 1: Divide and Conquer
6 hoursAlgorithm 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
Unit 2: The Greedy Method
7 hoursFractional 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
Unit 3: Dynamic Programming
8 hoursThe 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
Unit 4: Basic Traversal and Search Techniques
7 hoursTechniques 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
Unit 5: Backtracking and Branch and Bound
7 hours4- 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
Unit 6: NP-Hard and NP-Complete Problems
7 hoursBasic 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.