Exam II

Exam代写
Exam代写

Exam代写 When asked for time or space requirements, use Big-O notation, and use ‘n’ for the number of items in the collection or arrays.

   Name: ___________________

Comp 271: Data Structures, Fall 2017 Exam代写

21.4 points possible  (0.4 pts/ question unless noted)

10 pages, 1 hr  35 min time (~10 mins / page).   Please pace appropriately.

When asked for time or space requirements, use Big-O notation, and use ‘n’ for the number of items in the collection or array

IMPORTANT NOTE: for numbered problems, if you answer and receive no partial credit, you will be deducted up to an additional 0.4 pts.

In the Sorts homework we used ArrayList to perform array-like operations.  ArrayList uses methods to do the same things we did with indexed arrays.

Examples:
myArr[k] = myArr[k+1];
    myArr.set(k, myArr.get(k+1) );

int [] myArr = new int[50];
    ArrayList<Integer> myArr = new ArrayList<Integer>(50)


1. Translate the following line for when myArr is an ArrayList. Yes, it makes no sense.

myArr[temp] += myArr[myArr[k]];

2. In the list above, pick one of the Big-O functions above for the situations below: Exam代写

a) The time for the fastest sort for a shuffled, random array

b) The number of times you can subtract 100 from the number ‘n’ before it hits 0

d) The number of times you can multiply a number ‘n’ by 0.9 before it reaches 1

e) The speed of finding a value in an array, given the index

An important highlighted change is bolded and underlined in the code

public static int recFunc (int n, int count) {
  if (n > 1) {
    return (recFunc (n - 10, count + 1) );
  } else {
    return (count);
  }
}

1.  What value does recFunc(100,0) return, exactly. Exam代写

2. Approximately what mathematical function of ‘n’ does recFunc returns with large ‘n’ and ‘count’ at 0. (hint: use your answer to #1 to help think about it)

3.  How much time, in Big O notation, does recFunc take?

4.  For each recursive call, O(1) memory must be placed on the recursive function stack.  In Big-O notation, how much additional memory is necessary to compute the solution for a value ‘n’?

Provide the Big O time complexity for each function below of the following basic data structures

1. HashMap (the standard map/dictionary implementation)

a)_____ Find by key (assuming well implemented with minimal collisions)

b)_____ Find by value

c)_____ Insert (worst case, you have to resize the array used to implement it)

2. Linked list

a)_____ Find by index

b)_____ Find the first value in the list

c)_____ Insert given a random index

d)_____ Insert when given a pointer to the node location

3. Array (or ArrayList)

a)_____ Find by index

b)_____ Find by value (unsorted)

c)_____ Find by value (sorted, searching intelligently)

d)_____ Insert at a random index location

4. True / False: PriorityQueue implements a priority queue in the java collections framework using an AVL tree, which is one of the most common ways a priority queue is implemented.

1.  Fill the following table with the big-O time of each operation (2.0 pts, -0.4 per mistake, no added penalty) Exam代写

  Add(element) Remove(element) Contains(element)
LinkedList (doubly-linked)      
Heap (priority queue)    root only: ________   
Skip list (expected)       
TreeSet/TreeMap with an AVL tree (a balanced binary search tree)      
ArrayList (Unsorted array)    No empty spaces:  
Sorted array    No empty spaces:  
HashSet/HashMap   With resizing:  No resizing: By key: _______By value: ______

LinkedList Exam代写

The following questions involve a doubly-linked list.  For reference, the DoublyLinkedNode class used in the linked list implements the following functions:

public DoublyLinkedNode<E> previous();
public void setPrevious(DoublyLinkedNode<E>)
public DoublyLinkedNode<E> next();
public void setNext(DoublyLinkedNode<E>);
public E value();
public void setValue(E);

There are some mistakes in the code for the remove function for this doubly-linked list, which iterates through the list using ‘finger’ and removes the item with the same value as the passed object, returning the object removed. The mistakes are in bold and underlined below.  Replace the parts that are wrong with the correct code.

(6 fixes total – 0.4 pts each, no added penalty)

public E remove(E value)  {
// post: first element matching value is removed from list
DoublyLinkedNode<E> finger = null;
// iterate to the item to be removed
while (finger == null && !finger.value().equals(value)) {
     finger = finger.next();
}
if (finger != null) {
     // remove the node and return the element in it
     // fix the next pointer of the node to the left
     if (finger != null) {
         finger.previous().setNext(finger.next());
     } else {
         head = finger.next();
     }
// fix the previous pointer of the node to the right
     if (finger.previous() != null) {
         finger.next().setPrevious(finger.previous());
     } else {
         tail = finger;
     }
     count++;   // fewer elements
     return finger.value();
}
// if finger is null
return null;
}

Stacks & Queues Exam代写

1. Match the following implementations with the facts about them.  The matching should be one-to-one (one and only one for each) (1.2 pts, -0.4 pts/mistake)

The five queue implementations:

A) a singly-linked list with no tail pointer

B) a doubly-linked list

C) a circularly-linked list (tail node points to the head, and you maintain a tail pointer)

D) an array, adding and removing from the end only

E) an circular array – having the head move (not just at index 0) during add or removes from the head

