COMMON MISTAKES
---------------
------------------------------------------------------------------------
Q 1 and 2 are evaluated by AD
------------------------------------------------------------------------
Q1
--
Swap A[i] and A[j] even if i = j [-1]
Comment: This is unnecessary
Inrementing i after swap [-2]
Comment: Very wrong. The swap moves A[i] to correct
position, but A[i] may get a new value out of its own
place. Example: 4,3,1,2. After the pass it will be
2,1,3,4.
Using additional data while sorting B [-5]
Comment: B is given as a sorted array. You are not asked
to sort it. At any point of time, you can however copy A
and sort the copy using any additional data structure, but
that is too much extra effort (a complete sorting phase).
Since you are given B as a sorted version of A, you are
supposed to use it.
Sort A by making two swap passes [-5]
Comment: Two passes do not suffice. Consider the array
5,6,7,8,4,3,1,2. After first pass, it becomes
4,3,1,2,5,6,7,8, and after the second pass, it becomes
2,1,3,4,5,6,7,8. This is still not sorted.
Sort A by merge sort without using B [-8]
Comment: No efficient swap-based online merge sort is
known. Even if it exists, the number of swaps will be
O(n log n).
Sort A by quick / bubble / insertion sort without using B [-8]
Comment: Running time and swap count can be O(n^2).
Q2(a)
-----
O(n^3) algorithm (based on palindrome checker function) [-2]
Recursive algorithm (potentially exponential-time) [-3]
Incorrect populating order [-2]
Comment: The following orders will work.
(i) Diagonal-major
(ii) Column-major
(iii) Row-major but from higher to lower indexed rows
(iv) A seed-based order (seed at A[i...i] or A[i...i-1])
Incorrect initial conditions [-1]
Incorrect updating formulas [-2]
Comment: P[i][j] depends on P[i+1[[j-1]. There is no
relation with P[i][j-1] or P[i-1][j] or P[i-1][j-1].
Q2(b)
-----
Greedily choosing the palindromes [-2]
Comment: See the webpage for counterexamples.
ababaab = ababa a b (Greedy) = aba baab (Optimal)
baababa = b a ababa (Greedy) = baab aba (Optimal)
Choosing the palindromes without any minimization effort [-2]
Comment: Feasibility is not asked (because the problem is
always solvable). You should minimize the count of
plaindromes in the final decomposition.
Using a 2-D table for minimization [-1]
Comment: This will lead to O(n^3) running time. Only
1-D tables suffice.
Not computing a solution (an actual decomposition) [-1]
Comment: This is needed in addition to the count of
palindromes in a decomposition.
Recursive algorithm [-3]
------------------------------------------------------------------------
Q 3 and 4 are evaluated by AH
------------------------------------------------------------------------
Q3(a)
-----
Error in recursive formulation (of algorithm)
-- without / missing base condition [-2]
-- incomplete (less number of) recursion calls [-3]
Wrong Logic
-- Level-wise same number of nodes (or leaf-nodes) [-4]
-- Only from root node the left and right subtree [-4]
heights of T1 matches with either the left or right
subtree heights of T2
Inefficient Algorithms
-- Calculating height of left and right subtrees from [-2]
every node of T1 and matching it with the height of
either the left or the right subtrees of every
corresponding node of T2
-- Calculating total number of nodes present in the [-2]
left and right subtrees from every node of T1 and
matching it with the total number of nodes present
either in the left or in the right subtrees of
every corresponding node of T2
Q3(b)
-----
Only output complexity result
-- Without analysis [-4]
-- Some error in analysis or wrongly formulated [-3]
Simplified Analysis (not generic) considering every time [-2]
the recursive call splits both trees in with the half
number of nodes, and coming up with recursion,
T(n) = 4T(n/2) + c => T(n) = O(n^2)
Totally different analysis and produce some other result [-5]
Q4
--
O(n^2) time algorithm [-8]
Using more than one stack
-- correct algorithm [-6]
-- error in algorithm or produce wrong results [-7]
Pushing '(' and ')' together and hence not managing to [-5]
find the proper start and end of longest balanced
substring sequence
Error in output realization [-4]
Comment: Output realized may get wrong in some of the
test-cases mentioned like, ")(", ")()", ")()(", ")())",
"(()())" etc. (whichever is applicable and malfunctioning)
Not keeping the include positions properly [-5]
-- Not marking them in a separate array
-- Only kept two variables to mark the start and end [-4]
points of the longest realized balanced substring
sequence within the given input string
Comment: Very much wrong! It cannot ignore some
intermediate string which are not to be included
inside the mentioned start and end indexes
Not printing the output realizations [-3]
-- return the stack as a whole
Comment: Very wrong! It contains everything!
-- return include markers as an array (or some set)
Comment: It is the location index, not the
output realization
------------------------------------------------------------------------
GENERAL
-------
Do not express your algorithms in plain verbose English.
That is often too imprecise and even illegible. Writing
full-fledged C/C++ code is good for compilers, but may
be not so for human readers. Write appropriate psedocodes
(formal algorithms).
------------------------------------------------------------------------