Probability Engine · CSC314

Design and Analysis of Algorithms (BSc CSIT, CSC314): the questions likely to come

33 analyzed questions from 8 past papers (2074-2082), grouped by syllabus unit — each with its probability, how often it's been asked, and where to study the answer.

Papers analyzed

2074-2082

Analyzed questions

across 7 syllabus units

Very likely units

high-probability topics

Units = 80% of marks

study these first

Model answers for this subject are being written. Every question links to its original paper so you can study from the source meanwhile.

Pick a unit

U4 · Q1/6 · 207910 marks

Greedy Algorithms

Define minimum spanning tree. Write Kruskal's algorithm to find the MST of a connected weighted graph, illustrate it with an example and analyze its complexity.

35%

Possible to appearAppeared in 3 of the last 3 board papers

Seen in

How well do you know this?rating moves you on

MODEL ANSWERU4 · 10 marks

Minimum Spanning Tree (MST)

Given a connected, undirected, weighted graph $G=(V,E)$ , a spanning tree is a subgraph that is a tree connecting all $|V|$ vertices using exactly $|V|-1$ edges. A Minimum Spanning Tree is a spanning tree whose total edge weight $\sum_{e\in T} w(e)$ is minimum among all spanning trees.

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm. It repeatedly picks the smallest-weight edge that does not form a cycle, using a disjoint-set (Union-Find) structure to detect cycles.

KRUSKAL(G):
    A = {}                      // edges of MST
    for each vertex v in V: MAKE-SET(v)
    sort edges of E in non-decreasing order of weight
    for each edge (u,v) in sorted order:
        if FIND-SET(u) != FIND-SET(v):   // adding edge does not form a cycle
            A = A union {(u,v)}
            UNION(u, v)
    return A

Example

Consider a graph with vertices $\{A,B,C,D,E\}$ and edges: $AB=1,\ BC=2,\ AC=3,\ CD=4,\ BD=5,\ DE=6,\ CE=7$ .

Process edges in increasing order:

Edge	Weight	Action
AB	1	Add (no cycle)
BC	2	Add (no cycle)
AC	3	Reject (A,C already connected)
CD	4	Add (no cycle)
BD	5	Reject (B,D connected)
DE	6	Add (no cycle)

MST edges = $\{AB, BC, CD, DE\}$ , total weight $=1+2+4+6=13$ , with $|V|-1=4$ edges.

Complexity Analysis

Sorting the $E$ edges: $O(E\log E)$ .
$V$ MAKE-SET and at most $2E$ FIND/UNION operations with union by rank + path compression: $O(E\,\alpha(V))$ , nearly linear.
Total: $O(E\log E)=O(E\log V)$ (since $E\le V^2$ , $\log E=O(\log V)$ ).

Correctness follows from the greedy cut property: the lightest edge crossing any cut is safe to add to the MST.

AI-generated answer · unverifiedView in 2079 paper →

U4 · Question 1 of 6

Question Priority · U4ranked by appearance likelihood — study top-down

Greedy Algorithms

Analyzed next58%

★ TOP PICK

Define minimum spanning tree. Write Kruskal's algorithm to find the MST of a connected weighted graph, illustrate it with an example and analyze its complexity.

10 marksSEEN IN

35%

Explain the job sequencing with deadlines problem and solve it using the greedy approach for a given set of jobs.

5 marksSEEN IN

58%

Explain the greedy method of algorithm design. Generate the prefix code for the string "CYBER CRIME" using Huffman algorithm and find the total number of bits required to encode it.

10 marksSEEN IN

27%

Write a greedy algorithm for the fractional knapsack problem and analyze its time complexity.

5 marksSEEN IN

52%

Write Dijkstra's algorithm to find single-source shortest paths and explain it with an example.

5 marksSEEN IN

50%

How do you define optimal solution? Does greedy algorithm always guarantee optimal solution? Given the string "SUPER DUPER CSIT", use a Greedy algorithm to build a Huffman tree.

