Questions: Students may discuss Assignment Questions, and may be informed by such discussions, but when a student writes the submitted work the student must do so without the aid of any relic of any conversation, communication, or outside source that gives directly the solution or partial solution to the problem, unless explicitly permitted by the Assignment document.

1. Consider the following MARIE program.
   
   

      clear 
      Store answer
      input 
      store num
      input 
      store maxj
   loop, Load answer
      Add num
      Store answer 
      Load num
      Add one
      Store num
      Load j
      Add one
      Store j
      Subt maxj
      Skipcond 800
      Jump loop
      Load answer
      Output
      Halt
   
   num, dec 0
   j,   dec 0
   maxj,   dec 0
   one, dec 1
   answer, dec 0
   

   a) (1 mark) Give the answer that is output when the inputs are: 1, 3
   b) (1 mark) Give the answer that is output when the inputs are: 0, 11
   c) (5 mark) Give a short program in C++ that is equivalent to the program given. By equivalent, we mean that it computes the same thing and it uses the same method or algorithm. When writing it in C++, express the algorithm naturally in C++, using the C++ constructs.
   
   
2. Write the following Prolog predicates. Test them on the Prolog interpreter, and hand in typed or handwritten Prolog predicates.
   a) (1 mark) Give the predicate "append(L1,L2,L3)", where L3 is the result of appending list L2 to the back of list L1. You don't have to reinvent it; you can look it up in the Prolog Wikibook (link on the web page), or get it from your notes. The object of this 1 mark question is to ensure your familiarity with Prolog recursive predicates.
   b) (4 marks) Give a prolog predicate that takes a list and counts the number of elements in the list. The predicate will be size(L,X), where L is a list and X is the number of members of the list.
   
   c) (6 marks) Give a prolog predicate that takes a list and halves it into two sublists, the front end and the back end. The predicate will be halves(L, LF, LB). If the list is of odd length, the front half will be the longer half. Use the predicate append, which we looked at in class and is covered in the Prolog Wiki, and use the size predicate.