Q1: You must choose a structure to store about 5000 data items. These items do have a specific sequence that you wish to store them in so must be sortable. You expect to have regular insertions and deletions of the data. You are not terribly concerned about storage space requirements - but you do expect that you will need a very high level of performance for search, insertion, and deletion. Please select a data structure type to store this data and defend your choice.

A1: Skip List (excellent performance on required items). Would accept other types  - just need to reference performance comparisons. B-Tree, Red-Black Tree, and AVL tree all also have same performance, but higher setup cost.

Q2: You must now implement a sort algorithm for the data structure that you implemented in question 1. Performance is extremely important in this situation. Please select a specific Sort algorithm to use and defend (with technical details) why this is the best selection.

A2: Without more details, you simply need a fast and stable algorithm – these are all good choices. Also one I had not considered was Radix – which would give similar or better performance than these common algorithms and is also Stable.

Q3: You have implemented an algorithm that solves a very complex problem for a client. The complexity of the algorithm is O(2^n) and you find for a typical scenario of n=5 the algorithm takes 2 seconds to complete. The client would now like to use it on larger sets - ranging from n = 10 to n = 100. How would you advise your client about the feasibility of using this algorithm in this situation. Give some sample numbers to make your point.

A3:

Simply compare based on performance criteria

Q4: What is the time complexity of the loop

for(i = 1; i < n; i *= 2)

A4: O(log n) – actually this is the definition of log.

 Q5: A Priority Queue is an abstract data type where each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. These can be used for automated phone answering systems along with other types of applications. What type of data structure would be most efficient for the implementation  of a priority queue and why? Be as specific as possible. (there are multiple good answers for this question - for full credit I am looking for the best).

A5: A heap or binary heap provides O(log n) for insertion and removal. Alternatively a binary tree does offer the same performance.

Q6: Explain how a hashing function provides extra security in user validation systems (specifically storage of user credentials) and still ensures proper user access.

A6: A hashed version of the password is stored in the database (not the original version), and authentication compares a hashed version of the user entered password against the hashed password in the database. The original password value is never stored in the system and thus is unavailable for anyone having or gaining access to the system.

Q7: What is the total number of undirected graphs you can make with 4 vertices?

A7: The formula for maximum number of edges is n_edges =  n(n-1)/2, however this is not the maximum number of Graphs you can make. With 4 vertices you can make the following Graph;  just starting from A; A, AB, AC, AD, ABC, ABD, ACD, ABCD, ABDC, ACBD, ACDB, ADBC, ADCB – and for each graph with 3 or more vertices, these can loop or dead end, so we are already at 23. The entire formula for this is at https://en.wikipedia.org/wiki/Graph_enumeration and the answer is 38. (I am giving half credit for 6 as this is the number of edges you can have). The equation for a directed graph is 2^n_edges – however a directed graph will have more as when you remove direction you will have duplicates in the undirected case.

Q8: Select and describe a practical application of tree structures. Give at least one useful and practical application where a tree structure could be used.

A8:  There are lots of these, just looking for one that is actually used. The most common and obvious one is the typical file system used in a File Allocation Table (FAT)

Q9: When does a BubbleSort have better performance than QuickSort and why?

A9: If the list is already sorted BubbleSort has a performance of O(n) – the best possible. It would only be used in situations where there is a high likelihood that the list is already sorted (which does happen).

Q10: Can you implement a Queue using a Stack? Can you do it with more than one Stack? If so how? Give an example of the steps for enqueuing and dequeing using a stack.

A10: You simply need 2 stacks. There is more than one way to do this, but here is a simple one;

enQueue(q, x)
 1) While stack1 is not empty, push everything from satck1 to stack2.
 2) Push x to stack1.
 3) Push everything back to stack1.

deQueue(q)
 1) If stack2 is empty, while stack1 is not empty, push everything from satck1 to stack2.
 2) Pop the element from stack2 and return it.