Common Mistakes Assignment no. 1




General:



1. Pseudo code is something that should be easy to read and understandable. All sorts of programming effects and shortcuts should be avoided.



2. Please add a verbal description of every solution, and not only calculation or pseudo code.




Question 2:



1. The question said “Define precisely the representation of your data structure”. Some definitions given were not detailed, and many without proper description of the “circular array” structure (although the students did describe it correctly in the pseudo code).



2. Many students used only N-1 cells of the array, or defined an array of size N+1, and used only N cells. We didn’t take off points, but in general it’s not efficient, and there is a way to define an N size array and make use of all of its cells.




Question 3b:


Many of the students defined n to be “the size of the current array”, and gave answers of Theta(mn). This is not exact, since n wasn't given as one of the parameters in the question. The expression should have been Theta(m^2). Also, some students gave their answer in O-notation, that is O(m^2). You should have proved an asymptotically correct solution, that is Theta(m^2). O(m^2) is only an upper bound, Omega(m^2) is only a lower bound, and Theta(m^2) is the correct solution.
In this question, the important issue was proving an Omega(m^2) lower bound on the running time of m operations.




Question 4:

The pseudo-code checks if the list is correct i.e. has no inner cycle. If it is correct – returns true, otherwise, returns false.  Many students wrote long descriptions of every code line, and every if-command – that's not what was requested. We asked for a short description, of the “bottom-line”. Some said that the code checks if the list is infinite, which is obviously not a correct answer. Even if an infinite list is possible, the code would not stop on such a list, so the code doesn't "check" for infiniteness.