xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

COMP3506/COMP7505-Java代写

时间：2021-02-03

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

1

School of Information Technology and Electrical Engineering

EXAMINATION

Semester Two Final Examination, 2020

COMP3506/COMP7505 Algorithms and Data Structures

This paper is for all students.

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

2

Question 1 (2 marks)

What is the maximum possible number of external nodes in a binary tree with height

4? Give a brief description by drawing a resulting tree.

Question 2 (1 mark)

Consider the following Java program, containing a recursive method. When the class

ContainsRecursion is run, the final line of output will be:

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

3

Question 3 (4 marks)

a) Given two algorithms, A with O(n) time complexity, and B with Θ(n logn) time

complexity, testing shows that algorithm B is faster than algorithm A in practice

for all datasets tested. Give two possible reasons why this may be. (2 marks)

b) Given two algorithms for performing a task, is it ever reasonable to use the

algorithm with worse asymptotic performance? Why or why not? (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

4

Question 4 (2 marks)

Consider the following recurrences:

R1(n) = 4 R1(n/2) + O(1)

R2(n) = 2 R2(n/4) + O(1)

Explain which one is asymptotically faster and why? (2 marks)

Question 5 (2 marks)

Draw a table to represent the “last occurrence” function for the pattern P="baccarat",

which is used as part of the Boyer-Moore pattern matching algorithm.

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

5

Question 6 (4 marks)

A splay tree is populated by inserting into an empty tree the keys: 4, 15, 8, 16, 42, and

23, in that order.

a) Draw the final tree. No need to include the external leaves in the drawing. (2

marks)

b) What is the order that nodes are visited during a post-order traversal of the

resulting tree? (1 mark)

c) Draw a different splay tree with the same post order traversal. (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

6

Question 7 (2 marks)

We defined a hash function h(s) = s.size(), for a hash table which stores a set of

strings.

a) Explain why h(s) is not a good hash function. Note: size() returns the length of

the string. (1 mark)

b) Suggest an alternative hash function or technique that would perform more

suitably (and why?). (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

7

Question 8 (4 marks)

Arrays store a set of values by index using O(n) space, where n is the largest index in

use. In some cases, most indices of the array are null, wasting space; such arrays are

called sparse arrays. In other words, the number of non-default values stored m, is

much smaller than the largest index n.

a) Describe how you would efficiently implement a sparse array using a hash

table. What would be the worst-case time complexity of standard array

operations (insert, delete (moving indices of elements later in the array after

deletion), and search an item) in Big-O notation, if we implement sparse arrays

using hash tables? (2 marks)

b) Describe how you would efficiently implement a sparse array using a linked list.

What would be the worst-case time complexity of standard array operations in

Big-O notation, if we implement sparse arrays using linked lists? (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

8

Question 9 (2 marks)

Below is a Huffman tree generated from the exact frequencies of the text: "this is an

example of a huffman tree"

Using the Huffman tree above, determine the binary code and count the number of

bits required to transmit the text “fill pool” (do not forget the space separating the

words). Note: Left branches represented a 0 bit and right branches represent a 1 bit.

CODE=

#BITS=

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

9

Question 10 (5 marks)

For each of the following scenarios, suggest an efficient and suitable sorting algorithm

(out of the ones we learned in this course), and explain why you chose it. Note: n

potentially is very large.

(a) We have an array consisting of n objects in random order. The objects are

comparable, and not necessarily numbers. (1 mark)

(b) We have an array consisting of n objects. The objects are comparable. Apart from

d items (d< log2n) that are in random positions in this array, all the other items are

in sorted order. (2 marks)

(c) We have an array consisting of n random integers in the range of 0 to d, with d<

log2n. (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

10

Question 11 (4 marks)

a) Given a semi-balanced binary tree with n nodes, where the number of leaves

in the corresponding left and right subtrees differs at most by one. Explain the

worst-case height of the tree. Note: Write the Big-O with respect to the number

of nodes (n). (2 marks)

b) Given a semi-balanced binary tree with n nodes, where the number of nodes in

the left subtree is at most twice the number of nodes in the corresponding right

subtree. Explain the worst-case height of the tree. Note: Write the Big-O with

respect to the number of nodes (n). (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

11

Question 12 (4 marks)

Given an unweighted graph G with n vertices and the adjacency matrix A:

a) Given a positive integer k, propose an algorithm (give a pseudo-code or

explain in words) to calculate the number of walks (vertices/edges can

be revisited) consisting of exactly k number of edges between vertices i

and j. Your algorithm should return 0 if there are no walks of length k. (3

marks)

b) What is the worst-case time complexity of your proposed algorithm in terms of

