[SOLVED] CS 2521 Final Exam

Final Exam

Changelog

All changes to the exam paper and files will be listed here.

Rules & Overview

General

By completing the acknowledgement and starting this exam you have acknowledged that you are fit to sit the exam and cannot apply for Special Consideration for issues that existed prior to the exam

If during the exam a circumstance arises that prevents you from completing the exam, please email cs2521@cse.unsw.edu.au immediately and apply for special consideration shortly after

During the exam no communication is allowed with other people, excluding any common sense exceptions (e.g. answering “how are you?“ if a parent asks you)

If you have any questions during the exam, make a private post on the Ed forum (the same one we‘ve been using all term)

Do not wait until just before the deadline to submit all your answers. Submit each question as soon as you finish working on it or submit incrementally throughout the exam.

Programming Questions

All inputs will be valid.

You may define your own helper functions.

You may not #include any additional libraries.

You may add your own #defines or define your own structs/enums if you require them for your solution. You may use global variables and static variables.

Solutions which do not attempt to solve the question generally but instead only hardcode return values for specific tests will receive zero marks.

Admin

Marks Contributes 40% towards your final mark

Submit See the submission instructions for each question Date and time Thursday 19th August 9am-12pm

Total Marks 100

Total number of questions 14 (not worth equal marks)

Structure

This exam consists of a series of questions:

30 marks for written short/extended answers 70 marks for programming questions

Setting Up

Change into the directory you created for the sample exam and run the following command:

If you‘re working at home, download files.zip by clicking on the above link and then unzip the downloaded file.

Question 1 (4 marks)

Consider the following scenario:

Of the 3 graph representations discussed in the course, which would be most appropriate for use in this scenario? Justify your answer.

Write your answer in q1.txt

Expected response size: 30-100 words

Submission

Submit via the give command

Question 2 (4 marks)

Consider the following scenario:

Which hash collision method would be most appropriate in this scenario? Summarise the way this particular method works, and use it to justify your answer.

Write your answer in q2.txt

Expected response size: 50-150 words

Submission

Submit via the give command

Question 3 (3 marks)

Describe the types of data or scenario(s) in which heap sort would be an ideal sort to use. Write your answer in q3.txt

Expected response size: 30-100 words

Submission

Submit via the give command

Question 4 (3 marks)

Does an Euler path (NOT an Euler circuit) exist for this graph? Justify your answer. Write your answer in q4.txt

Expected response size: 30-100 words

Submission

Submit via the give command

Question 5 (3 marks)

What is a limitation of recursive solutions (as opposed to iterative solutions)? Describe an example. Write your answer in q5.txt

Expected response size: 10-50 words

Submission

Submit via the give command

Question 6 (2 marks)

Consider the following function:

What is the best and worst case time complexity for the function above? Write your answer in q6.txt

Provide time complexities with respect to n. printf() can be assumed to always be O(1).

Submission

Submit via the give command

Question 7 (3 marks)

Consider the following function:

What is the best and worst case time complexity for the function above? Write your answer in q7.txt

Provide time complexities with respect to n and m. Note that randInt is a function that generates a random number, and

insertionSort is a function that uses standard insertion sort to sort an array between two bounds. malloc(), randInt() and printf() can be assumed to always be O(1).

Submission

Submit via the give command

Question 8 (5 marks)

Describe the key differences between quicksort and mergesort, which includes at least:

Their respective best and worst case time complexities

Examples of circumstances where you would prefer to use one over the other

You can assume the quicksort is a median–of–three quicksort. Write your answer in q8.txt

Expected response size: 50-150 words

Submission

Submit via the give command

Question 9 (3 marks)

Is this minimum spanning tree being generated with Prim‘s or Kruskal‘s algorithm, or could it be generated by either? Justify your answer.

Note: This MST is mid-construction, and the green lines denote what has been constructed so far. Write your answer in q9.txt

Expected response size: 30-80 words

