xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Java代写-COMP3506/COMP7505

时间：2021-02-03

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 1 of 13

School of Information Technology and Electrical Engineering

EXAMINATION

Semester Two Def/Supp Examination, 2020

COMP3506/COMP7505 Algorithms and Data Structures

This paper is for all students.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 2 of 13

Question 1 (9 marks)

a) Use the definition of big-Theta notation to show 7 + n + 5n log n is Θ(n log n).

(2 marks)

The following algorithm takes a non-empty proper binary tree and prints it. You may

wish to recall that a proper binary tree is a binary tree in which each node is either

external or has exactly two children. The expression newIndent ¬ indent + " " creates

a new string that contains the characters in the string indent appended by the single

space character and assigns it to the variable newIndent. The string indent is not

modified by the assignment: the characters from it are copied over to the newly created

string.

Algorithm: print(tree)

return printHelper(tree, tree.root(), "")

Algorithm: printHelper(tree, node, indent)

System.out.println(indent);

System.out.println(node.getElement());

if tree.isInternal(node) then

newIndent ¬ indent + " "

printHelper(tree, tree.leftChild(node), newIndent)

printHelper(tree, tree.rightChild(node), newIndent)

return

b) What is the maximum height of a non-empty proper binary tree containing n nodes

in total? Count the height of a leaf node as being 0.

(2 marks)

c) What is the worst-case time complexity of the above algorithm print, given that

there are n nodes in the parameter tree and that each element in a node is a string

of no more than 30 characters? Express your answer in terms of n in big-O

notation, making the bound as tight as possible and simplifying your answer as

much as possible. Briefly justify your answer and give an example tree of n=7

nodes that would exhibit the worst-case time complexity.

(2 marks)

d) What is the worst-case space complexity of the above algorithm print, given that

there are n nodes in the parameter tree and that each element in a node is a string

of no more than 30 characters? Assume that the parameters in the algorithm and

its helper algorithm are passed by reference. Do not include the space already

consumed by the tree in your calculation. Express your answer in terms of n in

big-O notation, making the bound as tight as possible and simplifying your answer

as much as possible. Briefly justify your answer and give an example tree of n=7

nodes that would exhibit the worst-case space complexity.

(3 marks)

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 3 of 13

Answer Q1 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 4 of 13

Question 2 (7 marks)

a) A bucket sort uses key values as indices into an auxiliary array as part of the

sorting process. Explain how a collection of strings can be sorted using a bucket

sort.

(2 marks)

b) A radix sort is a specialised type of lexicographic sort.

i. Explain how a radix sort can be used to sort a collection of integers.

ii. Compare the performance of using a radix sort versus a bucket sort, to sort a

collection of n integers with values in the range of 0 to N. The comparison

should comment on both run-time complexity and space complexity of both

sorts.

(3 marks)

c) Comparison sorts perform their sorting process by comparing key values to

determine their relative ordering.

i. What is the best-case run-time performance of any comparison sort? Explain

how this can be determined.

ii. Is a bucket sort a comparison sort? Explain why or why not.

(2 marks)

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 5 of 13

Answer Q2 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 6 of 13

Question 3 (6 marks)

a) Construct the min-heap by inserting the keys, 6, 9, 4, 3, 2 and 7, one at a time, in

that order, to an initially empty heap. Draw the heap after each step.

(2 marks)

b) The following tree is a (2,4) tree after inserting the keys 12, 25, 2, 32, 65. Draw

the resulting (2,4) tree after inserting the key 15. Describe what steps were

involved in making the change to the tree’s structure.

(2 marks)

c) Out of the following search trees: AVL trees, Splay trees, (2,4) trees, B-Trees and

red-black trees, which one would be most appropriate for implementing an

Ordered Map that is expected to contain more entries than can be reasonably

expected to fit in main memory? Why?

(2 marks)

12

2 25 32 65

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 7 of 13

Answer Q3 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 8 of 13

Question 4 (3 marks)

Consider character string key consisting of three characters c1, c2, c3 and the

following hash functions for a hash table of size 1250 with linear probing. Which of

the following hash functions are good (less collisions) ones? Describe your answer

briefly. For each hash function, talk about the cases where you get collisions.

a) H1= c1 +5∗c2 mod 1250

b) H2= 10∗c1 +100∗c2 +1000∗c3 mod 1250

c) H3= 11∗c1 +101∗c2 +1001∗c3 mod 1250

Answer Q4 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 9 of 13

Question 5 (6 marks)

a) Represent the last occurrence function for the pattern P="structure", which is used

as part of the Boyer-Moore pattern matching algorithm.

