CS Problem Set

\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{listings}
\usepackage{xcolor}
\usepackage[hidelinks]{hyperref}

\definecolor{codebg}{HTML}{F7F7F7}
\lstset{basicstyle=\ttfamily\footnotesize,backgroundcolor=\color{codebg},frame=single,breaklines=true}

\newtheorem*{problem}{Problem}

\begin{document}

\begin{center}
{\LARGE\bfseries CS 170 -- Algorithms -- Problem Set 3}\\[0.3em]
{\large First Last \;•\; \today}
\end{center}

\begin{problem}[1: Asymptotic Analysis]
Rank the following by order of growth:
$n^2$, $n \log n$, $2^n$, $n!$, $\log n$, $n$, $n^{1.5}$, $\log(n!)$.
\end{problem}
\textbf{Answer.}
\[ \log n \;<\; \log(n!) \;<\; n \;<\; n\log n \;<\; n^{1.5} \;<\; n^2 \;<\; 2^n \;<\; n! \]
Note $\log(n!) = \Theta(n\log n)$ by Stirling, but strictly below $n\log n$ in leading constant.

\begin{problem}[2: Recurrences]
Solve $T(n) = 2T(n/2) + n \log n$ using the Master Theorem.
\end{problem}
\textbf{Answer.} $T(n) = \Theta(n \log^2 n)$ (Case 2 of the Master Theorem extended).

\begin{problem}[3: Dynamic Programming]
Give an algorithm for the longest increasing subsequence in $O(n \log n)$.
\end{problem}

\begin{algorithm}[H]
\caption{Longest Increasing Subsequence}
\begin{algorithmic}[1]
\Function{LIS}{$A[1..n]$}
  \State $\textit{tails} \gets$ empty array
  \For{$i = 1$ to $n$}
    \State $j \gets$ first index where $\textit{tails}[j] \ge A[i]$ (binary search)
    \If{no such $j$} \State append $A[i]$ to $\textit{tails}$
    \Else \State $\textit{tails}[j] \gets A[i]$
    \EndIf
  \EndFor
  \State \Return $|\textit{tails}|$
\EndFunction
\end{algorithmic}
\end{algorithm}

\textbf{Complexity.} Each iteration does $O(\log n)$ work for the binary search;
total $O(n \log n)$.

\begin{problem}[4: Implementation]
Implement Dijkstra's algorithm using a priority queue.
\end{problem}

\begin{lstlisting}[language=Python]
import heapq

def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist
\end{lstlisting}

\textbf{Complexity.} $O((V+E)\log V)$ with a binary heap.

\end{document}