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). ------------------------------------------------------------------------