CSCI 6010 Final Exam
Start Time: 8am 12 Dec. 2016; Due: 8am 13 Dec. 2016
Submit your solutions in the solution sheet provided.
solution(s). ( )
1. (Each 1 point; total 20%) Say True (T) or False (F) in the following statements.
(1) When an array is sorted, both quicksort and insertion sort perform in 𝑂(𝑛) time. ( )
(2) As far as a greedy algorithm guarantees exhibiting optimal substructure, it can find optimal
(3) Even if most scientists P ≠ NP, they agree with P ⊆ NP. In addition, they believe (P ∪NPC) ⊆ NP. ( )
(4) Minimum spanning tree should have exactly |𝑉| − 1 edges where V refers to the set of vertices in a graph G. ( )
(5) Shellsort takes advantage of Selection Sort’s best-case performance. ( )
(6) Quicksort is the fastest known general-purpose in-memory sorting algorithm in the average
case. ( )
(7) A binary tree of depth d can store at least 2𝑑+1 − 1 nodes. ( )
(8) A graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique
light edge crossing the cut. ( )
(9) A binding property can be bound to an observable source object. A change in the target
object will be automatically reflected in the binding property. A binding property has a value
getter method, value setter method, and property getter method. ( )
(10) If the propagation delay is long in packet delivery, it implies low bandwidth. ( ) (11) Proactive routing is more resource-efficient in finding routes from a source to a
destination than reactive routing. ( )
(12) For voice or image data transfer, TCP is used because users may not recognize much
difference of quality-of-service provided due to unreliable data delivery. ( )
(13) In circuit switching, TDM can provide lower delay than FDM in message delivery
because it can ensure that each signal uses all of the bandwidth some of the time. ( ) (14) Intrusion detection systems are developed for security against outside attackers. (
(15) If you cannot solve a problem in a polynomial time, the problem may or may not be NP.
()
(16) In key management using a symmetric key (a secret key or a group key), when a new
member joins in a secure group communication, the group key should be changed in order to
maintain backward secrecy. ( )
(17) Privacy is regarded as one of security goals in computer and network security. ( ) (18) In the cybersecurity domain, risk is often defined as the probability that a system has a
large number of vulnerabilities. ( )
(19) Dynamic programming is more efficient that greedy algorithms. ( )
(20) In multithreading, resolving the starvation issue also increases performance. ( )
)
2. (5%) In Radix Sort, where the maximum number of digits of an input number (integer) is 3 (i.e., 𝑘 = 3), the number of bins is 𝑟, and the number of keys is 𝑛, compare asymptotic complexity in Ɵ for the following two cases:
(1) When the original algorithm of radix sort is used (2.5%)
(2) When the radix sort is modified by sorting based on the maximum digit with k = 3 first and then by sorting of a sublist in each bin (2.5%). Use the asymptotic complexity for the sorting of a sublist in each bin with θ(𝑛 log 𝑛).
3. (5%) (1) Graph f1(n) = n log n, f2(n) = n1.5, and f3(n) = n2 in the range 1 ≤ n ≤ 1000 to visually compare their growth rates. Typically, the constant factor in the running-time expression for an implementation of Insertion Sort will be less than the constant factors for Shellsort or Quicksort (2%). (2) How many times greater can the constant factor be for Shellsort to be faster than Insertion Sort when n = 1000? (1.5%) (3) How many times greater can the constant factor be for Quicksort to be faster than Insertion Sort when n = 1000? (1.5%)
4. (5%) Give a dynamic programming (DP) algorithm for the activity-selection problem (Chap. 16, p. 415 in Cormen’s book) and compare the running time of the DP solution with that of the greedy algorithm. Discuss the reason for the difference.
5. (6%) Evaluate the following two hash functions by (1) (3%) calculating the keys hashed by the given hash functions respectively (i.e., 5 hash keys after performing the respective hash functions); (2) (3%) discussing which hash function is better than the other in terms of the key uniqueness, space utilization, and the speed of computation and also why you reached this conclusion.
Hash function A: h𝑎𝑠h(𝑘) = 𝑘%𝑚
Hash function B: h𝑎𝑠h(𝑘) = ⌊𝑚(𝑘𝐴%1)⌋
where m = 20, A = 0.618. We only want to hash the following keys: 1, 15672, 300, 478123, 34. Assume that we will not add more keys to this hash table and the length of a hash table will be determined based on a maximum key value generated by each hash function.
6. (5%) Answer the following questions based on the graph shown:
(1) (2.5%) Use Kruskal’s algorithm to find a minimum spanning tree and indicate the edges in the graph. Indicate on the edges that are selected the order of their selection and show the total distance; and
(2) (2.5%) Use Prim’s algorithm to find the minimum spanning tree and indicate the edges in the graph shown left (start from A). Indicate on the edges that are selected the order of their selection and show the total distance.
7. (10%) Answer the following questions on B-tree.
(1) (5%) Show the results of inserting the keys 50, 10, 25, 30, 40, 45, 70, 90, 95, 48, 60, 80,
35, 75, 43, 32, 78, 65, 55, 68, 99, 92, 96, 98, 94 in order into an empty B-tree with minimum degree 2. Draw only the configurations of the tree just before some node must split, and also draw the final configuration.
(2) (5%) From the tree constructed in (1) above, show the results of deleting the keys 95, 80, 55, 60, 75, 40, 25, 30, 92, 90, 70, 32, 45, 99 in order with the minimum degree 2. Draw only the configurations of the tree just before some node must merge or switch positions, and also draw the final configuration.
8. (2%) Using Depth First Search (DFS), show the discovery time and finishing time in each vertex, for example, (mask.d, mask.f), starting from batting glove like Figure 22.7.a (p.613).
9. (11%) Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the following probabilities:
(1) (6%) Show the three tables as shown in Figure 15.10 (p. 403): 𝑒[𝑖, 𝑗], 𝑤[𝑖, 𝑗] and 𝑟𝑜𝑜𝑡[𝑖, 𝑗].
(2) (3%) Show the tree.
(3) (2%) Give the total cost.
I
0
1
2
3
4
5
6
7
pi
0.04
0.06
0.08
0.02
0.10
0.12
0.14
qi
0.06
0.06
0.06
0.06
0.05
0.05
0.05
0.05
10. (10%; 2% each) Write code statement(s) or answer for the following questions.
(1) (2%) What is the parameter type for the setOnAction method?
(2) (2%) What is the method for registering an action event handler on a button?
(3) (2%) Suppose there are three Runnable tasks, task1, task2, task3. How do you run them in a thread pool with 2 fixed threads? Write the code snippet.
(4) (2%) A thread instance t (i.e., Thread t = new Thread(task)) is started with t.start() and is in sleep with Thread.sleep(200). You want to awake the thread t and make it a Ready state. To do so, you need to throw InterruptedException for exception handling. Show a line of the code snippet with the thread instance t to make it awaken.
(5) (2%) Analyze the below code and tell what can be printed out on the console. If there is any error, please discuss why the below code does not work.
import javafx.beans.property.DoubleProperty; import javafx.beans.property.SimpleDoubleProperty; public class BindingDemo {
public static void main(String[] args) { DoubleProperty d1 = new SimpleDoubleProperty(1); DoubleProperty d2 = new SimpleDoubleProperty(2); d1.bind(d2);
d2.setValue(70.2);
d1.setValue(40);
System.out.println(“d1 is ” + d1.getValue() + ” and d2 is ” + d2.getValue()); }
}
11. (5%) Calculate the amount of time that elapses from when the source begins to send the first packet until the destination has received all ten packets where each packet consists of 7500 Kbits, the bandwidth is 10 Mbps, and 4 routers exist between the source and destination (assume zero propagation delay).
12. (6%) Suppose users share a 1 Mbps link. Also suppose that each user alternates between
periods of activity, when a user generates data at a constant rate of 200 kbps, and periods of
of the time. In this scenario, (1) (2%) calculate the maximum number of users, denoted as 𝑈 ,
inactivity, when a user generates no data. Suppose further that a user is active only 5 percent
that can be supported simultaneously by circuit switched link; (2) (2%) if there are 25 users, calculate the probability that there are more than 𝑈 users simultaneously active; and (3)
𝐶
(2%) say whether the probability of being more than 𝑈𝐶 users simultaneously active will
increase or decrease if there are 30 users.
13. (10%) Provide source code including .java and .class files for the following program named ‘MyTime.java’ in one zip file named ‘(Last_Name)_(Fist_Name)_Final.zip’. Please remove a line of package and test your program in the command line prompt. This program will be tested in the command line as your project is tested.
The above GUI program should show the current time, EST time, in the left textbox when the program is run. When each button is pressed, the resulting time in a specified time zone should be shown in the right text box. (Note: Please don’t forget to update the date as needed!)
𝐶