## CSci 2101 Data Structures: Takehome exam I.

Due Wednesday, October 13th, at 8pm. Please submit the paper-and-pencil part to Elena's office (slide it under the door if the door is closed). The program part is to be submitted by e-mail to Elena. Absolutely no late submissions are accepted, the deadline is firm. Don't try to submit at the last minute, allow extra time for bounced e-mail and similar things. Double-check to make sure that you are submitting the right files (only .java files need to be submitted).

You may use any printed and online materials and your own problem sets. You are allowed to talk to each other about general approaches to the problems. You may also discuss particular compilation issues, but you may not reproduce any part of another person's code or a solution of a paper-and-pencil problem. You may get help from me or from Andy Korth. You may not get any help on the assignment from anyone else outside of the class.

### Problem 1 (7 points)

Write a program to do the following:
• Create an array of integers.
• Write a loop (a while loop or a for loop) to check if the array is symmetric. An array is symmetric if the first element is the same as the last one, the second element is the same as the second-to-last, and so on. For instance, arrays {5, 2, 3, 4, 3, 2, 5} and {7, 7} are symmetric, but {1, 2, 1, 2} is not.
• Your program should print "Symmetric" for a symmetric array and "Not symmetric" for a non-symmetric one.
Make sure to test your program well and submit all the test cases. The program must work for any array with at least one element.

### Problem 2 (8 points)

For this program you will need the class files IntQueue.class, QueueException.class and the Node and LinkedList. Copy/paste the code for Node and LinkedLists into files Nodes.java and LinkedList.java. You don't need to copy the code for the Packages class.

You need to write a program to do the following:

• Create a queue of integers and a linked list. Insert some integers into the queue and add some nodes to the list. Do not change the nodes after you have added them to the list.
• Write a loop that compares whether the queue and the linked list have exactly the same elements in the same order (the data of the nodes is compared to the integers on the queue). The program should print "The same" if the queue and the linked list have the same elements and "Not the same" otherwise. Note that the queue and the linked list may have a different number of elements.
Test your program carefully, submit all test cases.

### Problem 3, paper-and-pencil (5 points)

In a heap representation of a priority queue does the order of elements in the array depend on the order in which the elements were inserted into the queue? In other words, is it possible to insert the same group of elements on the queue, but to get two different orderings of elements in the array if the order of elements in the two groups was different?

### Problem 4 (20 points)

Your boss wants you to implement a priority queue to store integers between 1 and 10 as a linked list. He says that since the range of the elements is known, it would be more efficient to implement the queue as a doubly linked list and insert the elements which are greater than 5 from the front of the list, and those smaller or equal to 5 from the back of list. This will cut down on the number of nodes accessed when an element is inserted. Your task is:
• To implement the priority queue using this Doubly linked lists implementation. In your priority queue implementation write private methods `insertFromFront(int d)` and ```insertFromEnd(int d)``` to insert the elements in the right place in the doubly linked list. Your enqueue method should call one of these methods depending on whether the element is greater than 5.
• Test it to and record all your test cases.
• Find out the big-Oh efficiency of the enqueue and dequeue operations of the new queue, explain your reasoning. You need to consider the worst case only, not the average case.
• What the efficiency of the algorithm in practice? Compare the new priority queue to the other linked list implementation of the priority queue. More specifically:
• Add static counters to all methods of the class Node and DoubleNode.
• Run a testing program that inserts a 100 of the same random integers between 1 and 10 into both queues. Print out the values of the counters.
• Compare the results. Add the values for setNext() and setPrev() of the DoubleNode together and compare the sum to counter of the setNext() of the Node in the linked list implementation. Similarly compare the total number of calls to getNext() and getPrev() of DoubleNode to setNext() of the Node. Compare the values of getData() for the two kinds of nodes.
• Compare the memory use. Consider the DoubleNode to take 1.5 amount of space of a Node: object references are 4 bytes, int is 4 bytes, Node has one object reference and one int, and DoubleNode has 2 references and one int. Note: this may be not true in reality because of machine-specific alignment and other factors.
Was your boss right? I.e. is the doubly linked list more efficient for this problem despite the overhead of the 'prev' references in the doubly linked list?

Extra credit (up to 3 points) Analyze this testing strategy. Can you see any flaws in it? Can you suggest better tests? You don't need to implement them, just describe them in detail.

This is a takehome exam from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.