(2 marks)

b) Draw a Standard Trie for the following set of strings: {ab, aa, aab, baa, caab}

(2 mark)

c) Using Huffman’s algorithm, construct a Huffman tree that defines an optimal prefix

code for the string “havaianas”. Show the intermediate states of the priority queue.

(2 marks)

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 10 of 13

Answer Q5 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 11 of 13

Question 6 (9 marks)

A graph is simple if it contains no self-loops (no edges from a vertex to itself) or parallel

edges (i.e. for any pair of vertices v and u, there is at most one edge from v to u).

a) Draw an adjacency matrix representation of the following simple directed graph.

(1 marks)

b) An alternative way to represent a simple undirected graph is to store a list of

vertices in the graph together with a hash table that maps pairs of vertices to

edges. The hash table contains an entry with key (v, u) and value e, if and only if

there is an edge e from vertex v to u in the graph. For instance the directed graph

in part (a) would be represented by the list [v1, v2, v3, v4, v5] of vertices together

with a hash table containing entries ((v1, v4), e1), ((v2, v1), e2), ((v4, v5), e3),

((v5, v3), e4) and ((v1, v5), e5).

Assuming that this alternative representation is well implemented, compare it to

the adjacency matrix representation, taking into consideration the following

aspects:

i. For any two vertices v and u, the time complexity for determining if v and u

are adjacent.

ii. For any vertex v, the time-complexity of creating a list of all of the vertices u

such that there is an edge from vertex v to u.

iii. The space complexity of the different representations.

(6 marks)

c) Decide whether these statements are True or False. You must briefly justify all

your answers to receive full credit.

i. Given an undirected graph, it can be tested to determine whether or not it is

a tree in linear time.

ii. The topological sort of an arbitrary directed acyclic graph G = (V, E) can be

computed in linear time.

(2 marks)

v1 v2

v4 v5

v3

e1

e3

e2

e5 e4

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 12 of 13

Answer Q6 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 13 of 13

Question 7 (0 marks)

Please specify any assumptions you have made in completing this examination and

which questions those assumptions relate to. You may also include queries you may

have made with respect to a particular question, should you have been able to ‘raise

your hand’ in an examination room.

Answer Q7 here.

END OF EXAMINATION

学霸联盟

Page 1 of 13

School of Information Technology and Electrical Engineering

EXAMINATION

Semester Two Def/Supp Examination, 2020

COMP3506/COMP7505 Algorithms and Data Structures

This paper is for all students.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 2 of 13

Question 1 (9 marks)

a) Use the definition of big-Theta notation to show 7 + n + 5n log n is Θ(n log n).

(2 marks)

The following algorithm takes a non-empty proper binary tree and prints it. You may

wish to recall that a proper binary tree is a binary tree in which each node is either

external or has exactly two children. The expression newIndent ¬ indent + " " creates

a new string that contains the characters in the string indent appended by the single

space character and assigns it to the variable newIndent. The string indent is not

modified by the assignment: the characters from it are copied over to the newly created

string.

Algorithm: print(tree)

return printHelper(tree, tree.root(), "")

Algorithm: printHelper(tree, node, indent)

System.out.println(indent);

System.out.println(node.getElement());

if tree.isInternal(node) then

newIndent ¬ indent + " "

printHelper(tree, tree.leftChild(node), newIndent)

printHelper(tree, tree.rightChild(node), newIndent)

return

b) What is the maximum height of a non-empty proper binary tree containing n nodes

in total? Count the height of a leaf node as being 0.

(2 marks)

c) What is the worst-case time complexity of the above algorithm print, given that

there are n nodes in the parameter tree and that each element in a node is a string

of no more than 30 characters? Express your answer in terms of n in big-O

notation, making the bound as tight as possible and simplifying your answer as

much as possible. Briefly justify your answer and give an example tree of n=7

nodes that would exhibit the worst-case time complexity.

(2 marks)

d) What is the worst-case space complexity of the above algorithm print, given that

there are n nodes in the parameter tree and that each element in a node is a string

of no more than 30 characters? Assume that the parameters in the algorithm and

its helper algorithm are passed by reference. Do not include the space already

consumed by the tree in your calculation. Express your answer in terms of n in

big-O notation, making the bound as tight as possible and simplifying your answer

as much as possible. Briefly justify your answer and give an example tree of n=7

nodes that would exhibit the worst-case space complexity.

(3 marks)

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 3 of 13

Answer Q1 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 4 of 13

Question 2 (7 marks)

a) A bucket sort uses key values as indices into an auxiliary array as part of the

