Final Exam

Locations

Final exam locations are NOT the same as the ones for the class prac tests. Please check your final exam location..

We will give you exact seat numbers later.

Exam Format

Multiple Choice: 10 marks
Short Answer: 45 marks
Programming Questions: 45 marks

Exam Tips and Feedback from Prac tests

For the final exam you must be familiar with the assignment 2 spec and be able to state exactly which vertices a detective would visit, given a particular map if the detective was following a particular strategy etc.

For questions when you need compare algorithms do not say things like merge sort is faster or selection sort is slower. Use the exact time complexities. For example Bubble sort with early exit is adaptive and has a time complexity of O(n) on ordered data, whereas quicksort has a time complexity of O(n^2) for ordered data etc.

For programming questions:

Do not change the structs we give you unless it says you can in the instructions
Do not free things we have passed into your functions unless it tells you to
You will not get many marks for code that does not compile. You will most likely get 0.
If you have time go back and make up your own tests to thoroughly test your functions - you will be given the test code in the final exam so this will help.

Exam Content

Not in the exam

Makefiles

Things you will NOT have to code in the exam

Note: these are things you need to understand, you may have to trace through or understand the time complexity of, know when to use etc but will not be asked to write the code for. You should understand how the code works though to thoroughly understand the concepts. You could be given the code for it and asked to use it for a given problem.

Shell sort
Splay trees
Kruskal's algorithm

Prac test 2

Exam Format

1 and 1/2 hours
3 Programming Questions worth 10 marks each. 2 Short answer questions worth 5 marks each. 5 multiple choice questions worth 2 marks each.

Exam Content

Content up to and including all graph material.

Possible programming questions

programming question on linked lists/sorting linked lists
programming question on a binary search trees (just the normal binary search trees - not the alternative implementation with the size nodes or rotations etc)
programming question on graphs

Short answer questions and multiple choice

Prac test 1

Exam Format

1 and 1/2 hours
5 Programming Questions of equal weight

Exam Content

Things in the exam

programming questions on linked lists
programming questions on a binary search trees
programming using recursion

Exam Instructions for Prac Test 1

The prac exam consists of five questions and you have 1 hour and 30 minutes to solve the questions. Each question is worth 10 marks.

As always, it is a good idea to start with the simplest question - be mindful of the time, if you get stuck, try to move to the next question and come back to the problem later.

The submission instructions are detailed in the file for each question. When submitting your program, the system will run a couple of simple tests. The test code is not available, but if a test fails, you can use gdb, set a break point at the function you implemented, and step through the execution to see where things are going wrong.

Each question is described in the corresponding .c file

Exam Tips for Prac Test 1

Do not modify the .h files.
You may always write additional static helper functions in your c file.
Do not change the structs we give you unless it says you can in the instructions
Do not free things we have passed into your functions unless it tells you to
You will not get many marks for code that does not compile
You will be given a .o file for the tests that we run for submission. You will not have access to the .c test files. If you have time make up your own tests to thoroughly test your functions as we test things more thoroughly when we mark them.

Sample BST programming question

This is to give you practice following instructions for the prac exam.

Files for this task

`deleteLargest.c`	A BST implementation you need to write a function for
`deleteLargest.h`	An interface for the BST. You must not modify this
`deleteLargest.o`	A simple test binary file for your implementation. You may wish to write your own extra test file for this question to test more thoroughly.

The instructions for the task are detailed in the file for the question. The test code is not available, but if a test fails, you can use gdb, set a break point at the function you implemented, and step through the execution to see where things are going wrong.

Note: the .o file has been compiled using cse machines. It may not work on your machine at home. deleteLargestSoln.c

Resources

During the exam you will have access to the following Reference Card (pdf)