MCA-201
Design and Analysis of Algorithms
How to judge an algorithm and how to build one — asymptotic analysis, recurrences, the four design paradigms, and NP-completeness.
- Semester
- Semester 3
- Credits
- 4
- Scheme
- 3 lectures + 1 tutorial a week
- Contact hours
- 45 across four units
- Category
- Core
What the paper is
Design and Analysis of Algorithms is the theoretical centre of the degree, and it is organised around a single question asked repeatedly: given a problem, which technique applies, and what does it cost? Unit I gives you the cost model, Units II and III give you the techniques — divide and conquer, greedy, dynamic programming — and Unit IV asks what happens when no efficient technique exists at all.
It carries four credits and a tutorial hour, one of only two papers in the later semesters to do so, and the tutorial is where the recurrences get solved and the algorithms get traced. This is not a paper that can be revised by reading.
Unit IV is the part with no equivalent anywhere else in the syllabus. Reducibility, NP-completeness proofs and Cook's theorem are about the limits of computation rather than about writing better code, and they need a different kind of attention — closer to the proof work in Discrete Structures than to the rest of this paper.
What to concentrate on
- The master theorem is the single highest-return thing to memorise, together with enough substitution and recurrence-tree practice to handle the cases it does not cover.
- For dynamic programming, learn the table, not the story. Matrix-chain multiplication, longest common subsequence, 0/1 knapsack and Floyd-Warshall are all asked as “fill this table on this input”, and the recurrence relation is where the marks are.
- Know the difference between NP-complete and NP-hard precisely enough to state it in one sentence, and be able to sketch one reduction — 3SAT to vertex cover or clique is the usual choice. That covers most of what Unit IV asks.
Syllabus, unit by unit
Summarised from the approved scheme. Hours are the contact hours the scheme allots, which is a fair guide to where the marks sit.
Unit I · Performance analysis and recurrences
9 hours- Algorithm specification, space and time complexity, correctness of algorithms
- Growth of functions, asymptotic notations and their types
- The concept of randomised algorithms
- Recurrences: substitution, iteration, master and recurrence-tree methods
Unit II · Divide and conquer, sorting and string matching
12 hours- Divide and conquer: comparative analysis of sorting and searching techniques, Strassen's matrix multiplication
- Sorting in linear time: counting sort, bucket sort, radix sort
- String matching: naive algorithm, finite automata, Knuth-Morris-Pratt, Rabin-Karp
- Red-black trees, disjoint sets and their implementation, medians and order statistics
Unit III · Greedy algorithms and dynamic programming
12 hours- Greedy algorithms: activity selection, fractional knapsack, job sequencing with deadlines, Huffman coding
- Analysis and correctness of Prim's, Kruskal's and Dijkstra's algorithms
- Dynamic programming: matrix-chain multiplication, longest common subsequence, Bellman-Ford
- Analysis and correctness of Floyd-Warshall, optimal binary search trees, 0/1 knapsack, the network flow problem
Unit IV · Backtracking, branch and bound, and complexity classes
12 hours- Backtracking: n-queens, Hamiltonian circuit, subset-sum, graph colouring
- Branch and bound: the assignment problem, travelling salesman problem
- Computability, polynomial-time verification, NP-completeness
- Complexity classes: reducibility, NP-completeness proofs, NP-complete and NP-hard, problem classification
- Circuit satisfiability, 3SAT, vertex cover, clique, Cook's theorem
How it is examined
- Question 1 is compulsory, covers the whole syllabus, and is made of objective or short-answer questions. It carries 12 marks.
- The rest of the paper is four units matching the four above. Each unit sets two questions and you attempt one, so there are four more answers at 12 marks each.
- Examiners are asked to map every question to a course outcome using Bloom's taxonomy, which is why questions are phrased as “apply”, “analyse” or “evaluate” rather than only “explain”.
The pass mark is 40 out of 100 in every paper.
Learning objectives
- Understanding the important concepts of algorithm design and their analysis
- Analysing the efficiency of alternative algorithmic solutions
- Understanding the divide and conquer, greedy, dynamic, backtracking and branch and bound paradigms
- Identifying appropriate data structures and design techniques and assessing their impact on performance
Assumed beforehand
- Programming skills
- Discrete Structures
- Data Structures
Paired in the scheme with MCA-261 Design and Analysis of Algorithms Lab.
Books it is taught from
- TB1T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms”, PHI, 2nd edition, 2006
- TB2S. Dasgupta, C. Papadimitriou and U. Vazirani, “Algorithms”, McGraw Hill Higher Education, 1st edition, 2017
- TB3J. Kleinberg and E. Tardos, “Algorithm Design”, Pearson Education, 2nd edition, 2009
Notes for MCA-201
Lecture notes, question papers and assignments filed against MCA-201 are in the library. Everything there has been checked by a moderator before it appears, and an account is free — new ones are approved by hand, which is what keeps the shelf clean.