


\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}
\usepackage{multicol}
\usepackage{soul}
\usepackage{xcolor}
\usepackage{graphicx}                                          
\usepackage{float}                                                

\vfuzz2pt 
\hfuzz2pt 

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{fact*}{Fact}
\numberwithin{equation}{section}

\newtheoremstyle{probstyle}  
{3ex}                        
{0pt}                        
{\normalfont}                
{-3ex}                       
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{probstyle}
\newtheorem{problem}{Problem}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\setlength\parindent{0pt}
\setul{.25ex}{}

\begin{document}
	\title{Math 154 Homework \#6\vspace{-3ex}}
	\date{Spring 2023}
	\maketitle
	\begin{center}
		Due date: \textbf{11:59pm} Pacific Time on \textbf{Wed, May 24} (via \href{https://www.gradescope.com/}{Gradescope})
	\end{center} 
	\vskip 3ex
	\thispagestyle{empty}
	\vspace{-2ex}
	\noindent\emph{On the first page of your work, please write a list of everyone with whom you collaborated on this assignment, as well as any outside sources you consulted, apart from the textbook, your notes, and the course staff. If you did not collaborate with anyone, please explicitly write, “No collaborators.”}
	
	\begin{problem} 
		Use the greedy algorithm with vertex ordering \textsf{A, B, C, D, E, F} to color the graph below. 		Does a coloring with fewer colors exist? Why or why not?\\
		
		\textit{Note: you can just ``color" with numbers 1,2,3, etc. But if you want to use real colors, it will make it faster for us to grade if you use 1 = red, 2 = yellow, 3 = green, 4 = blue}.\\
		
		\begin{figure}[H]
			\centering
			\begin{minipage}{.26\textwidth}
				\includegraphics[width=1\linewidth]{./hw6_graph_new}\\
				
			\end{minipage}
		\end{figure}
	\end{problem}
	
	\begin{problem}
		Answer parts (a) and (b) of \textbf{Question 6.6} at the end of Chapter 6 of the textbook.\\
	\end{problem}
	
	\begin{problem}\label{prob:registers}   \textit{\textbf{Background:}} In this problem, we'll explore an application of graph theory to computer science.\footnote{It’s okay if you don’t know any programming, or if this material is new to you -- all the background you need is in the problem statement, and if you’re confused about anything, just ask! Also, there are complexities I'm sweeping under the rug -- if you’re curious, you can learn more about register allocation in a computer architecture or compiler design course.} Computers have special memory locations called registers that are very fast to access, but are expensive and limited in quantity. Ideally, when we run a computer program, the value of each variable is stored in a register for fast access, but each register can only hold one variable at a time -- a register is like a little box or whiteboard only big enough for one number. However, we can re-use a register for multiple variables if they don’t need to be stored at the same time.  To illustrate, here is pseudocode for a simple program to compute the 4th power of a number \texttt{a}.\\
		
		
		\ul{Program to compute \texttt{a}$^4$:}\\
		\texttt{1. get a} \textit{(e.g, from user input)}\\
		\texttt{2. b = a*a}\\
		\texttt{3. c = b*b}\\
		\texttt{4. return c}\\
		
		This program has 3 variables (\texttt{a},\texttt{b}, and \texttt{c}), but it can run with just 2 registers: after Step 2, variable \texttt{a} is not needed, and variable \texttt{c} is only used starting in Step 3. So we can store \texttt{a} and \texttt{c} in the same register at different times:\\
		
		
		\begin{minipage}{4cm}
			\hspace{1.5cm}\ul{Step 1}
			\begin{align*}
				\text{\textit{Register 1}} & \text{\ \ \fbox{\texttt{a}}}\\
				\text{\textit{Register 2}} & \text{\ \ \framebox(11.5,12){}}\\
			\end{align*}	
		\end{minipage}\hspace{1cm}
		\begin{minipage}{4cm}
			\hspace{.7cm}\ul{Step 2}
			\begin{align*}
				\text{\textit{Register 1}} & \text{\ \ \fbox{\texttt{a}}}\\
				\text{\textit{Register 2}} & \text{\ \ \fbox{\texttt{b}} \textcolor{lightgray}{\texttt{(=a*a)}}}\\
			\end{align*}	
		\end{minipage}\hspace{1cm}
		\begin{minipage}{4cm}
			\hspace{.7cm}\ul{Step 3}
			\begin{align*}
				\text{\textit{Register 1}} & \text{\ \ \fbox{\texttt{c}} \textcolor{lightgray}{\texttt{(=b*b)}}}\\
				\text{\textit{Register 2}} & \text{\ \ \fbox{\texttt{b}}}\\
			\end{align*}	
		\end{minipage}\mbox{}\\~\\
		
		
		
		
		
		
		
		\textit{\textbf{Problem:}} Suppose we have a computer program with 6 variables, as summarized in this table. \textit{(Here, \texttt{a} and \texttt{b} can't be stored in the same register, because both are used in Steps 1-2, but for example, \texttt{a} and \texttt{c} could be, since they're not used simultaneously.)}\\
		
		\begin{tabular}{ |c|c| } 
			\hline
			Variable & Steps used  \\ 
			\hline
			\texttt{a} & 1-2\\ 
			\texttt{b} & 1-5\\
			\texttt{c} & 6-8\\ 
			\texttt{d} & 3-10\\ 
			\texttt{e} & 4-7\\ 
			\texttt{f} & 9-10\\ 			 
			\hline
		\end{tabular}\mbox{}\\\\
		
		If we want to store each variable in a register, what is the minimum number of registers needed to run this program? \textit{(Note: you should convert this into a graph theory problem before solving it!)}\\\vspace{-1ex}
		
	\end{problem}\mbox{}\\
	
	
	
	
	\begin{problem}
		If $m$ is the length of the longest path in a graph $G$, prove that $\chi(G)\leq m+1$.
	\end{problem}
	
\end{document} 