n and k? and explain why. (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

12

Question 13 (4 marks)

Work out the most efficient Big-O time complexity of finding pth smallest element in a

BST with m elements. Hint: The Big-O will be in terms of m and p. Describe in words

your proposed algorithm.

End of Examination

1

School of Information Technology and Electrical Engineering

EXAMINATION

Semester Two Final Examination, 2020

COMP3506/COMP7505 Algorithms and Data Structures

This paper is for all students.

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

2

Question 1 (2 marks)

What is the maximum possible number of external nodes in a binary tree with height

4? Give a brief description by drawing a resulting tree.

Question 2 (1 mark)

Consider the following Java program, containing a recursive method. When the class

ContainsRecursion is run, the final line of output will be:

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

3

Question 3 (4 marks)

a) Given two algorithms, A with O(n) time complexity, and B with Θ(n logn) time

complexity, testing shows that algorithm B is faster than algorithm A in practice

for all datasets tested. Give two possible reasons why this may be. (2 marks)

b) Given two algorithms for performing a task, is it ever reasonable to use the

algorithm with worse asymptotic performance? Why or why not? (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

4

Question 4 (2 marks)

Consider the following recurrences:

R1(n) = 4 R1(n/2) + O(1)

R2(n) = 2 R2(n/4) + O(1)

Explain which one is asymptotically faster and why? (2 marks)

Question 5 (2 marks)

Draw a table to represent the “last occurrence” function for the pattern P="baccarat",

which is used as part of the Boyer-Moore pattern matching algorithm.

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

5

Question 6 (4 marks)

A splay tree is populated by inserting into an empty tree the keys: 4, 15, 8, 16, 42, and

23, in that order.

a) Draw the final tree. No need to include the external leaves in the drawing. (2

marks)

b) What is the order that nodes are visited during a post-order traversal of the

resulting tree? (1 mark)

c) Draw a different splay tree with the same post order traversal. (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

6

Question 7 (2 marks)

We defined a hash function h(s) = s.size(), for a hash table which stores a set of

strings.

a) Explain why h(s) is not a good hash function. Note: size() returns the length of

the string. (1 mark)

b) Suggest an alternative hash function or technique that would perform more

suitably (and why?). (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

7

Question 8 (4 marks)

Arrays store a set of values by index using O(n) space, where n is the largest index in

use. In some cases, most indices of the array are null, wasting space; such arrays are

called sparse arrays. In other words, the number of non-default values stored m, is

much smaller than the largest index n.

a) Describe how you would efficiently implement a sparse array using a hash

table. What would be the worst-case time complexity of standard array

operations (insert, delete (moving indices of elements later in the array after

deletion), and search an item) in Big-O notation, if we implement sparse arrays

using hash tables? (2 marks)

b) Describe how you would efficiently implement a sparse array using a linked list.

What would be the worst-case time complexity of standard array operations in

Big-O notation, if we implement sparse arrays using linked lists? (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

8

Question 9 (2 marks)

Below is a Huffman tree generated from the exact frequencies of the text: "this is an

example of a huffman tree"

Using the Huffman tree above, determine the binary code and count the number of

bits required to transmit the text “fill pool” (do not forget the space separating the

words). Note: Left branches represented a 0 bit and right branches represent a 1 bit.

CODE=

#BITS=

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

9

Question 10 (5 marks)

For each of the following scenarios, suggest an efficient and suitable sorting algorithm

(out of the ones we learned in this course), and explain why you chose it. Note: n

potentially is very large.

(a) We have an array consisting of n objects in random order. The objects are

comparable, and not necessarily numbers. (1 mark)

(b) We have an array consisting of n objects. The objects are comparable. Apart from

d items (d< log2n) that are in random positions in this array, all the other items are

in sorted order. (2 marks)

(c) We have an array consisting of n random integers in the range of 0 to d, with d<

log2n. (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

10

Question 11 (4 marks)

a) Given a semi-balanced binary tree with n nodes, where the number of leaves

in the corresponding left and right subtrees differs at most by one. Explain the

worst-case height of the tree. Note: Write the Big-O with respect to the number

of nodes (n). (2 marks)

b) Given a semi-balanced binary tree with n nodes, where the number of nodes in

the left subtree is at most twice the number of nodes in the corresponding right

subtree. Explain the worst-case height of the tree. Note: Write the Big-O with

respect to the number of nodes (n). (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

11

Question 12 (4 marks)

Given an unweighted graph G with n vertices and the adjacency matrix A:

a) Given a positive integer k, propose an algorithm (give a pseudo-code or

explain in words) to calculate the number of walks (vertices/edges can

be revisited) consisting of exactly k number of edges between vertices i

and j. Your algorithm should return 0 if there are no walks of length k. (3

marks)

b) What is the worst-case time complexity of your proposed algorithm in terms of

n and k? and explain why. (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures

12

Question 13 (4 marks)

Work out the most efficient Big-O time complexity of finding pth smallest element in a

BST with m elements. Hint: The Big-O will be in terms of m and p. Describe in words

your proposed algorithm.

End of Examination