From tianhan@cs.toronto.edu Fri Jul 26 11:40:41 2002 Date: 25 Jul 2002 18:59:04 GMT From: Tianhan Wang Newsgroups: ut.cdf.csc270h Subject: A2 marking comments Comments for A2 marking: ------------------------- Question 1. - It must be obvious from the code what the dimensions (including the upper/lower bounds) of the array are. It is a good way to specify them clearly right above the algorithm. - Remember you are supposed to write an algorithm for the recurrence relationship in dynamic programming but not recursion. Recursive algorithms will get 0 mark, even if it computes the table entries correctly. - Remember to label the table with i/j. Question 2. - There are a few possible solutions to the problem, and a different highest possible mark for each solution. Refer to the marking scheme. - Be concise and clear on your reasoning. Reason in general cases but not solely from specific examples. - Again if the solution is recursive, you lose many marks. Make sure you understand the diference between dynamic programming and recursion. - About the recurrence relationship: if c=0, the number of ways to stamp a 0-cent letter is 1 ("do not use any stamps), but not 0. - The estimate of running time and space usage should be both written in terms of "Big O". If you have a recursive algorithm, the running time will probably be exponential rather than polynomial. From niloofar@.MISSING-HOST-NAME. Fri Jul 26 13:52:38 2002 Date: Fri, 26 Jul 2002 11:54:57 -0400 From: Niloofar Arshadi To: Tristan Miller Newsgroups: ut.cdf.csc270h Subject: A2 marking comments Comments on A2 ------------- Q1 == - In your pseudocode, you need two different variables for the two sequence of numbers (array A and B); as the number of elements in A and B may not be the same. - Be careful about upper and lower bounds of the loops in your algorithm. Q2 == - In part b, you should specify which cell holds the solution. - In the best possible solution for this question, space requirement is of O(c) not O(kc). - In your table, you should not have a row for i=0 since the post office always has 1-cent stamps, where i denotes different denominations. -- Niloofar