CSci 2101 Data Structures: Takehome exam I.
Due Wednesday, March 2, at 8pm. 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. If you have
questions, please come to see me or send me an e-mail. You may not get
any help on the assignment from anyone 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, and the Node and
LinkedList. Copy/paste the code for Node and LinkedLists into files
Nodes.java and LinkedList.java.
You need to write a program to do the following:
Test your program carefully, submit all test cases.
Problem 3 (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 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 node comparisons
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 and record all your test cases and the results.
- Find 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 getNext() 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.