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