10 marksSEEN IN

25%

03The mock

Sit a probable paper

A full mock exam built from the most likely questions, mirroring the real paper's structure. Every slot is a real past question.

Most Probable Paper

Mirrors the real structure · 60 marks · based on 8 past papers

Section A: Long Answer QuestionsAttempt any TWO questions.

1.
Define minimum spanning tree. Write Kruskal's algorithm to find the MST of a connected weighted graph, illustrate it with an example and analyze its complexity.
[10 marks]
Greedy AlgorithmsVery likelyfrom 2079 paper →
This question has recurred in 3 of 8 years; so far only in internal assessments, not the board; and its topic (Greedy Algorithms) appears in 100% of years.
2.
Explain the greedy method of algorithm design. Generate the prefix code for the string "CYBER CRIME" using Huffman algorithm and find the total number of bits required to encode it.
[10 marks]
Greedy AlgorithmsVery likelyfrom 2077 paper →
This question has recurred in 3 of 8 years; so far only in internal assessments, not the board; and its topic (Greedy Algorithms) appears in 100% of years.
3.
Define asymptotic notations (Big-O, Big-Omega, Big-Theta). State the master theorem and use it to solve the recurrences T(n)=3T(n/2)+n and T(n)=2T(n/4)+sqrt(n).
[10 marks]
Foundations of Algorithm AnalysisVery likelyfrom 2080 paper →
This question has recurred in 3 of 8 years; so far only in internal assessments, not the board; and its topic (Foundations of Algorithm Analysis) appears in 88% of years.

Section B: Short Answer QuestionsAttempt any EIGHT questions.

1.
Explain the job sequencing with deadlines problem and solve it using the greedy approach for a given set of jobs.
[5 marks]
Greedy AlgorithmsVery likelyfrom 2081 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Greedy Algorithms) appears in 100% of years.
2.
Write a greedy algorithm for the fractional knapsack problem and analyze its time complexity.
[5 marks]
Greedy AlgorithmsVery likelyfrom 2081 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Greedy Algorithms) appears in 100% of years.
3.
Write Dijkstra's algorithm to find single-source shortest paths and explain it with an example.
[5 marks]
Greedy AlgorithmsVery likelyfrom 2081 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Greedy Algorithms) appears in 100% of years.
4.
Solve the recurrence relation T(n) = 2T(n/2) + n using the substitution method and the recursion tree method.
[5 marks]
Foundations of Algorithm AnalysisVery likelyfrom 2082 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Foundations of Algorithm Analysis) appears in 88% of years.
5.
Differentiate between Breadth First Search (BFS) and Depth First Search (DFS) with examples and their time complexities.
[5 marks]
Foundations of Algorithm AnalysisVery likelyfrom 2080 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Foundations of Algorithm Analysis) appears in 88% of years.
6.
Explain heap sort algorithm with an example and analyze its time complexity.
[5 marks]
Divide and Conquer AlgorithmsVery likelyfrom 2081 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Divide and Conquer Algorithms) appears in 100% of years.
7.
What are approximation algorithms? Explain the approximation algorithm for the vertex cover problem.
[5 marks]
Number Theoretic, Computational Geometry and NP-CompletenessVery likelyfrom 2079 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic (Number Theoretic, Computational Geometry and NP-Completeness) appears in 100% of years.
8.
Explain how the subset-sum problem is solved using backtracking with an example.
[5 marks]
BacktrackingLikelyfrom 2082 paper →
This question has recurred in 5 of 8 years; so far only in internal assessments, not the board; and its topic recurs in 6 of 8 years.
9.
Explain the naive string matching algorithm and the Rabin-Karp algorithm with their time complexities.
[5 marks]
Foundations of Algorithm AnalysisVery likelyfrom 2081 paper →
This question has recurred in 4 of 8 years; so far only in internal assessments, not the board; and its topic (Foundations of Algorithm Analysis) appears in 88% of years.

