CSC325 · TU past paper
Design and Analysis of Algorithms 2080 question paper
The complete TU 2080 exam paper for Design and Analysis of Algorithms (CSC325), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 1Solving RecurrencesHideAnswer
Recurrence Relations and Solving using Substitution Method
A recurrence relation is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a recurrence relation means to obtain a function defined on the natural numbers that satisfies the recurrence...
- 210 marksNumericalGreedy Algorithms vs Dynamic Programming, HideAnswer
Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order $2, 3, 4, 2, 5$. [10]
Aspect Dynamic Programming Greedy Strategy --------------------------------------------- Global optimality Guarantees a globally optimal solution by examining all relevant subproblem combinations May settle for a locally optimal choice t...
- 310 marksSorting AlgorithmsHideAnswer
Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.[10]
--- A heap is a complete binary tree stored as an array where: - Max-Heap property: Every parent node is greater than or equal to its children. - Min-Heap property: Every parent node is less than or equal to its children. For an array A ...
- 45 marksRAM modelHideAnswer
Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis. [5]
Definition: The Random Access Machine (RAM) model is a model for counting the steps in an algorithm in order to analyze its time complexity. In this model: - Basic operations (+, -, , /) are counted as 1 step - Memory references (read/wr...
- 55 marksSearching AlgorithmsHideAnswer
Write down nimmax algorithm and analyze its complexity. [5]
--- The Minimax algorithm is a recursive backtracking algorithm used in two-player zero-sum games (e.g., Chess, Tic-Tac-Toe). It determines the optimal move for a player assuming the opponent also plays optimally. - The MAX player tries ...
- 65 marksGreedy AlgorithmsHideAnswer
When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity. [5]
A greedy strategy provides an optimal solution when the problem satisfies the following conditions: 1. Greedy Choice Property: A globally optimal solution can be reached by making a locally optimal (greedy) choice at each step. That is, ...
- 75 marksNumericalHuffman CodingHideAnswer
Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet.
Symbol Frequency a 30 b 20 c 25 d 15 e 35 [5]
Symbol Frequency ------------------- a 30 b 20 c 25 d 15 e 35 Total frequency $= 30 + 20 + 25 + 15 + 35 = 125$ --- Sort ascending: d(15), b(20), c(25), a(30), e(35) Node db(35) Remaining: c(25), a(30), e(35), db(35) Node ca(55) Remaining...
- 85 marksNumericalBacktracking AlgorithmsHideAnswer
Does backtracking give multiple solution? Trace subset sum algorithm for the set $(3, 5, 2, 4, 1)$ and sum = 8. [5]
- Set $S = {3, 5, 2, 4, 1}$ - Target sum $X = 8$ - Number of elements $n = 5$ Yes. Backtracking systematically explores the entire state-space tree using depth-first search. It does not necessarily halt at the first feasible solution; ...
- 95 marksNumber Theoretic Notations, Euclid's and EHideAnswer
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity. [5]
The Extended Euclidean Algorithm is used to find not only the Greatest Common Divisor (GCD) of two integers a and b, but also the integer coefficients x and y such that: ax + by = gcd(a, b) This is based on Bezout's Identity. It is widel...
- 105 marksConcept of Aggregate AnalysisHideAnswer
Write short notes on a) Aggregate Analysis b) Selection problems [5]
Definition: Aggregate analysis is a technique used in amortized analysis that determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the average (amortized) cost per operation as T(n)/n. Steps in...
- 115 marksSorting AlgorithmsHideAnswer
Write down algorithm of insertion sort and analyze its time and space complexity. [5]
Insertion Sort works by picking each element and inserting it into its correct position among the already-sorted elements to its left. Steps: 1. Start with the array A of n elements. 2. Pick the element at position i (starting from i = 1...
- 125 marksNP Complete Problems, NP Completeness and HideAnswer
Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete". [5]
A problem X is called NP-complete if it satisfies both of the following conditions: 1. X belongs to NP: The problem X can be verified in polynomial time. That is, given a candidate solution (certificate), we can check whether it is corre...