CP164 : Winter 2020 Midterm Notes

The following are comments on the Midterm. Please review this material before bringing any questions about your midterm to the instructor. You should also try implementing your solution in Eclipse to see how well they work.

Benefit of the Doubt (BD) Marks: A BD mark was added to your midterm grade in MLS - it was not recorded on your midterm. As always with BD marks, should you request a remark of any midterm question, the BD mark will first be removed from your recorded midterm grade.

If you failed the midterm, drop the course!

The array-based data structures are the easy part of the course. If you can't handle these, you're not going to do better in the last half of the course. At the very least, talk to me about your progress.

General Comments

Better solutions get better marks

Even solutions that 'work', (i.e. generate the correct solution) don't get full marks if their approach is clumsy, unnecessarily complex, grossly inefficient, or there is simply a better approach.

Don't Copy The Question Into The Answer

I know what the question is - just Stop Doing this.

Use the methods that match the data structures

Stacks use push and pop, not insert and remove. You cannot call len on a Stack or use [i] on a Stack - those methods are not defined for it. Note that every page of the midterm contained a list of data structures and their main methods, so there is no reason for you to use the wrong method names.

_values, which is a Python list, does not have an is_empty method.

Understand your Python data structures

A string is not a list and they cannot be compared. The Python methods lower, upper, reverse, etc., all return a new string - they do not change the existing string. The result of the method must be sent to a new variable,
i.e. tmp = s.lower()

Remember basic CP164 rules
Know your CP104 skills:
Call methods and functions properly

Ex: is_empty is a method, it must be called with the parentheses as s.is_empty().

Accessing low level data structures in a Use question

is wrong. Thus if you are asked to use a Queue to do something, but your code references _values, you will lose marks.

Accessing high level data structures in an Extend question

is wrong. The opposite to the above is using high level data structures methods in an extend question. Calling a Stack push when you should be using _values.append() loses marks.

Not using a data structure

A use question that starts out with the words,

Use a Stack …

or equivalent, expects that the answer you provide uses a Stack object. If your solution does not use a Stack (or other requested data structure), then the grade is 0, no matter what else is written. This is a Data Structures course, and if you're not using a data structure, you're missing the point completely.

Proper use of deepcopy

Do not use deepcopy when something is going to be removed from a data structure.

Do not use deepcopy when a method already does so.
stack.push(deepcopy(x)) is unnecessary since deepcopy is already done inside push.

Do not use deepcopy inside a loop when only the last value needs to be copied. Ex:

max_val = deepcopy(self._values[0])

for i in range(1, len(self._values)):
    if self._values[i] > max_val:
        max_val = deepcopy(self._values[i])
return max_val

should be:

max_val = self._values[0]

for i in range(1, len(self._values)):
    if self._values[i] > max_val:
        max_val = self._values[i]
return deepcopy(max_val)

because we need to copy only the value actually returned.

This Is Evil
if ...:
    value = value

If an else isn't used, leave it out!

Use the correct loop

If an algorithm is determining whether something is true or false about a string or list or expression, and the first occurrence of a problem is enough to falsify the entire expression, then Stop Looping! Use while not for to process the expression. Ex:

is_mirror = True

for i in range(len(string)):

     if string[i] not in CHARS:
         is_mirror = False

should be replaced by:

i = 0

while is_mirror and i < len(string):

     if string[i] not in CHARS:
         is_mirror = False
         i += 1

because if we find a character that is not valid (not in CHARS), then we don't care about the rest of the string. If that is the case, why are we processing the rest of the string?


A worse case of the previous example is when the code toggles between two return values, as in this example:

is_mirror = True

for i in range(len(string)):

     if string[i] not in CHARS:
         is_mirror = False
         is_mirror = True

If the last character in the string is valid, then is_mirror is set to True for the entire expression, which is wrong. Do not toggle between return values. Once a return value has been set to False, never set it back to True (or visa-versa).

Bad Compound if

Don't do this:

if s.pop() != '[':
elif s.pop() != '(':
elif s.pop() != '{':

because the top of s is popped three times. Replace with:

value = s.pop()

if value != '[':
elif value != '(':
elif value != '{':
Incorrect string splitting

The result of splitting the string "aaamaaa" with


is ["aaamaaa"] which is not what you expect, nor is it useful. Just work with the string as is.

Check your algorithms

The code:

s = Stack()

while not s.is_empty():

makes no sense as an algorithm. (Stacks are empty when created, so this loop never executes.) Keeping your thoughts straight and attention to detail is important.

Grossly Inefficient Algorithm

Here is an example of a grossly inefficient (but 'working') algorithm for a Sorted_List:

def remove_many(self, key):
    while key in self._values:
        i = self.binary_search(key)

The use of the in operator makes this particularly inefficient, because in works like a linear search. So for every loop the algorithm performs a linear search for a key, followed by a binary search for the same key. Given that this is a Sorted_List and all the matching values are beside each other (i.e. find the first occurrence, you've found where the rest of them are), this is particularly bad.