Submission

Submit via the give command

Question 10 (9 marks)

Implement the following function in the file q10/equalBST.c:

equalBST takes two binary search trees. It should return 1 if the trees are equal, and 0 otherwise. Two binary search trees are considered to be equal if they have the same structure and corresponding values.

Constraints

The given trees must not be modified.

The time complexity of your solution must be approximately O(n + m), where n and m represent the number of nodes in t1 and t2 respectively. If your solution is slower than O(n + m), the maximum mark you can attain for this question will be 7 (out of 9). Note that a fairly standard solution is easily complexity O(n + m).

Files

BSTree.c	Contains the implementation of basic binary search tree functions.
BSTree.h	Contains the definition of the binary search tree data structure and function prototypes.
testEqualBST.c	A testing program. The program reads tree data from stdin, calls equalBST, and outputs the result to stdout.
equalBST.c	This is the only file you‘re required to modify. Contains equalBST, the function you must implement.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases

Examples

The following are examples of how the program should behave:

In the last example, empty trees were created by pressing enter without typing any numbers.

Testing

You can compile and test your function using the following commands:

$ make

$ ./testEqualBST

$ ./testEqualBST < input-file

$ ./testEqualBST < tests/input1.txt

# compiles the program

# tests with manual input, outputs to terminal

# tests with input from a file, outputs to terminal

# for example, tests with input from tests/input1.txt

Submission

Submit via the give command

Question 11 (14 marks)

Implement the following function in the file q11/printWords.c:

printWords takes one argument: a pointer to the root node of a Trie. It should print all the words in the trie to stdout in alphabetical order, one per line.

Assumptions

Words consist only of lowercase alphabetic characters.

Words are between 1 and 64 characters in length (inclusive).

Constraints

The given trie must not be modified.

Files

Trie.c	Contains the implementation of a trie and associated functions.
Trie.h	Contains the definition of the trie and function prototypes.
testTriePrintWords.c	A testing program. The program reads trie data from stdin and calls printWords.
printWords.c	This is the only file you‘re required to modify. Contains printWords, the function you must implement.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases

Examples

The following are examples of how the program should behave:

Testing

You can compile and test your function using the following commands:

$ make

$ ./testTriePrintWords

$ ./testTriePrintWords < input-file

$ ./testTriePrintWords < tests/input1.txt

# compiles the program

# tests with manual input, outputs to terminal

# tests with input from a file, outputs to terminal

# for example, tests with input from tests/input1.txt

Submission

Submit via the give command

Question 12 (14 marks)

Implement the following function in the file q12/mergeOrdered.c:

mergeOrdered takes two ordered lists, each of which is in non-decreasing order (i.e., increasing order potentially with duplicates). It should merge the two ordered lists together into a new list that is also in non-decreasing order and return the merged list.

Assumptions

The given lists will be in non-decreasing order.

The given lists may contain duplicate values. Duplicate values may be added to the merged list in any order. You may use the functions in list.h.

Constraints

The function must always return a new list. The given lists must not be modified.

You must not use arrays, either directly or indirectly. If you don‘t satisfy this requirement, you will receive zero for this question.

Files

list.c	Contains the implementation of basic linked list functions.
list.h	Contains the definition of the linked list data structure and function prototypes.
testMergeOrdered.c	A testing program. The program reads list data from stdin, calls mergeOrdered, and outputs the result to stdout.
mergeOrdered.c	This is the only file you‘re required to modify. Contains mergeOrdered, the function you must implement.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases

Examples

The following are examples of how the program should behave:

$ ./testMergeOrdered

1 4 6

list1: 1, 4, 6

2 8 10 15

list2: 2, 8, 10, 15

merged list: 1, 2, 4, 6, 8, 10, 15

In the last example, an empty list was created by pressing enter without typing any numbers.

Testing

You can compile and test your function using the following commands:

$ make

