hw1 grading scheme

[Michael Brudno]

So our class TA is Shobhit Jain, his e-mail is shobhit@cs. Below is
his grading scheme for HW1. Pleases feel free to send him any
questions about your solutions.

======

Marking Scheme

This is a broad marking scheme. Marks also depend upon how well
the arguments are made.

Question 1 -

Part (a) - 5 marks each for odd and even cases
Part (b) - (i) 4 marks
(ii) 3 marks
(iii) 3 marks
Part (c) - 10 marks for graph based solution
max 10 marks for well argued modified alignment algo

Question 2 -

Part (a) - 10 marks for correct linear space algorithm
key points -
- Modification in SW to make it work in linear space

Part (b) - 10 marks for describing the key idea of finding
point on diagonal
max 5 marks for partially correct solutions

Question 3 -

Part (a) - max 10 marks for well explained cubic time solution
key points -
- recursive definition of matrix
- height of matrix
- Normalized score matrix
- talking about complexity of solution


Part (b) - 10 marks for O(mn) solution using modified alignment algo
max 10 marks for well explained grpah based solution in O(mn)
key point -
- construction of graph from alignment matrix

Part (c) - 10 marks for O(mn) solution
key point -
sub-optimal solution could be present any where in the matrix
max 5 marks with worse coplexity

Part (d) - 5 marks for O(mn^2) solution
10 marks for O(mn(log(n))) solution

Question 4 - 10 marks for stating correct reweighting scheme
3 marks for doing negation and adding same value to all edges

Comment: Figures and brief explanation of pseudocodes are really
helpful. Unannotated pseudocode
is basically impossible to read, and got very little benefit of the doubt.