Introduction to Algorithms, 2020-1
Week 7: Exercises

1. Average Partition Size

Perform experiments to determine the average size of the smaller partition in each quicksort partition operation, as a fraction of the number of elements being partitioned.

2. Quicksort Efficiency

Perform experiments to compare the relative efficiency of merge sort and quicksort.

3. Adjacent Elements

We can use this class to represent a linked list node:

class Node:
  def __init__(self, val, next):
    self.val = val
    self.next = next

Write a function hasAdjacent(n) that takes a pointer to the first Node in a linked list and returns True if any two adjacent elements in the list have the same value, otherwise False.s

4. Prepend

You are given a class LinkedList with an attribute head that points to the head of a linked list of Node objects:

class LinkedList:
  def __init__(self, head):
    self.head = head

Write a method that prepends a value to a LinkedList.

5. Append

Write a method that appends a value to a LinkedList.

6. Efficient Append

Modify the LinkedList class so that the append() method runs efficiently (i.e. in O(1)).

7. Delete First

Write a method that deletes the first node (if any) in a LinkedList.

8. Delete Last

Write a method that deletes the last node (if any) in a LinkedList.

9. Split a List

Write a function split() that takes a pointer to the the first Node in a linked list and splits the list into two linked lists of roughly equal size. Return a pair containing these lists. The elements in the returned lists may appear in any order.

10. Merge Lists

Write a function merge() that takes pointer to the first Nodes of two sorted lists and combines them into a single sorted list.

11. Merge Sort

Write a function merge_sort() that performs a merge sort on a linked list, returning a pointer to a sorted list. Do not allocate any new list nodes while sorting.