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

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.