\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage{tcolorbox}
\usepackage{enumerate}
\usepackage{tikz}

\usepackage{algorithmic}

    \setlength{\headheight}{26pt}
    \pagestyle{fancy}
    \fancyhead[C]{\textbf{Basic Algorithms (Section 7)}\\Fall 2024}
    \fancyhead[R]{HW7 (Due 11/6 22:00)\\ Instructor: Jiaxin Guan}
    \fancyfoot[C]{}
    \fancyfoot[R]{\thepage}
    \renewcommand{\headrulewidth}{0.4pt}
    \renewcommand{\footrulewidth}{0.4pt}

\begin{document}


    %%%% EDIT THIS PART 
    %Put your name and Net ID here
    \fancyhead[L]{Name:  \\ Net ID: }
    %Write your collaborators' names here
    \fancyfoot[L]{Discussion Partners:}
    %%%%%

    %Problem 1
    \begin{tcolorbox}[title={Problem 1 (Alice's party, 30 pts)}] \setlength\parindent{1em}
    
    Alice organizes a party and is deciding which of her $n$ friends to invite. She wants to have that for each person at the party there are at least $5$ other people they know and at least $5$ other people they do not know. 
    
    Give a greedy strategy for finding the maximal number of friends she can invite (and a corresponding guest list), given a list of all pairs of people that know each other. Prove that your strategy finds the guest list of maximal size and analyze its runtime. For full credit, your algorithm should run in polynomial time.
    
    {\it Hint: In greedy examples we have seen so far, we greedily built up a solution from scratch. Here, you should instruct Alice to ``greedily'' cross people off her list.}
    \end{tcolorbox}
    %Write your solution here!

    \newpage

    %Problem 2
    \begin{tcolorbox}[title={Problem 2 (Making Change, 35 points)}] \setlength\parindent{1em}

    Given a set of coin denominations, consider the problem of making change for $n$ cents using the fewest
    number of coins. Assume that the set of coin denominations consists of only positive integers.

    \begin{enumerate}[(a)]
    \item (10 points) Describe a greedy algorithm to make change consisting of the following coin denominations:
    \begin{center}
        quarters (25 cents), dimes (10 cents), nickels (5 cents), pennies (1 cents)
    \end{center}
    For example, if you are told to give out 118 cents, you can use 4 quarters, 1 dime, 1 nickel, and 3
pennies. It is not possible to use less than 9 coins in total.
    \item (15 points) Prove that your algorithm always outputs an optimal solution for the set of coin denominations given in the previous part.
    \item (10 points) Now we will show that the greedy approach is not necessarily optimal if a different set of coin
    denominations is used. Give a set of coin denominations for which the greedy algorithm does not
    output an optimal solution. Your set should include a penny (1 cent) so that there is a solution for
    any value of $n \in\mathbb{N}$.
    \end{enumerate}
    \end{tcolorbox}
    %Write your solution here!
    
    \newpage

    %Problem 3
    \begin{tcolorbox}[title={Problem 3 (Huffman Encoding Practice, 15 points)}] \setlength\parindent{1em}
        Consider a file that uses the symbols $\{A,B,C,D,E,F,G\}$ with the corresponding frequencies:
        
        \begin{center}
            \begin{tabular}{c|c|c|c|c|c|c}
               $f_A$  & $f_B$ & $f_C$ & $f_D$ & $f_E$ & $f_F$ & $f_G$ \\
               \hline
                0.06 & 0.09 & 0.16 & 0.12 & 0.10 & 0.32 & 0.15 \\
            \end{tabular}
        \end{center}

        Find an optimal prefix code based on Huffman’s algorithm (using $0$ and $1$ only). You should give out the following (no justification needed):
        
        \begin{enumerate}[(a)]
        \item (5 points) The derived Huffman tree.
        \item (5 points) The mapping from symbols to bit strings. (You can fill in the chart below)
        \begin{center}
            \begin{tabular}{c|c}
               Symbol & Encoding \\ 
               & (e.g. 1101)\\ \hline
                A & \\ \hline
                B & \\ \hline
                C & \\ \hline
                D & \\ \hline
                E & \\ \hline
                F & \\ \hline
                G & \\            
            \end{tabular}
        \end{center}
        \item (5 points) $ABL$ (Average Bits per Letter) of your encoding.
        \end{enumerate}    
    \end{tcolorbox}
    %Write your solution here!
    
    \newpage

    % Problem 4
    \begin{tcolorbox}[title={Problem 4 (Huffman Encoding, Short Answers, 20 points)}] \setlength\parindent{1em}
        \begin{enumerate}[(a)]
        \item (10 points) In general, for a given set of letters and corresponding frequencies, is Huffman encoding always ``length-unique''? That is, for any letter, will the length of its encoding always be the same across all valid Huffman trees constructed from the frequencies? Note that different letters may have the same frequency in the general case. If yes, justify in a few sentences. Otherwise, provide a counterexample.
        \item (10 points) Is it possible that in an \emph{optimal} prefix code, a letter with a lower frequency has a shorter encoding than a
        letter with a higher frequency? If no, explain why not in a few sentences. Otherwise, provide an explicit example of the letter frequencies and the corresponding prefix code.
        \end{enumerate}    
    \end{tcolorbox}
    %Write your solution here!    
    
\end{document}