\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}
\title{CSE 101 Homework 4}
\date{Winter 2021}
\begin{document}
\maketitle
This homework is due on gradescope Friday February 19th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.
\begin{ques}[Dropping Lowest Grades, 35 points]
In a class Ronaldo had to complete $n$ assignments. On the $i^{th}$ assignment he scored $a_i$ points out of $b_i$ possible (with $b_i > 0$). At the end of the quarter his teacher told him that he could drop the scores on \emph{any} $k$ assignments that he liked. In particular, if he kept the grades on a set $S$ of $n-k$ assignments, his final grade would be $\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}$.
\begin{enumerate}[(a)]
\item Give an example where dropping the $k$ assignments in which $a_i$ is smallest does not give Ronaldo the best possible grade. [5 points]
\item Give an example where dropping the $k$ assignments in which $a_i/b_i$ is the smallest does not give Ronaldo the best possible grade. [5 points]
\item Show that there is a polynomial time algorithm that given a target grade $g$ determines whether or not there is a set of assignments that Ronaldo can drop in order to attain grade $g$ or better.\\
Hint: Ronaldo's grade is at least $g$ so long as $\sum_{i\in S} a_i-gb_i \geq 0$. [25 points]
\end{enumerate}
\end{ques}
\begin{ques}[Job Scheduling, 50 points]
Kiki works as a freelancer. At the start of each day, she is given a list of potential jobs to do for that day. Each job has a time at which it becomes available and an amount of time that it will take to accomplish. She can work on a job at any time after it becomes available and may even split up the time spent working on it (for example doing other jobs in between), however she will only be paid for the job if she completes it by the end of the day. As each job pays the same amount, Kiki's goal is to find a way to complete as many jobs as possible by the end of the day.
Our goal for this problem is to devise an algorithm that given a schedule of $n$ jobs, their start times and total work times and the time that the business day ends to come up with such an optimal schedule in time polynomial in $n$.
\begin{enumerate}[(a)]
\item Show that given a collection $C$ of jobs, that it is possible for Kiki to complete all of the jobs in $C$ if and only if she can do so by always working on the remaining job that was first made available (if there are any that are currently available). Hint: If this strategy doesn't work, show that there is a collection of jobs near the end of the day that there is not time to complete all of. [15 points]
\item Let job $J$ be the shortest job that is available far enough ahead of the end of the day that it is possible to complete on time. Show that there is a schedule that completes as many jobs as possible so that $J$ is one of the jobs completed. [20 points]
\item Provide a polynomial time algorithm for coming up with an optimal schedule for Kiki. [15 points]
\end{enumerate}
\end{ques}
\begin{ques}[Huffman Code Depths, 15 points]
Suppose that we build an optimal Huffman code for an alphabet with given letter frequencies using the algorithm discussed in class. Suppose that there is some letter $X$ which accounts for a $p$-fraction of the total letter occurrences. Show that the depth of $X$ in the resulting Huffman tree is at most $O(\log(1/p))$.
\end{ques}
\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}
\end{document}