04The receipts

Behind the numbers

The raw evidence the predictions are computed from: marks per unit per year, syllabus weights, trends, and coverage.

Show the heatmap, topic table and coverage analysis

The receipt: marks per unit, per year

Each row is a syllabus unit, each column an exam year, each cell the marks that unit earned that year. Click any cell to see the actual questions behind it.

Marks:nonefew → many

2074

2075

2077

2078

2079

2080

2081

2082

Total

U4Greedy Algorithms

145

U1Foundations of Algorithm Analysis

105

U3Divide and Conquer Algorithms

U7Number Theoretic, Computational Geometry and NP-Completeness

U5Dynamic Programming

U6Backtracking

U2Iterative Algorithms

#	Syllabus unit	Probability	Appeared	Avg marks	Syllabus weight	Exam vs syllabus	Trend	Questions
1	U4Greedy Algorithms	Very likely100%	2074 2075 2077 2078 2079 2080 2081 2082	18.1	16%7 lecture hrs	Over-examinedexam 24% · syllabus 16%	Fading	5 recurring6 total
2	U1Foundations of Algorithm Analysis	Very likely88%	2075 2077 2078 2079 2080 2081 2082	15	11%5 lecture hrs	Over-examinedexam 18% · syllabus 11%	Rising	4 recurring5 total
3	U3Divide and Conquer Algorithms	Very likely100%	2074 2075 2077 2078 2079 2080 2081 2082	10	16%7 lecture hrs	Balancedexam 13% · syllabus 16%	Steady	3 recurring5 total
4	U7Number Theoretic, Computational Geometry and NP-Completeness	Very likely100%	2074 2075 2077 2078 2079 2080 2081 2082	9.4	18%8 lecture hrs	Under-examinedexam 12% · syllabus 18%	Rising	2 recurring6 total
5	U5Dynamic Programming	Likely75%	2074 2075 2077 2080 2081 2082	15.8	18%8 lecture hrs	Balancedexam 16% · syllabus 18%	Steady	4 recurring6 total
6	U6Backtracking	Likely75%	2074 2075 2077 2078 2079 2082	12.5	11%5 lecture hrs	Balancedexam 12% · syllabus 11%	Fading	3 recurring3 total
7	U2Iterative Algorithms	Likely62%	2078 2079 2080 2081 2082	5	11%5 lecture hrs	Under-examinedexam 4% · syllabus 11%	Rising	1 recurring2 total

Study smart, not hard

Drag the slider: studying the top 5 units in priority order covers ~83% of all observed marks.

Units to study5/7

~80% line

Lecture time vs exam marks

Where the exam pays more than the curriculum spends: ● lectures vs ● exam marks, as a share of the whole course. A long teal-leading bar = high-yield unit.

U4Greedy Algorithms

16% of lectures → 24% of markshigh yield

U1Foundations of Algorithm Analysis

11% of lectures → 18% of markshigh yield

U3Divide and Conquer Algorithms

16% of lectures → 13% of marks

U7Number Theoretic, Computational Geometry and NP-Completeness

18% of lectures → 12% of markslow yield

U5Dynamic Programming

18% of lectures → 16% of marks

U6Backtracking

11% of lectures → 12% of marks

U2Iterative Algorithms

11% of lectures → 4% of markslow yield

Design and Analysis of Algorithms (BSc CSIT, CSC314): the questions likely to come

Minimum Spanning Tree (MST)

Kruskal's Algorithm

Example

Complexity Analysis

Greedy Algorithms

Sit a probable paper

Most Probable Paper

Behind the numbers

The receipt: marks per unit, per year

Study smart, not hard

Lecture time vs exam marks

2082 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2081 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2080 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2079 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2078 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2077 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2075 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)

2074 B.S.

Design and Analysis of Algorithms (BSc CSIT, CSC314)