Computer Science and Software Engineering

Written Questions

Question 1

Consider the algorithm DoSomething below:

Algorithm DoSomething (A, n)

Input: Array A of integer containing n elements

Output: Array S of integer containing n elements

1. for i=0 to n-1 do
2. Var[i]=0
3. end for
4. for i=0 to n-2 do
5. for j=i+1 to n-1 do
6. if A[i]A[j] then
7. Var[j]= Var[j]+1
8. else
9. Var[i]= Var[i]+1
10. end if
11. end for
12. end for
13. for i=0 to n-1 do
14. S[Var[i]]= A[i]
15. end for
16. Return S

1. What is the big-O (O(n)) and big-Omega ((n)) time complexity for algorithm DoSomething in terms of n? Show all necessary steps.
2. Trace (hand-run) DoSomething for an array A = (60,35,81,98,14,47). What is the resulting A?
3. What does DoSomething do? Explain that clearly and briefly given any arbitrary array A of n integers?
4. Can the runtime of DoSomething be improved easily? Explain how (i.e., re-write another solution(s) that does exactly what DoSomething is doing more efficiently)?
5. Can the space complexity of DoSomething be improved? Explain how?

Question 2

A company is involved in shipping large number of containers at a dock. Containers are classified into three categories:

Category 1: containers need to be accessed by their indices: lookup, set, add and remove from Category 1. Category 2: containers need to be added and removed before or after certain position including the first and last position of the Category 2.

Category 3: containers need to be added and removed in a sorted alphabetical order of their destination and any new added container need to follow that order of the Category 3.

From the three linear ADTs: List, Positional and Sequence covered in class. discuss which ADT to choose and its underlying implementation for the above containers categories.

Question 3

1. Draw a single binary tree that gave the following traversals:

Inorder: C O P Y R I G H T A B L E

Postorder: C P O R G I T H B A E L Y

1. Assume that the binary tree from the above- part (a)- is stored in an array-list as a complete binary tree as discussed in class. Specify the contents of such an array-list for this tree.

Question 4

1. Draw the min-heap that results from the bottom-up construction algorithm on the following list of values: 10,12,13,15,4,16,8,9,2,20,7,14,6,23,19

Starting from the bottom layer, use the values from left to right as specified above. Show immediate steps and the final tree representing the min-heap.

1. Perform the operation removeMin two times on the heap you created in part (a) and show the resulting min-heap after each step and the final tree representing the min-heap.

Question 5

1. Given a tree T, where n is the number of nodes of T.

Give an algorithm for computing the depths of all the nodes of a tree T. What is the complexity of your algorithm in terms of Big-O?

1. We say that a node in a binary search tree is full if it has both a left and a right child.

Write an algorithm called Count-Full-Nodes(t) that takes a binary search tree rooted at node t, and returns the number of full nodes in the tree. What is the complexity of your solution?

Programming Questions

In these programming questions you will evaluate two implementations of List interface in terms of their performance for different operations.

List^[1] interface is an ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

The List interface provides four methods for index access to list elements, two methods to search for a specific object, and two methods to efficiently insert and remove multiple elements at an arbitrary location in the list. Note that the speed of these operations may depend on the implementation (e.g., Array or LinkedList).

You are required to write two implementations of List interface, one that uses array, and one that uses doublylinked list. Then, you will have to test the performance of several operations when using your implementations.

Question 1:

Implement the following methods in the two implementations (called MyArrayList and MyLinkedList) of List interface:

Boolean add(E e) // Appends the specified element to the end of this list void add(int index,E element) // Inserts the specified element at the specified position in this list void _clear() // Removes all of the elements from this list

E remove(int index) // Removes the element at the specified position in this list

Boolean remove(Object o) // Removes the first occurrence of the specified element from this list

String toString() // Returns a string representation of this list int size() // Returns the number of elements in this list

Define your classes to be generics. The array implementation should have dynamic resizing (double the size when growing and halve the size when less than 25 % of the capacity is used); and the linked list implementation should use doubly linked list. Also, the behavior of these methods should be equivalent to that of Java Standard Librarys classes ArrayList or LinkedList. Please refer to the corresponding descriptions online^[2]/^[3].

For the rest of the methods of the List interface, you may just throw an exception:

public type someUnneededMethod() {

throw new UnsupportedOperationException();

}

Question 2:

Write your driver class ListTester. Use both of your list implementations and compare them to the

corresponding Java library implementations ( ArrayList and LinkedList) For numbers N = {10, 100, 1000, 10000, 100000, 1000000}

1. Starting with empty lists of Number-s; measure how long it takes to insert N integer numbers (int, or Integer) with random values ranging from 0 to 2N into the lists, when inserting them at the beginning, at the end, and into a random location of the list (use indices to indicate where to do the insertion (e.g., add (randomLocation, number)).

1. Starting with non-empty lists of N items (e.g., from part a), measure how long it takes to remove N numbers from the lists when removing them from the beginning, from the end, and from a random location of the list (use indices to indicate the location).
2. Starting with non-empty lists of N items (same as part b), measure how long it takes to remove N random numbers (with values between 0 and 2N) from the four lists (some values might not exist in the list!).

• Produce the following table (the timing values below are just an illustration and do not relate to any real measurements):

N = 10	[email protected]start(ms)	[email protected]end (ms)	[email protected]random (ms)
MyArrayList	18	110	310
ArrayList	18	110	310
MyLinkedList	18	110	310
LinkedList	18	110	310

N = 10	[email protected]start(ms)	[email protected]end(ms)	[email protected]random(ms)	Remove byvalue (ms)
MyArrayList	10	150	200	1234567
ArrayList	10	150	200	1234567
MyLinkedList	10	150	200	1234567
LinkedList	10	150	200	1234567

• Repeat for all values of N = 100; N = 1000; . etc.
• Save the result of your program execution in a file testrun.txt and submit it together with your other files.