Semester: 4
Subject: Design and Analysis of Algorithms
Examination: CIA 1
Time: 90 minutes
- Objectives
- Code Output
- Time Complexity
- Space Complexity
1) Functions to generate randomised 16-character sequences 's1' & 's2' using given character set - Done.
2) Recursive function calls are encouraged - Noted.
3) Output: First 4 maximal score sub-sequences - Done.
4) Space Complexity - Done.
5) Time Complexity - Done.
6) Generate Alignment Matrix - Done.
7) Traceback in Alignment Matrix - Done.
8) Alignment Scores - Done.
[ TODO: Automate Step 3, to provide 'n' top-scoring sequences ]
| Section | Time Complexity | Explanation |
|---|---|---|
| Randomised Sequence Generation | O(n) | Depends linearly on the length of the character set. |
| Alignment Matrix Initialisation | O(l1 * l2) | Initialises an alignment matrix of size '(l2 + 1) * (l1 + 1)'. |
| Recursive Alignment Matrix Generation [dp] |
O(l1 * l2) | The recursive function 'dp' is called for each cell of the alignment matrix, resulting in a total of '(l1 + 1) * (l2 + 1)' function calls. Each function call performs constant time operations - comparisons, assignments, and recursive calls, leading to a time complexity proportional to the product of the string lengths. |
| Traceback in Alignment Matrix [tracepath] |
O(l1 + l2) | The traceback process stops when reaching a cell with a score of '0', which occurs in the worst case when all cells are filled with values greater than '0'. The longest resultant sequence in the matrix is of length 'l1 + l2'. |
| 'n' = size of the character set. 'l1' & 'l2' = lengths of sequences 's1' & 's2', respectively. |
||
| Section | Space Complexity | Explanation |
|---|---|---|
| Input Sequences | O(l1 + l2) | The space required to store the input sequences is proportional to the lengths of 's1' and 's2', respectively. |
| Alignment Matrix | O(l1 * l2) | The alignment matrix has dimensions '(l2 + 1) * (l1 + 1)'. |
| Recursive Calls | - | The recursive calls in the 'dp' and 'tracepath' functions do not require additional space for each call since the function parameters and local variables are stored on the stack. |
| 'l1' & 'l2' = lengths of sequences 's1' & 's2', respectively. | ||