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

------------------------------------------------------------------------