Implementing the Stable Matching Algorithm Using Lists and Arrays

In this section of chapter two, we explore the tradeoffs between lists arrays and lists to determine which data is appropriate for the algorithm. Some of the tradeoffs we read about are finding an element in the array or list with given index i, seeing if a given element is an array or list and if the array is sorted or not. An important concept to take away from this section is that preprocessing allows us to convert between the array and list representations in O(n) time, so we are not limited in which data structure we choose and we can freely jump between which one fits the algorithm best!

Our goal is to complete all four steps of the algorithm in constant time to achieve an efficient run time of O(n²). The data structure we chose to represent the free men is a linked list. We used two arrays (arrays of arrays) that will use O(n²) space to represent the women's preference lists and the men's preference lists. The data structures allow each step of the algorithm to take place in constant time (O(1)). After this section was presented in class it was more clear the tradeoffs between lists and arrays and why we chose certain data structures to represent key elements of the algorithm.

This section did a lot of comparing and contrasting that we went over in detail in class. It was very clear but a lot less interesting because it seemed so repetitive. Readability: 8

A Survey of Common Running Times

In this section we analyze common running times: O(n), O(n log n), O(n²).

• Linear Time- O(n) (p.48-50)
  • the run time is at most the size of the input times some constant factor
  • example algorithms that are linear time:
    • computing the maximum
    • merging two sorted lists
• O(n log n) Time (p. 50-51)
  • “the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time”
  • sorting is the best example of n log n time, specifically merge sort
  • n log n frequently is the run time of algorithms because many algorithms require sorting the input
• Quadratic Time (p. 51)
  • common running time is performing a search over all pairs of input items and spending constant time per pair
    • example: find a pair of points in form (x,y) in a given plane that are closest together
  • nested loops
• Cubic Time (p. 52)
  • more elaborate nested loops
  • example: finding the subset of given sets that is disjoint (has no elements in common)
• O(n^k) Time (p. 53)
  • obtain a running time of O(n^k)for any constant k when we search over all subsets of size k
  • example: finding independent sets in a graph
• Beyond Polynomial Time (p. 54)
  • O(2ⁿ)
    • like the brute-force algorithm for k-node independent sets but now iterating over ALL subsets of the graph
    • total number of subsets is 2ⁿ
    • example: given a graph and want to find an independent set of maximum size
  • O(n!)
    • grows even more rapidly!
    • number of ways to match up n items with n other items
    • example: Stable Matching Problem- matching n women with n men
    • when the search space consists of all ways to arrange n items in order.
    • example: Traveling Salesman Problem: finding distances between pairs of n cities, what is the shortest way to visit all of the cities?
• Sublinear Time
  • some encounters that are even asymptotically smaller than linear!
  • happens in a model of computation where input can be “queried” indirectly vs read completely and the goal is to minimize the amount of querying that must be done
  • example: binary search algorithm
    • given a sorted array of n numbers, determine whether a given number p belongs in the array

This section was a really large chunk of information and took a few times to read to understand. The most confusing part was the sub linear time. Even though I don't have any specific questions, just the general topic confused me. I thought this chapter was pretty interesting although not very easy to read. It was a very good review and important to cover moving on into the next sections. I would rate readability an 8/10.

A More Complex Data Structure: Priority Queues

In this section we discuss a very broadly used data structure to help us achieve our goal of improving run time. We discover the different processes a PQ can perform that a list or array can't.

The Problem: For the Stable Matching algorithm we need to maintain a dynamically changing set of free men so we can add and delete elements from the set in linear time. We use the priority queue because elements have a priority value or key so when we want to select an element from the set of free men we take the one with the highest priority.

The Motivation: One motivation for applying PQ's is the problem of managing real-time events (ex: scheduling processes on a computer). We want to implement a priority queue that supports a O(n log n) time per operation such as adding and deleting elements and selecting the element with the minimum key. We will use the priority queue to sort a set of n numbers!

The Data Structure: Heap A heap is a balanced binary tree (or can be represented as an array too) and is the most efficient way to implement a priority queue. The tree has a root and each node can have up to two children (L and R). The keys in the tree are in heap order where every element v, at node i, the element w at i's parent satisfies key(w)< or = key(v)

Heap Operations

• to identify the minimum element is constant time (O(1)) because it is the root node.
• to add or delete elements we have to maintain the balance and order of the tree so we have two processes to maintain
• Heapify-Up
  • swap the positions if the child is smaller than the parent
• Heapify-Down
  • swap the positions if the replacement node is too large for its position
• With heapify-up/down we can add and delete elements in O(log n) time

This section was very straight-forward after the class lecture on heaps. It was a lot less interesting to read the chapter than be presented the information in class but overall the text clearly outlined and identified the main points we need to remember about priority queues and heaps and why this data structure helps us achieve a better run-time. I would rate the readability a 8/10.