← Back to MCS-211

PYQ Analysis

MCS-211 · 9 papers

Block Weightage

Block 1 — Introduction to Algorithms

~23 marks/paper · 9/9 papers · 4 units

23%

Block 2 — Design Techniques-I

~31 marks/paper · 9/9 papers · 3 units

31%

Block 3 — Design Techniques-II

~27 marks/paper · 9/9 papers · 3 units

27%

Block 4 — NP-Completeness & Approximation Algorithm

~19 marks/paper · 9/9 papers · 3 units

19%

Unit Breakdown

Unit 1 — Basics of an Algorithm and its Properties

Must

~8 marks · 90% frequency

Definition & Characteristics of AlgorithmAlgorithm Design StepsEuclid's GCD AlgorithmMathematical InductionBinary Exponentiation

Unit 2 — Asymptotic Bounds

Must

~10 marks · 95% frequency

Big-O Notation (Upper Bound)Big-Omega Notation (Lower Bound)Big-Theta Notation (Tight Bound)Growth Rate OrderingTime Complexity of Code Fragments

Unit 3 — Complexity Analysis of Simple Algorithms

~5 marks · 70% frequency

Best, Worst, Average Case AnalysisComplexity of Searching AlgorithmsComplexity of Sorting AlgorithmsHorner's Rule for Polynomial Evaluation

Unit 4 — Solving Recurrences

Must

~10 marks · 95% frequency

Substitution MethodRecursion Tree MethodMaster Theorem (3 Cases)QuickSort Recurrence

Unit 1 — Greedy Technique

Must

~15 marks · 100% frequency

Greedy Approach & ActivitiesFractional Knapsack ProblemTask Scheduling with DeadlinesHuffman CodingKruskal's MST AlgorithmPrim's MST Algorithm

Unit 2 — Divide and Conquer Technique

Must

~12 marks · 95% frequency

Merge SortQuick SortBinary SearchStrassen's Matrix MultiplicationKaratsuba AlgorithmFinding ith Smallest (Selection)

Unit 3 — Graph Algorithm-1

Must

~15 marks · 100% frequency

Graph Terminology & RepresentationBFS (Breadth First Search)DFS (Depth First Search)Topological SortStrongly Connected Components

Unit 1 — Graph Algorithms-II

Must

~12 marks · 100% frequency

Dijkstra's Shortest Path AlgorithmBellman-Ford AlgorithmFloyd-Warshall AlgorithmFord-Fulkerson / Bipartite Matching

Unit 2 — Dynamic Programming Technique

Must

~12 marks · 90% frequency

Principle of OptimalityMatrix Chain Multiplication0/1 Knapsack ProblemBinomial CoefficientHorner's Method (polynomial evaluation)

Unit 3 — String Matching Algorithms

~8 marks · 65% frequency

Naive String MatchingKMP Algorithm & LPS ArrayRabin-Karp Algorithm

Unit 1 — Introduction to Complexity Classes

Must

~8 marks · 85% frequency

P Class ProblemsNP Class ProblemsNP-Complete ProblemsTractable vs Intractable Problems

Unit 2 — NP-Completeness and NP-Hard Problems

Must

~8 marks · 85% frequency

Cook-Levin Theorem & SAT ProblemCNF-SatisfiabilityCLIQUE & Vertex Cover ProblemNP-Hard vs NP-Complete Difference

Unit 3 — Handling Intractability

~5 marks · 45% frequency

Approximation AlgorithmsBacktrackingBranch and Bound

Most Repeated Model Questions