Problem 1

Recall the Insertion Sort algorithm discussed in class, which produces an array whose elements are in increasing / non-decreasing order.

Suppose that we wish to run Insertion Sort on an array containing elements in generally increasing order, but with elements out of place relative to the original increasing order (where is a constant).

Select all of the options below that are true about the Insertion Sort's running time on this array:

• [x] (a)
• [x] (b)
• [ ] (c)
• [ ] (d)
• [x] (e)

Select all possible options that apply.

Problem 2

Select all the true statements from the list below. Each makes a statement on the pros and cons of lists vs. arrays.

• [x] (a) An array is better than a linked list because the th element of an array can be accessed in time compared to time for a linked list with only a head pointer.
• [x] (b) A sorted array is better than a sorted linked list because we can do binary search on a sorted array, in time.
• [ ] (c) Linked lists are better than arrays because it is asymptotically faster to reverse a linked list than to reverse an array.
• [x] (d) Linked lists are better than arrays, because insertion into the front of an array is often expensive.

Select all possible options that apply.

Problem 3

Consider a doubly linked list with a head pointer, a tail pointer, and nodes. From the list below, select the locations at which removing a node requires time, worst case.

• [x] (a) Given a valid pointer to the node after the one being removed.
• [x] (b) The end of the list.
• [x] (c) The front of the list.

Select all possible options that apply.

Problem 4

Consider a singly linked list with a head pointer, and nodes. From the list below, select the positions at which inserting a node requires time, worst case.

• [x] (a) Given a valid pointer to the node after the one being inserted.
• [ ] (b) The front of the list.
• [ ] (c) The 3rd position in the list.

Select all possible options that apply.

Problem 5

Consider a null-terminated, singly-linked list with head and tail pointers.

Suppose that every node, in addition to its next pointer, also maintains an additional pointer mid to the node which is halfway in between its own position in the list and the last node in the list.

The mid pointer of each node is subject to these further invariant properties:

• If the sub-list beginning with a node nd has even length (i.e. there are two "middle" nodes), then nd's mid pointer points to the node which is closer to the back of the list.
• If the sub-list consists of a single node (i.e. length is 1), the node's mid pointer refers to NULL.

Assuming that the length of the list is known () and is sufficiently large, what is the tightest upper bound on the best case running time of inserting a new item at the front of the list?

• [ ] (a)
• [ ] (b)
• [x] (c)
• [ ] (d)
• [ ] (e) None of the above

This best case running time occurs when the list's length before insertion is

• [x] (a) odd
• [ ] (b) either odd or even
• [ ] (c) None of the above

Problem 6

Choose the best asymptotic description for each of the following statements. Unless otherwise stated, assume we are referring to the worst-case behavior or structure, and that our algorithms (if any) are the best possible for the scenario.

1. A.
2. B.
3. C.
4. D.
5. E.
6. F.
7. G. Some other asymptotic expression!

Enter the letter corresponding to the appropriate asymptotic expression into the boxes. Choices may be used more than once, or not at all.

• C; Time to reverse a singly linked list of length . Assume you have a head pointer but no tail pointer.
• A Time to delete the first node of a doubly linked list of length . Assume you have a head pointer but no tail pointer.
• C Time to delete the last node of a doubly linked list of length . Assume you have a head pointer but no tail pointer.
• C Time to delete the last element in a singly linked list of length . Assume you have a head pointer but no tail pointer.

Problem 7

What is the running time of finding an element in a singly linked list of length ?

• [ ] (a)
• [ ] (b)
• [ ] (c)
• [x] (d)

Problem 8

Assume you have a doubly linked list with head and tail pointers, and no sentinels. Pat is trying to write the delete function for a linked list of unique (no duplicates) integers.

/*
@param head     - a pointer to the head of the linked list
@param toDelete - a pointer to the node to be deleted from the list
                  the node is guaranteed to be part of the list
                  this parameter will never be null or the head or tail                     of the linked list
*/
void deleteNode(ListNode *head, ListNode *toDelete) {
    ListNode *temp = head;
    while (temp != NULL) {
        if (temp == toDelete) {
            ListNode *prevNode = temp->prev;
            ListNode *nextNode = temp->next;
            nextNode->prev = prevNode;
            prevNode->next = nextNode;
            delete toDelete;
            toDelete = NULL;
            break; // this is a break statement! it exits the loop.
        }
        temp = temp->next;
    }
}

What is the problem with Pat’s code?

• [x] (a) The code correctly deletes the element, but it is inefficient.
• [ ] (b) The code will segfault.
• [ ] (c) There is a link missing from the linked list when it returns.
• [ ] (d) The code correctly and efficiently deletes the element