# 1

- 1 mark for a/b/c (must be perfect to get mark)

- 4 marks for d and 5 marks for e

- In (d) (-2) for not taking care of “at least” 2 b’s properly (if a mistake was made here it was generally by doing something like …(abb)*…

- In (d) (-1) if force at least 1 abb or miss leading b’s

- In (e) (-2) if “0” included in solution or 5 not included

- If not a valid regular express, atleast (-3) up to a max of no marks (depending on the severity of the viololation)

- In (e) (-1) for leading 0’s

- In (e) (-1) if accept empty

# 2

- 2 marks, 1 each (must be correct to get mark)

- Picky on wording - for (a) must specify first occurrence and empty otherewise - for (b) must specify ( ) is not counted. (Note that ( ) is an atom and a list)

# 3

- 2 marks, 1 each (must be correct to get mark)

- Many included the +’s in the trace, which we were not interested in, only the calls and subsequent returns from the main function. Otherwise, why not include all the functions (car, etc…)

- Some missed the case for the ( ) in part b

# 4

- a (2 marks), b (8 marks), c (2 marks), d (8 marks)

- The questions did not say anything about atoms (rather, it said elements, which could be pairs) You lost .5 in each question for using eq?, eqv?, or =.

- Marks lost for missing base cases

- In (b) Majority of the marks were for building the recursion cases (2 for base case, 4 for recursing when removing element, 2 for recursing on the rest)

- In (c), you must have had a ‘more-or-less’ correct solution to receive marks. (-2) if you recursed on the same portions of the list repeatadly (inefficient)

- You realy could not write nice code without use of helper functions (-1 atleast, up to 0 marks for question)

- Many people had many redundant base cases in all part of 4. This means that you either don’t understand what you are writing, or that you have not traced your code through after writing it. As a general rule, don’t just though in base cases to get ride of problems that are occuring latter on in the recursion. You should take care of these elegantly.

- In (d) you most likely lost many marks for not writing nice code (should have used helper functions. If you messed up the main recursion, you lost half the marks for the question, or for using set!xxx.

- In general, do not modify the interface if it is given. You can use helper functions to accomplish what you want. (-1) for each instance of this for any question. Also, these (like most all function we do here) have very short and simple solutions.

# 5

- 2 marks for a/b and 10 marks for c

- You lost marks if you had to reverse a list in part (a)

- Part b and c were done poorly. Many said an improper list was something that was not a list, which, one its own, is incorrect since an improper list is also a pair. Excluding the part about a pair implies that the atom x is an improper list (which is obviously incorrect).

- In (c) (-5) for not checking recursively on both the car and cdr (as you had to make sure **ALL** sublists were also improper lists.

- In (c) Only 2/10 if you missed the above point and also did not take the conjunction of the results.

- In (c) many used things like (list? ….) to check, and then if that was true, did recursion, checking for improper sublists. Well, you cannot do this since if the argument is a list, then there is no sence checking the sublists. These types or errors were avoidable since if you type (list? (a (b . c) d)) at the interactive prompt, you will get => #t, as list? only checks the top level

- In (c) (-5) if you did not conjuct the results

- In (c) (-2) if said ((null? a) #t) since ‘( ) is a proper list

# 6

- 5 marks

- Many found the solution in the text and used that. Software re-use is a wonderful thing, but defeated the purpose of this question. I would have liked to see more novel solutions, rather than verbaitum solutions. If you just copied out the solution from the text, and made any mistakes **at all**, you were penalized more so than if you made the same mistake in your own solution.

- I took off 1 mark if you missed the fact that fib(0) = 0 (which most missed). If this was not the case, you would not be able to generate 0, 1, 1, 2, … since the base of the fib numbers are 0 and 1 (from which you can generate the rest of the pattern).

- Again, don’t change the interface!

- 0 if your code does not run in linear time.

# 7

- 5 marks

- Done well. Make sure that you do not use the style that Sebesta uses, as the notation is incorrect (where it uses null pointers). You will not receive marks in the future using this notation.