Analysis & Design of Algorithms Syllabus — Government College of Engi…
Full syllabus, topics and curated resources for Analysis & Design of Algorithms (Government College of Engineering and Technology, Jammu).
Algorithm design paradigms, complexity analysis, and NP-completeness theory
- Subject code: CST-3501
- University: Government College of Engineering and Technology, Jammu
- Course: BE (2022 onwards)
- Branch: CE
- Semester: 5
Analysis & Design of Algorithms syllabus
Unit 1: Introduction to Algorithms
- Analysing the Performance of an Algorithm
- Space/Time Complexity
- Asymptotic Analysis
- Recurrence Relations
Unit 2: Heap and Hash Tables
- Representing a Heap
- Building a Heap
- Operations on Heaps
- Applications - Priority Queues Using Heaps
- HeapSort
- Hash Table and Hashing Functions
- Resolving Collision by Separate Chaining
- Open Addressing
- Quadratic Probing
- Double Hashing
- Rehashing
Unit 3: Lower Bound Theory
- Lower Bounds - Comparison Trees for Searching and Sorting
- Arguments through Reduction
- Parallel Comparison Trees
- Oracle and Adversary Arguments
Unit 4: NP-Completeness
- Introduction to NP-Completeness
- Deterministic and Non-Deterministic Algorithms
- Polynomial Time Algorithms
- P, NP and NP-Hard Classes
- NP-Complete Classes
- Reducibility and NP-Completeness
- Satisfiability Problem
- Cook's Theorem
- Introduction to Approximation Algorithm
Unit 5: Divide and Conquer
- Introduction to Divide and Conquer
- Binary Search
- Finding the Maximum and Minimum
- Merge Sort
- Quick Sort
- Selection Sort
- Strassen's Matrix Multiplication
Unit 6: Greedy Method
- Introduction to Greedy Method
- Single Source Shortest Path
- Activity Selection Problem
- Knapsack Problem (Greedy)
- Task Scheduling Problem
- Optimal Merge Patterns
Unit 7: Dynamic Programming
- Introduction to Dynamic Programming
- Memoization
- Multistage Graphs
- 0/1 Knapsack Problem (Dynamic Programming)
- Longest Common Subsequence