COMP1921 16s2

Final Exam Part I Instructions

The Final Examination consists of two parts: Part I Written and Part II Practical. The maximum time allowed for both parts combined is 3 hours. The following instructions and questions form the Written part.

You are NOT permitted to log into the lab computers until you have completed and handed in Written Part I to the exam invigilator.

• Maximum Time allowed: 1 hour (i.e. 60 minutes) + 10 minutes reading time

• Total number of questions: 10 (8 multiple-choice questions plus 2 open questions)

• Total marks available: 20 (1 for each multiple-choice question and 6 for each open question)

• All answers must be written on blue or black ink on this exam paper. The paper may not be retained by the candidate.

• For the multiple-choice questions, tick the box for your answer directly (only one answer is correct). To make a correction, tick all boxes, then circle the box for your answer.

• You may not use calculators, textbooks, notes, phones, laptops, tablets or watches.

• Fill in your name, student id, signature on the cover of this exam paper.

• Sign the attendance sheet and place your student card on it.

• Answer all questions.

• If you finish early, you may start answering the Practical Part (Part II) of the exam. However, you must return the exam paper for the Written Part before you commence on the Practical Part.

Final Exam Part II Instructions

• Minimum Time allowed: 2 hours (i.e. 120 minutes)

• Total number of questions: 4

• Total marks available: 35

• Questions are not worth equal marks.

• Your solutions must be answered in a file named as specified in the question and submitted electronically using the submit command as described in each question.

• Please note:

  • Your program should:
    • be compiled using gcc -Wall -Werror -O, and generate no compiler warnings or errors
    • contain proper indentation and be clearly written
    • conform to the style guide

  • You can use the provided Makefile to compile your programs; for example,

    prompt$ make 1

    will produce the executable swapTree from your program swapTree.c for Question 1 etc.

  • You should name your programs as instructed. This is very important.

  • You should submit your files using the submit command as described in the question. You may submit your solutions as many times as you like. The last submission ONLY will be marked. You can check what you have submitted by using the submit command with no arguments.

  • You should match the output exactly (do not change the format in any way).

Prac Question 1 (14 marks)

• builds a BST (binary search tree) from a sequence of integers on the command line (in the order they are given)
• pretty-prints the BST in the format shown below in the test cases (NOTE: Your program must adhere exactly to the format shown below)
• re-orders the tree so that values appear in descending order, that is, the new tree has the propery:
  • all values in left subtree are greater than root
  • all values in right subtree are less than root
  • this property applies over all nodes in the tree

• pretty-prints the re-ordered BST

prompt$ ./swapTree 2 1 3 1 2 3 Swapped tree: 3 2 1

prompt$ ./swapTree 8 4 6 2 7 5 3 1 12 10 9 14 13 11 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Swapped tree: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

prompt$ ./swapTree 6 5 4 3 2 1 1 2 3 4 5 6 Swapped tree: 6 5 4 3 2 1

prompt$ ./swapTree 7 7 Swapped tree: 7

prompt$ ./swapTree Usage: ./swapTree integers ...

prompt$ ./swapTree 3 10 a Usage: ./swapTree integers ...

NOTE: You must ensure that your program prints the output in the format shown in the above test cases.

Prac Question 2 (15 marks)

Write a program simulate.c that simulates the following roulette betting strategy, starting with a given initial balance ≥ $1:

1. Let n = $1
2. Place n on "Odd"
3. If the round is won, then n will be added to the balance; and the next bet is n = $1
4. If the round is lost, then n will be subtracted from the balance; and the next bet is n = min(2 * n, balance)
5. Repeat steps 2-4 until either you have doubled the initial amount (i.e. balance is twice the initial balance), or balance is $0

Your program should use a random number generator to simulate the result of spinning the wheel in each round, which is a number between 0 and 36 (including both 0 and 36). A round is won if this number is odd. A round is lost if the number is even (including zero). Your program should output the bet, the winning number and the new balance after each round (NOTE: Your program must adhere exactly to the format shown below.) Your program should accept two integer command line arguments:

• The first argument is the initial balance
• The second argument is used as the seed for the random number generator.

prompt$ ./simulate 3 4567 Bet: $1. Winning number: 29. New balance: $4 Bet: $1. Winning number: 0. New balance: $3 Bet: $2. Winning number: 25. New balance: $5 Bet: $1. Winning number: 31. New balance: $6

prompt$ ./simulate 3 2234 Bet: $1. Winning number: 16. New balance: $2 Bet: $2. Winning number: 1. New balance: $4 Bet: $1. Winning number: 9. New balance: $5 Bet: $1. Winning number: 0. New balance: $4 Bet: $2. Winning number: 10. New balance: $2 Bet: $2. Winning number: 26. New balance: $0

prompt$ ./simulate 100 16 Bet: $1. Winning number: 0. New balance: $99 Bet: $2. Winning number: 2. New balance: $97 Bet: $4. Winning number: 18. New balance: $93 Bet: $8. Winning number: 2. New balance: $85 Bet: $16. Winning number: 14. New balance: $69 Bet: $32. Winning number: 6. New balance: $37 Bet: $37. Winning number: 8. New balance: $0

prompt$ ./simulate 100 Usage: ./simulate initialbalance randomseed

prompt$ ./simulate 100 16 1 Usage: ./simulate initialbalance randomseed

prompt$ ./simulate 100 x Usage: ./simulate initialbalance randomseed

• The C library stdlib provides the functions   void srandom(int seed)   and   long int random()

• It is important that you call the random number generator as specified in lectures, otherwise the output will not match. If you use a different method to generate random numbers, the testcases will "fail", but your program could still be perfectly correct.