$ ./testMergeOrdered

$ ./testMergeOrdered < input-file

$ ./testMergeOrdered < tests/input1.txt

# compiles the program

# tests with manual input, outputs to terminal

# tests with input from a file, outputs to terminal

# for example, tests with input from tests/input1.txt

Submission

Submit via the give command

Question 13 (14 marks)

Implement the following function in the file q13/nodesNotBalanced.c.

nodesNotBalanced takes one argument: a binary search tree t. It should return the number of nodes in the tree that are not height-balanced.

Constraints

The given tree must not be modified.

You must not use arrays or any variant of malloc, either directly or indirectly. If you don‘t satisfy this requirement, you will receive zero for this question.

Files

BSTree.c	Contains the implementation of basic binary search tree functions.
BSTree.h	Contains the definition of the binary search tree data structure and function prototypes.
testNodesNotBalanced.c	A testing program. The program reads tree data from stdin, calls nodesNotBalanced, and outputs the result to stdout.
nodesNotBalanced.c	This is the only file you‘re required to modify. Contains nodesNotBalanced, the function you must implement.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases

Examples

The following are examples of how the program should behave:

$ ./testNodesNotBalanced

5 4 3 2 1 7 6 8

Tree:

5

/

4

/

7

/

3 6 8

/

2

/

1

nodesNotBalanced returned: 3

Testing

You can compile and test your function using the following commands:

$ make

$ ./testNodesNotBalanced

$ ./testNodesNotBalanced < input-file

$ ./testNodesNotBalanced < tests/input1.txt

# compiles the program

# tests with manual input, outputs to terminal

# tests with input from a file, outputs to terminal

# for example, tests with input from tests/input1.txt

Submission

Submit via the give command

Question 14 (19 marks)

Implement the following function in the file q14/rankPopularity.c:

rankPopularity takes three arguments: a directed graph g, a source node src, and an array mnV. For each node reachable from src (and only these nodes), the function should calculate the popularity rank of that node and store it in the array mnV. For example, mnV[2] should contain the popularity rank of node 2 if node 2 is reachable from src.

Important: If a node is not reachable from src, the function should not calculate and store the popularity rank of that node. Only nodes reachable from src should be considered. In the test program testRankPopularity.c, all values in mnV are initialised to

-1.0. If a node v is not reachable, mnV[v] should remain as -1.0. If you change the value, you will fail the test.

Assumptions

You can assume that the array mnV has size n, where n is the number of nodes in the graph.

Constraints

The given graph must not be modified.

Files

Graph.c	Contains the implementation of basic Graph ADT functions.
Graph.h	Contains the definition of the Graph ADT and function prototypes.
testRankPopularity.c	A testing program. The program reads graph data, calls rankPopularity, and outputs the results to stdout.
rankPopularity.c	This is the only file you‘re required to modify. Contains rankPopularity, the function you must implement.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases

Example

For example, consider the following graph:

The popularity ranks for nodes reachable from node 3 in the above graph are: popularityRank(0) = 3/1 = 3.0

popularityRank(2) = 2/2 = 1.0 popularityRank(3) = 1/2 = 0.5

popularityRank(4) = 3/0.5 = 6.0 (since outDegree(4) = 0, we have used 0.5 instead)

Note that node 1 is not reachable from node 3, so it must be ignored and its popularity rank must remain as -1.

Testing

You can compile and test your function using the following commands:

$ make

$ ./testRankPopularity < input-file

$ ./testRankPopularity < tests/input1.txt

# compiles the program

# tests with input from a file, outputs to terminal

# for example, tests with input from tests/input1.txt

Submission

Submit via the give command

This is the end of the exam.

COMP2521 21T2: Data Structures and Algorithms is brought to you by the School of Computer Science and Engineering

at the University of New South Wales, Sydney.

For all enquiries, please email the class account at cs2521@cse.unsw.edu.au CRICOS Provider 00098G