\documentclass[12pt]{article}
\usepackage{geometry}
\usepackage{latexsym}


\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}

\begin{document}

\title{CS 141: Advanced Topics in Algorithms \\ Spring 2006 \\ Assignment 8b}
\author{Assignment Jon and Garret}
\date{Due:  Tuesday, April 4}
\maketitle

\begin{enumerate}

  \item \Points{10} \Name{Offline Scheduling}
  
    Remember the problem given in class: Given finite jobs $J_1\ldots
    J_k$, where job $J_i=(r_i,d_i,w_i)$, with $r_i$ being defined as
    the release time of $J_i$, $d_i$ the deadline, and $w_i$ the
    weight of the job.
 
    Each job takes a unit time to complete, and we can only begin a
    job once it has been released and before the deadline, and the
    release times and deadlines are given as non-negative integers.
    
    We can only work on one job at a time, so the goal of this problem
    is to maximize the total weight $w_i$ of all of the jobs
    completed.

  \begin{enumerate}
  \item Devise an offline polynomial-time algorithm that solves this
    scheduling problem.
    
  \item Briefly, prove the correctness of your algorithm.
        
  \item Analyze the runtime of your algorithm and show that it is
    indeed polynomial in the size of the problem instance.
  \end{enumerate}
\end{enumerate}
 
\end{document}