MCA 201 Design and Analysis of Algorithms Notes from Unnati Educations are a 72-page printed book that covers all 4 units of the GGSIPU MCA Semester 3 syllabus, with 48 worked examples, 40 short-answer questions with answers and 40 long-answer questions with answer key points. They follow the MCA scheme in force from academic session 2025-26.
Written by Prateek Talwar, Founder, Unnati Educations · Reviewed by Ritik Rawat, B.Tech, Senior Full Stack Developer · Checked against the official MCA Scheme of Examination and Detailed Syllabus (ipu.ac.in, from A.S. 2025-26) on 13 Oct 2026 · Updated 14 October 2026 · Editorial policy
Scheme: MCA scheme 2025-26 (USIC&T, affiliated institutes) | Applies to: academic session 2025-26 onwards | Verified against: MCA Scheme of Examination and Detailed Syllabus, BoS 28 Jul 2025, AC Sub Committee 1 Aug 2025
MCA 201 Design and Analysis of Algorithms at a glance: GGSIPU MCA Sem 3 credits, units and exam pattern
MCA 201 is the compulsory algorithms paper of MCA Semester 3, taught over 45 hours (9, 12, 12 and 12 per unit). It sits with the other GGSIPU MCA Semester 3 papers.
| Code and title | MCA-201 Design and Analysis of Algorithms |
|---|---|
| Course and semester | Master of Computer Applications (MCA), Third Semester |
| Type and credits | Core paper · L 3, T/P 1 · 4 credits |
| Marks | 100: 40 internal assessment + 60 end-term. Passing marks 40 out of 100 for every paper (scheme note 9) |
| End-term pattern | Compulsory Q1 (objective or short answers, whole syllabus) 12 marks + one of two questions from each of 4 units, 12 marks each (12 + 48 = 60 marks) |
| Rules | Programme governed by Ordinance 11 (scheme note 8) |
| Units | 4 (numbered I to IV, no unit titles in the official PDF) |
| Paired lab | MCA-261 Design and Analysis of Algorithms Lab. · L 0, T/P 2 · 1 credit |
MCA 201 Design and Analysis of Algorithms Notes unit-wise: 48 worked examples and 80 exam questions across 4 units
The 72-page book gives each unit a block ending in solved questions and a revision table. These are Design and Analysis of Algorithms notes in English, written for one-sitting revision per unit. Notes for every other paper sit under GGSIPU MCA notes; the sample PDF in the header shows one page per unit.
MCA 201 Unit 1: Performance Analysis of Algorithms and Recurrences
Unit 1 (pages 5 to 21) covers step counts (the iterative Sum takes 2n + 3 steps), space as S(P) = c + Sp, a loop-invariant proof of insertion sort, all five asymptotic notations with real constants, Las Vegas vs Monte Carlo, and recurrences by substitution, iteration, recurrence tree and master method. It has 17 worked examples and 20 exam questions.
| Recurrence | n^(log_b a) | Case | Answer |
|---|---|---|---|
| 9T(n/3) + n | n² | 1 | Θ(n²) |
| 2T(n/2) + n | n | 2 | Θ(n lg n) |
| 4T(n/2) + n³ | n² | 3 (regularity holds) | Θ(n³) |
| 2T(n/2) + n lg n | n | Gap, extended Case 2 | Θ(n lg² n) |
Quick look: master method on four recurrences (from page 16)
- Recurrence
- 9T(n/3) + n
- n^(log_b a)
- n²
- Case
- 1
- Answer
- Θ(n²)
- Recurrence
- 2T(n/2) + n
- n^(log_b a)
- n
- Case
- 2
- Answer
- Θ(n lg n)
- Recurrence
- 4T(n/2) + n³
- n^(log_b a)
- n²
- Case
- 3 (regularity holds)
- Answer
- Θ(n³)
- Recurrence
- 2T(n/2) + n lg n
- n^(log_b a)
- n
- Case
- Gap, extended Case 2
- Answer
- Θ(n lg² n)
MCA 201 Unit 2: Divide and Conquer, Linear-Time Sorting, String Matching and Advanced Data Structures
Unit 2 (pages 22 to 39) is the longest unit. It covers merge sort and partition traces, a nine-sort comparison table, Strassen on a 2 x 2 pair, linear-time sorts on real data, naive, Rabin-Karp, automaton and KMP matching, red-black insertion, disjoint-set forests and median of medians. It has 11 worked examples and 20 exam questions.
| q | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P[q] | a | b | a | b | a | c | a |
| π[q] | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
Quick look: KMP prefix function π[q] for P = ababaca (from page 31)
- q
- P[q]
- 1
- a
- 2
- b
- 3
- a
- 4
- b
- 5
- a
- 6
- c
- 7
- a
- q
- π[q]
- 1
- 0
- 2
- 0
- 3
- 1
- 4
- 2
- 5
- 3
- 6
- 0
- 7
- 1
MCA 201 Unit 3: Greedy Algorithms and Dynamic Programming
Unit 3 (pages 40 to 56) covers greedy methods: activity selection on CLRS data, Huffman codes (224 vs 300 thousand bits), Kruskal and Prim on one graph (MST 21) and Dijkstra with its proof. Dynamic programming follows, with full tables for matrix-chain (30,000), LCS, Bellman-Ford, Floyd-Warshall, an optimal BST of cost 32 and Ford-Fulkerson max flow. It has 14 worked examples and 20 exam questions.
| Item (w, v) | w=3 | w=4 | w=5 |
|---|---|---|---|
| 1 (2, 3) | 3 | 3 | 3 |
| 2 (3, 4) | 4 | 4 | 7 |
| 3 (4, 5) | 4 | 5 | 7 |
| 4 (5, 6) | 4 | 5 | 7 |
Quick look: 0/1 knapsack, W = 5, best value 7 from items 1 and 2 (from page 51)
- Item (w, v)
- 1 (2, 3)
- w=3
- 3
- w=4
- 3
- w=5
- 3
- Item (w, v)
- 2 (3, 4)
- w=3
- 4
- w=4
- 4
- w=5
- 7
- Item (w, v)
- 3 (4, 5)
- w=3
- 4
- w=4
- 5
- w=5
- 7
- Item (w, v)
- 4 (5, 6)
- w=3
- 4
- w=4
- 5
- w=5
- 7
MCA 201 Unit 4: Backtracking, Branch and Bound and NP-Completeness
Unit 4 (pages 57 to 72) covers Place() and NQueens() with a 4-queens trace, sum of subsets for m = 30, m-colouring, a Hamiltonian cycle, a 5-city TSP by reduced cost matrix (tour 28), then P, NP, NP-hard, the five-step NP-completeness proof, Cook's theorem and 3SAT to CLIQUE to VERTEX-COVER. It has 6 worked examples and 20 exam questions.
Quick look: branch and bound on a 4 x 4 assignment (from page 63)
- Root bound = row minima 2 + 3 + 1 + 4 = 10.
- a to job 2 keeps the bound at 10, so expand it.
- b to job 1 gives 13, the lowest child.
- c to job 3, d to job 4 completes it at cost 13; every other node is 14 or more, so prune.
Job sequencing with deadlines in greedy algorithms: excerpt from page 43 of the MCA 201 notes
Excerpt from page 43
Fractional knapsack: the answer and its catch
For capacity M = 50 and items (profit, weight) = (60, 10), (100, 20) and (120, 30), the ratios p/w are 6, 5 and 4. Items 1 and 2 go in whole and two-thirds of item 3 fills the last 20 units: profit 60 + 100 + 80 = 240. Sorting by ratio costs O(n log n) and filling costs O(n).
The ratio rule breaks when items cannot be split. With whole items only, greedy picks items 1 and 2 for 160, while items 2 and 3 give 220. That is why 0/1 knapsack is solved with dynamic programming later in the unit.
The problem
There are n jobs and one machine. Each job takes one unit of time, has a deadline dᵢ and earns profit pᵢ only if it finishes by that deadline. The aim is a feasible set of jobs, in an order the machine can actually run, with the largest total profit.
The greedy rule
Take jobs in decreasing order of profit. Put each job in the latest free slot on or before its deadline; if no such slot is free, reject it. Filling from the latest possible slot keeps earlier slots open for jobs with tighter deadlines.
Worked example, n = 5
| Job | Profit, deadline | Action | Slots 1 | 2 | 3 |
|---|---|---|---|
| J1 | 20, 2 | Place in slot 2 | - | J1 | - |
| J2 | 15, 2 | Slot 2 busy, use slot 1 | J2 | J1 | - |
| J3 | 10, 1 | Slot 1 busy, reject | J2 | J1 | - |
| J4 | 5, 3 | Place in slot 3 | J2 | J1 | J4 |
| J5 | 1, 3 | No free slot up to 3, reject | J2 | J1 | J4 |
Job sequencing trace for profits (20, 15, 10, 5, 1) and deadlines (2, 2, 1, 3, 3)
- Job
- J1
- Profit, deadline
- 20, 2
- Action
- Place in slot 2
- Slots 1 | 2 | 3
- - | J1 | -
- Job
- J2
- Profit, deadline
- 15, 2
- Action
- Slot 2 busy, use slot 1
- Slots 1 | 2 | 3
- J2 | J1 | -
- Job
- J3
- Profit, deadline
- 10, 1
- Action
- Slot 1 busy, reject
- Slots 1 | 2 | 3
- J2 | J1 | -
- Job
- J4
- Profit, deadline
- 5, 3
- Action
- Place in slot 3
- Slots 1 | 2 | 3
- J2 | J1 | J4
- Job
- J5
- Profit, deadline
- 1, 3
- Action
- No free slot up to 3, reject
- Slots 1 | 2 | 3
- J2 | J1 | J4
The machine runs J2, then J1, then J4, for a maximum profit of 15 + 20 + 5 = 40. Searching for a free slot job by job takes O(n²) in the worst case; keeping the slots in a disjoint-set structure brings it down to O(n log n).
Do the MCA 201 notes cover the full GGSIPU syllabus?
Yes. Every MCA-201 topic in the 2025-26 syllabus has its own section, from step counts in Unit I to Cook's theorem in Unit IV.
| Official unit | Official topics | Where in the notes | Status |
|---|---|---|---|
| Unit I (9 hours) | Performance analysis, correctness, asymptotic notations, randomized algorithms; four recurrence methods | Unit 1, sections 1 to 7, pages 6 to 16 | Covered |
| Unit II (12 hours) | Divide and conquer, Strassen; linear-time sorts; four string matchers; red-black trees, disjoint sets, order statistics | Unit 2, sections 1 to 8, pages 23 to 35 | Covered |
| Unit III (12 hours) | Greedy (activity selection, fractional knapsack, job sequencing, Huffman, Prim, Kruskal, Dijkstra); DP (matrix-chain, LCS, Bellman-Ford, Floyd-Warshall, optimal BST, 0/1 knapsack, network flow) | Unit 3, sections 1 to 15, pages 41 to 52 | Covered |
| Unit IV (12 hours) | Backtracking (4 problems); branch and bound (assignment, TSP); P, NP, NPC, NP-hard, reductions, Cook's theorem | Unit 4, sections 1 to 15, pages 58 to 68 | Covered |
Official MCA-201 units and topics mapped to the notes
- Official unit
- Unit I (9 hours)
- Official topics
- Performance analysis, correctness, asymptotic notations, randomized algorithms; four recurrence methods
- Where in the notes
- Unit 1, sections 1 to 7, pages 6 to 16
- Status
- Covered
- Official unit
- Unit II (12 hours)
- Official topics
- Divide and conquer, Strassen; linear-time sorts; four string matchers; red-black trees, disjoint sets, order statistics
- Where in the notes
- Unit 2, sections 1 to 8, pages 23 to 35
- Status
- Covered
- Official unit
- Unit III (12 hours)
- Official topics
- Greedy (activity selection, fractional knapsack, job sequencing, Huffman, Prim, Kruskal, Dijkstra); DP (matrix-chain, LCS, Bellman-Ford, Floyd-Warshall, optimal BST, 0/1 knapsack, network flow)
- Where in the notes
- Unit 3, sections 1 to 15, pages 41 to 52
- Status
- Covered
- Official unit
- Unit IV (12 hours)
- Official topics
- Backtracking (4 problems); branch and bound (assignment, TSP); P, NP, NPC, NP-hard, reductions, Cook's theorem
- Where in the notes
- Unit 4, sections 1 to 15, pages 58 to 68
- Status
- Covered
Source: MCA Scheme of Examination and Detailed Syllabus (affiliated institutes, from A.S. 2025-26). Unit names here are the notes' own.
The MCA 201 Design and Analysis of Algorithms IPU notes name two syllabus books as sources: CLRS (TB1) for proofs and Horowitz-Sahni (RB1) for pseudocode. Every course in GGSIPU notes is mapped to its official PDF this way.
How to write MCA 201 answers: asymptotic proofs, recurrence solutions and DP table numericals
Most MCA 201 questions take three shapes: prove a bound, solve a recurrence, or fill a table. The notes give long answers as key points to expand with diagrams and derivations: definition, working, then the final complexity in one line.
Bound proofs
Write the formal definition, then find real constants. Page 12 adds a rule many students skip: when you draw the O, Ω and Θ graphs, mark n₀ on the x-axis.
Worked example: show 3n + 2 = Θ(n) (page 11)
- Lower bound: 3n ≤ 3n + 2 for n ≥ 1, so c₁ = 3.
- Upper bound: 3n + 2 ≤ 4n once n ≥ 2, so c₂ = 4.
- With n₀ = 2 both hold, so 3n + 2 = Θ(n).
Recurrences
Name the method first. For the master method write a, b and n^(log_b a), compare with f(n) and state the case; where it fails, as with T(n) = T(n−1) + n, use iteration.
Table numericals
For matrix-chain, LCS, Floyd-Warshall, optimal BST or knapsack, draw the full table, show one cell's working, then trace back. An LCS answer needs the string (BCBA), not just the length 4. In Unit 4, the notes advise drawing the state space tree and the P and NP Venn diagram.
Practise these formats on GGSIPU MCA important questions.
MCA 201 exam corner: 40 short-answer and 40 long-answer questions by unit
| Unit | Short answer (2.5 Marks) | Long answer (12.5 Marks) | Worked examples |
|---|---|---|---|
| Unit 1 | 10 | 10 | 17 |
| Unit 2 | 10 | 10 | 11 |
| Unit 3 | 10 | 10 | 14 |
| Unit 4 | 10 | 10 | 6 |
| Total | 40 | 40 | 48 |
MCA 201 questions and worked examples in the notes, by unit
- Unit
- Unit 1
- Short answer (2.5 Marks)
- 10
- Long answer (12.5 Marks)
- 10
- Worked examples
- 17
- Unit
- Unit 2
- Short answer (2.5 Marks)
- 10
- Long answer (12.5 Marks)
- 10
- Worked examples
- 11
- Unit
- Unit 3
- Short answer (2.5 Marks)
- 10
- Long answer (12.5 Marks)
- 10
- Worked examples
- 14
- Unit
- Unit 4
- Short answer (2.5 Marks)
- 10
- Long answer (12.5 Marks)
- 10
- Worked examples
- 6
- Unit
- Total
- Short answer (2.5 Marks)
- 40
- Long answer (12.5 Marks)
- 40
- Worked examples
- 48
The notes print 2.5 and 12.5 marks labels; the 2025-26 paper has a 12-mark Q1 and 12-mark unit questions, so read "short" and "long" as answer lengths.
The MCA 201 notes solve 40 short-answer questions and give answer key points for 40 long-answer questions across 4 units, plus 48 worked examples.
One question per unit, with answer pointers:
- Unit 1: Solve T(n) = T(n−1) + n, T(1) = 1, by iteration. Pointer: expand to 1 + 2 + ... + n = n(n+1)/2, so Θ(n²).
- Unit 2: Insert 10, 20, 30, 15 into an empty red-black tree. Pointer: 30 forces a left rotation at 10; 15 meets a red uncle, so recolour, leaving 20 black over black 10 and 30, with 15 red.
- Unit 3: Find the LCS of ABCBDAB and BDCABA. Pointer: c[7, 6] = 4 and one trace-back gives BCBA, in Θ(mn).
- Unit 4: Differentiate NP-hard and NP-complete. Pointer: NP-hard need not be in NP (halting problem); NP-complete is NP-hard and in NP (SAT, CLIQUE).
More practice sits in the MCA 201 important questions.
Who writes and checks the MCA 201 DAA notes?
- Prateek Talwar, author: Founder, Unnati Educations; Associate Company Secretary (ACS), ICSI, membership no. 58704, since 15 May 2019; B.Com, University of Delhi (School of Open Learning), 2012. Profile
- Ritik Rawat, subject reviewer: B.Tech; Senior Full Stack Developer, Unnati Educations; reviews the MCA, BCA and B.Tech notes.
The 2026-27 edition maps MCA 201 to the scheme approved by the USIC&T Board of Studies on 28 July 2025, with a syllabus roadmap opening Units 2 to 4. Last updated 14 October 2026 under our editorial policy.
The same team prepares GGSIPU important questions for every course it covers.
MCA 201 and the MCA 261 DAA lab, plus other GGSIPU MCA Sem 3 papers
Paired lab: MCA 261 Design and Analysis of Algorithms Lab. · 1 credit (L 0, T/P 2)
The official PDF lists course outcomes, not practicals, for MCA-261. Lab CO3 (searching, sorting and tree-based algorithms) draws on Unit 2, CO4 (optimal solutions) on the Unit 3 DP tables and Unit 4 branch and bound, and CO2 (invariants) on the Unit 1 correctness proofs.
- Core: MCA-203 Artificial Intelligence and Machine Learning.
- Core Elective II (one of): MCA-205 to MCA-225, such as Cloud Computing or Applied Cryptography.
- Core Elective III (one of): MCA-227 to MCA-247, such as Compiler Design or Soft Computing.
- Open Elective II (one of): MCA-249 to MCA-255, such as Operational Research.
- Labs, project and NUES: labs MCA-263 to MCA-267, Minor Project III (MCA-269), and NUES papers MCA-271 and MCA-273.
MCA 201 DAA notes FAQs
How do I get the full MCA 201 notes?
Tap the "Get Full Notes" button to message us on WhatsApp at 9899436384. The MCA 201 notes are sold only as a printed book, not as a PDF. Once your order is confirmed, the 72-page book reaches you within 5 to 7 days at most, depending on your location. All order details are shared on WhatsApp.
Which semester is MCA 201 in, and how many credits does it carry?
MCA 201 is a Third Semester core paper in the GGSIPU MCA scheme that applies from academic session 2025-26 onwards. It carries 4 credits, with 3 lecture hours and 1 tutorial hour a week. It is not an elective, so every MCA student in Semester 3 must take it, alongside MCA-203 and the MCA-261 lab.
What is the passing mark for MCA 201?
MCA 201 is marked out of 100: 40 internal assessment and 60 end-term, where the end-term paper is a 12-mark compulsory Q1 plus four 12-mark unit questions. The MCA scheme of examination states passing marks as 40 out of 100 for every paper, which is 40%. End-term minimums and re-appear rules are in GGSIPU Ordinance 11 on ipu.ac.in.
Which MCA 201 unit is the biggest in the notes?
In the printed notes, Unit 2 is the longest at 18 pages, because it packs four topic groups: divide and conquer, linear-time sorting, string matching and advanced data structures. Unit 1 has the most worked examples (17), mostly asymptotic proofs and recurrences, while Unit 3 carries 14 table-based numericals across greedy methods and dynamic programming.
Do the MCA 201 notes follow the 2025-26 MCA syllabus?
Yes. Every topic in the four official MCA-201 units has a section in the notes, checked against the scheme approved in July 2025. One difference: the notes still label questions 2.5 and 12.5 marks, while the 2025-26 paper uses a 12-mark Q1 and 12-mark unit questions, so use those questions for practice, not as a marks guide.
Is MCA 201 the same as the MCA 261 lab?
No. MCA 201 is the 4-credit theory paper with a written end-term exam, while MCA 261 is the separate 1-credit Design and Analysis of Algorithms Lab. These notes cover MCA 201 theory: proofs, recurrences, traces and table numericals. Coding the sorts or the knapsack table belongs to the lab, which has its own notes page.
Get the full MCA 201 Design and Analysis of Algorithms Notes on WhatsApp
Format: printed book only, not available as PDF. 72 pages in English with an index and a revision table for each unit. Delivery: within 5 to 7 days at most; the exact time may vary with your location.
Order the MCA 201 notes book on WhatsApp (4 units, 72 pages)
Unnati Educations is an independent education provider based in Vikaspuri, Delhi. We are not affiliated with, authorised by, or endorsed by Guru Gobind Singh Indraprastha University (GGSIPU). 'GGSIPU' and 'IPU' are used only to describe the syllabus our notes follow. For official information, visit ipu.ac.in.
Ready for the full notes?
Discuss coverage and delivery with our team.