Facts about those implementations: Exam代写

 ______ Great FIFO and LIFO, O(1), but you have to deal with capacity vs. size issues

 ______ Great FIFO and LIFO, O(1), no capacity issues and you can remove either from the head or tail.

 ______ O(1) for both add and remove as a FIFO and LIFO queue, but you can only remove from the head for that speed.

 ______ Great LIFO, terrible FIFO (that is, O(n)).  ArrayList essentially implements it for you (using add(E) and remove(myList.size()-1) )

 ______ Great LIFO, terrible FIFO (that is, O(n)) as normally implemented.  Elements are not in contiguous portions of memory.

2.  If we take a typical singly-linked list implementation and maintain a pointer to the tail, which of the following are O(1) operations.  

Circle all the apply. (0.6 pts, -0.2 per mistake)

a) Removing the tail element Exam代写

b)  Removing the second element (the one the head points to)

c)  Adding an element at the head

d) Adding an element to the tail

e)  Removing the head element

f)   Removing the second to last element (the one that points to the tail element)

Start fresh with the following heap for the next two problems. Note, no partial credit will be given for incorrect answers, but there will also be no added penalty.

Exam代写
Exam代写

1. Write the resulting heap in tree form upon removing the TWO highest priority/lowest value elements.  (Hint: replace the root with the last value in the heap, and percolate that value down to satisfy the heap property – no need to show work). (0.6 pts)

2. Starting with the original heap again (before doing the problem before), write the resulting heap if you add the values 0 and 1 to it (hint: add at the end and percolate up – no need to show work) (0.6 pts)

4  Oh, no! someone forgot which index equations match which relationships.  Match them.  Write parent, left child, and right child next to the appropriate equation.  Hint: use the example above to check them.

a) 2*index + 1

b) 2 * (index + 1)

c) (index-1) / 2  

Hash Tables

Suppose you have a class called ‘Student’ which holds student information and uses the student’s ID as the key.

Here is the hashCode method for this class – NOTE THE VALUE ‘7’:

public int hashCode(){
return (7 * this.ID);
}

1. Hash the following student ID/names pairs into the following hash table, which uses LINEAR PROBING to deal with collisions.  Use the remainder of the hashCode divided by 5 to determine the index. (1.6 pts, -0.4 per mistake, no added penalty)

ID   NAME

1   Mary

11   Sarah

3 Kat

6 Matt

Index         <key, name>

0  
1  
2  
3  
4  

2.  For a singly-linked list with a tail pointer…

a) which end(s) can you add to if you will use it as a FIFO queue?

b) which end(s) can you add to if you will use it as a LIFO queue?

1.  Write the letter for the following data structures next to the description.  Note, the matching is one-to-one so if one appears suitable to multiple descriptions it may have to change so the others match.  

(2.0 pts total, -0.3 for each wrong, no additional penalty)

___  If there are O(n log n) evenly distributed edges, search for an edge is O(log n)

___  The fastest, best implementation to represent a dense graph

___  This type of graph is useful for showing dependencies between methods

___  Use this to represent relationships with different strengths between items

a) weighted   b) directed c) adjacency matrix graph   d) linked-list graph

___  Primitives

___  Wrapper object classes

e) Integer, Double              f) int, double

___  O(1) search with index, O(log n) fastest search for a value, does not resize easily

___  O(1) search with index, O(n) fastest search for a value, does not resize

___  O(1) search with index, O(n) fastest search for value, dynamically resizes

___  Great LIFO, bad FIFO queue unless you add a tail pointer and add at the tail

___  A Deque – great LIFO and FIFO behavior since the head and tail are symmetric

g) ArrayList h) singly-linked list Exam代写

j) LinkedList   k) sorted array       l) unsorted array

___  No extra methods in this, only a promise that duplicates are not allowed

___  You can only access elements on the top or bottom of this interface

___  This isn’t a sub-interface of java.util.Collection since it only stores associations

___  The super-interface for most interfaces in the Java collections framework

___  A group of static methods that work on collections (e.g. shuffle, sort, …)

___  You can access elements by an index, but speeds can range from O(1) to O(n)

m) Map       n) Queue     o) List          p) Set  q) Collection  r) Collections

___  this tree is self-balancing for fast, efficient behavior

___  an in-order traversal of this tree gives the elements in sorted order

___  this has no particular ordering. e.g. heaps are abstractly represented as these.

s) binary tree         t) binary search tree         u) AVL tree

___  an alternative to hash tables that maintains items in sorted order

___  a map implementation which is O(1) and fastest for very small load factors

___  a map which can hold more items than its underlying array

___  useful when all you need to do is choose the highest/lowest value each time

___  same expected times as a AVL tree for add/search/remove operations

v) treemap w) hash table, chaining  x) hash table, linear probing

y) skip list   z) heap/priority queue

Assuming all the functions in our SkipList were implemented with reasonable efficiency. What is the Big O for each of the following functions. Assume our skiplist has ‘n’ elements, and any passed collection also has ‘n’ elements. Note, the questions below are numbered so being wrong incurs an added penalty. You will not receive less than a 0 for this page. (0.4 pts / question, 5.6 pts total, note the penalty applies here to each questions separately).

Exam代写
Exam代写

更多其他:prensentation代写 Case study代写  心理学论文代写 哲学论文代写 计算机论文代写 毕业论文代写 论文代写

合作平台:天才代写 幽灵代写  写手招聘