sorting process. Explain how a collection of strings can be sorted using a bucket

sort.

(2 marks)

b) A radix sort is a specialised type of lexicographic sort.

i. Explain how a radix sort can be used to sort a collection of integers.

ii. Compare the performance of using a radix sort versus a bucket sort, to sort a

collection of n integers with values in the range of 0 to N. The comparison

should comment on both run-time complexity and space complexity of both

sorts.

(3 marks)

c) Comparison sorts perform their sorting process by comparing key values to

determine their relative ordering.

i. What is the best-case run-time performance of any comparison sort? Explain

how this can be determined.

ii. Is a bucket sort a comparison sort? Explain why or why not.

(2 marks)

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 5 of 13

Answer Q2 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 6 of 13

Question 3 (6 marks)

a) Construct the min-heap by inserting the keys, 6, 9, 4, 3, 2 and 7, one at a time, in

that order, to an initially empty heap. Draw the heap after each step.

(2 marks)

b) The following tree is a (2,4) tree after inserting the keys 12, 25, 2, 32, 65. Draw

the resulting (2,4) tree after inserting the key 15. Describe what steps were

involved in making the change to the tree’s structure.

(2 marks)

c) Out of the following search trees: AVL trees, Splay trees, (2,4) trees, B-Trees and

red-black trees, which one would be most appropriate for implementing an

Ordered Map that is expected to contain more entries than can be reasonably

expected to fit in main memory? Why?

(2 marks)

12

2 25 32 65

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 7 of 13

Answer Q3 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 8 of 13

Question 4 (3 marks)

Consider character string key consisting of three characters c1, c2, c3 and the

following hash functions for a hash table of size 1250 with linear probing. Which of

the following hash functions are good (less collisions) ones? Describe your answer

briefly. For each hash function, talk about the cases where you get collisions.

a) H1= c1 +5∗c2 mod 1250

b) H2= 10∗c1 +100∗c2 +1000∗c3 mod 1250

c) H3= 11∗c1 +101∗c2 +1001∗c3 mod 1250

Answer Q4 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 9 of 13

Question 5 (6 marks)

a) Represent the last occurrence function for the pattern P="structure", which is used

as part of the Boyer-Moore pattern matching algorithm.

(2 marks)

b) Draw a Standard Trie for the following set of strings: {ab, aa, aab, baa, caab}

(2 mark)

c) Using Huffman’s algorithm, construct a Huffman tree that defines an optimal prefix

code for the string “havaianas”. Show the intermediate states of the priority queue.

(2 marks)

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 10 of 13

Answer Q5 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 11 of 13

Question 6 (9 marks)

A graph is simple if it contains no self-loops (no edges from a vertex to itself) or parallel

edges (i.e. for any pair of vertices v and u, there is at most one edge from v to u).

a) Draw an adjacency matrix representation of the following simple directed graph.

(1 marks)

b) An alternative way to represent a simple undirected graph is to store a list of

vertices in the graph together with a hash table that maps pairs of vertices to

edges. The hash table contains an entry with key (v, u) and value e, if and only if

there is an edge e from vertex v to u in the graph. For instance the directed graph

in part (a) would be represented by the list [v1, v2, v3, v4, v5] of vertices together

with a hash table containing entries ((v1, v4), e1), ((v2, v1), e2), ((v4, v5), e3),

((v5, v3), e4) and ((v1, v5), e5).

Assuming that this alternative representation is well implemented, compare it to

the adjacency matrix representation, taking into consideration the following

aspects:

i. For any two vertices v and u, the time complexity for determining if v and u

are adjacent.

ii. For any vertex v, the time-complexity of creating a list of all of the vertices u

such that there is an edge from vertex v to u.

iii. The space complexity of the different representations.

(6 marks)

c) Decide whether these statements are True or False. You must briefly justify all

your answers to receive full credit.

i. Given an undirected graph, it can be tested to determine whether or not it is

a tree in linear time.

ii. The topological sort of an arbitrary directed acyclic graph G = (V, E) can be

computed in linear time.

(2 marks)

v1 v2

v4 v5

v3

e1

e3

e2

e5 e4

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 12 of 13

Answer Q6 here.

Semester Two Def/Supp Examinations, 2020 COMP3506/COMP7505 Algorithms and Data Structures

Page 13 of 13

Question 7 (0 marks)

Please specify any assumptions you have made in completing this examination and

which questions those assumptions relate to. You may also include queries you may

have made with respect to a particular question, should you have been able to ‘raise

your hand’ in an examination room.

Answer Q7 here.

END OF EXAMINATION

学霸联盟