CMSC 27200 — Problem Set 1

Instructions

This problem set is due on Wednesday April 15, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

  1. Let $f,g$ be functions with $f(n) = O(g(n)$. Determine and prove the following.
    1. Is $f(n)^2$ always $O(g(n)^2)$?
    2. Is $\log f(n)$ always $O(\log g(n))$?
  2. The sorting problem is: Given an array $A$ of $n$ integers $a_1, \dots, a_n$, return an array $A'$ containing $a_1, \dots, a_n$ such that $A'[0] \lt A'[1] \lt \cdots \lt A'[n-1]$.
    1. Give an algorithm, in pseudocode, that when given an array, determines whether it is sorted or not. Do a brief analysis to determine the worst-case time complexity.
    2. A very important result about sorting is that sorting can be done in $O(n \log n)$ time. We will not be showing this. In Lecture 2, when discussing notions of efficiency, the idea of "obvious" or brute-force algorithms is briefly mentioned. Describe the simplest brute-force algorithm for sorting, and give the best-case and worst-case running times for this algorithm. Take care not to prematurely optimize!
  3. Two teams $\mathcal S$ and $\mathcal T$ are competing in a tournament where they must present a lineup to compete in $n$ matches. Each member $s_i \in \mathcal S$ and $t_i \in \mathcal T$ have a particular skill rating, so it is in each team's best interest to try to match high skilled players against the other team's lower skilled players. We say that a pair of lineups $(S,T)$ is stable if neither $\mathcal S$ nor $\mathcal T$ can change their lineup on their own to get more advantageous matchups. That is, there is no lineup $S'$ such that $(S',T)$ that does better than $(S,T)$ for $\mathcal S$ and there is no lineup $T'$ such that $(S,T')$ does better than $(S,T)$ for $\mathcal T$.
    For every set of players $\{s_1, \dots, s_n, t_1, \dots, t_n\}$ with skill ratings, is there always a pair of stable lineups $(S,T)$? Either prove that there is by constructing an algorithm to find such a pair or show that there isn't by giving a counterexample (i.e. a set of players and ratings for which there is no pair of stable lineups).