CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Winter, 2020 (Dillencourt)

• The text book up through the end of Section 4.2.
• The class uptes up through and including slide 4-15.

• Stable matching:
  • Problem formulation. Definitions: matching, perfect matching, instability, stable matching
  • Gale-Shapley algorithm: Mechanics of the algorithm, analysis. Implementation details necessary to achieve quadratic running time. Characterization of the stable matching produced; definitions of valid partner, best valid partner, worst valid partner.
• Problem reduction
• Asymptotic notation: definitions and basic properties of Big O, Big Omega, Theta, little O.
• Priority queues. Binary heaps. Mechanics and analysis of operations on binary heaps: insertion, deletion, makeHeap.
• Introduction to graphs
  • Basic definitions: directed vs. undirected. Path, simple path, cycle. Connected (undirected) graph, strongly connected (directed) graph. Link distance. Trees (free,rooted).
  • Graph traversal: BFS, DFS
  • Graph representation: Adjacency list, adjacency matrix.
  • Basic graph algorithms: connected-component labeling, testing for bipartiteness, strong-connectivity testing, topological sorting, strong-component labeling. (Mechanics and analysis of each of these algorithms.)
• Greedy Algorithms
  • Scheduling Problems: Scheduling a maximum number of intervals on a single processor, scheduling all intervals using a minimum number of processor, scheduling jobs to minimize the maximum lateness.

• Define [any term for which you are expected to know the definition, see the preceding list of topics].
• Given a collection of preferences and a matching M, is M stable?
• Given a collection of preferences and given which set of entitities does the proposing, what matching would be produced by the Gale-Shapley algorithm?
• Given a collection of preferences what is the best/worst valid partner of entity x?
• Given two functions f and g, which of the following statement(s) is/are true: f is O(g). f is Omega(g). f is Theta(g). f is o(g).
• Given a list of functions, order them so that each function is big oh of the next function. If there are ties (i.e., two functions that are both big oh of each other), indicate this.
• Give the asymptotic running time of [a given chunk of pseudocode]
• Show the result of applying a specified operation to a given binary heap
• For a given graph G, a given algorithm from the list above, and possibly additional relevant information (e.g., the order in which vertices are visited, the order in which the neighbor of each vertex are visited): show the result of applying a particular algorithm to the graph.
• For one of the greedy scheduling algorithms listed above, given an appropriate input, show the output and possibly answer additional questions testing your understanding of the mechanics of the algorithm.