% --------------------------------------------------------------
% This is all preamble stuff that you don't have to worry about.
% Head down to where it says "Start here"
% --------------------------------------------------------------

\documentclass[12pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{courier}
\usepackage{listings}
\usepackage[colorlinks,linkcolor=blue]{hyperref}
\usepackage[noabbrev]{cleveref}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}

\newenvironment{theorem}[2][Theorem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{lemma}[2][Lemma]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{exercise}[2][Exercise]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{reflection}[2][Reflection]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{proposition}[2][Proposition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{corollary}[2][Corollary]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}

\oddsidemargin 0in
\evensidemargin 0in
\textwidth 6.5in
\topmargin -0.5in
\textheight 9.0in

\newcommand{\ignore}[1]{}
\def\pp{\par\noindent}

\newcommand{\assignment}[4]{
\thispagestyle{plain}
\newpage
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{ \vbox{ \hbox to 6.28in
{\bf CIS 419/519: Applied Machine Learning \hfill #1}
\vspace{4mm}
\hbox to 6.28in
{\hspace{2.5in}\large\mbox{Homework #2}}
\vspace{4mm}
\hbox to 6.28in
{{\it Handed Out: #3 \hfill Due: #4}}
}}
\end{center}
}

\makeatletter
\renewcommand{\fnum@algorithm}{\fname@algorithm}
\makeatother

\lstset{basicstyle=\footnotesize\ttfamily,breaklines=true}
\lstset{framextopmargin=50pt,frame=bottomline}


\begin{document}
%\assignment{Spring 2018}{2}{February ${14}^{th}$, $2018$}{February ${26}^{th}$, $2018$, 11:59 PM}
\assignment{Fall 2019}{0}{August 26}{September 6}

% --------------------------------------------------------------
%                         Start here
% --------------------------------------------------------------

%\renewcommand{\qedsymbol}{\filledbox}

\begin{footnotesize}
\begin{itemize}


\item The goal of HW0 is to give you an idea of the level of mathematical knowledge and maturity expected in this class. You should have seen all the material used here; the goal of this homework is to encourage you to go back to some of the material and refresh your memory. 

\item Most of these problems require you to be familiar with the notation and the definitions of the concepts. Beyond that, you should be able to reason from the definitions and do some algebraic manipulation. None of these problems require deep understanding of the material.
    
\item Feel free to go back to some of your text books and the web when solving it. 
%
%\item Also, feel free to talk to other members of the class in doing the homework.  I am more concerned that you learn how to solve the problem than that you demonstrate that     you solved it entirely on your own.  
%
You should, however, be able to write down your own solution to these problems. 

\item {\bf If you are not familiar with more than 30\% of the material in this problem set, or find it difficult to solve at least $2/3$ of it in a few hours, you are missing the prerequisites, and you will find the class too difficult. In this case, I recommend that you drop the class, take the required classes first, and then come back to take this class.}
    
\item While we encourage discussion within and outside the class, in the specific case of HW0, you are on your own. It's a test of your level of readiness to the clas, so please work on it independently. 

\item Please use Piazza if you have questions about the homework. In general, we encourage you to come to the Professor and the TAs office ours and recitations, although for this specific assignment you are on your own. 
    
\item Please try to keep the solution brief and clear.

\item Please, no handwritten solutions. Consult the class’ website if you need guidance on using Latex. You will submit your solution manuscript as a single pdf file. 

\item The homework is due at 11:59 PM on the due date. We will be using Canvas for collecting the homework assignments. Please submit your solution manuscript as a pdf file via Canvas. Please do NOT hand in a hard copy of your write-up.  Post on Piazza and Contact the TAs if you are having technical difficulties in submitting the assignment.

\item {\bf If you are on the waiting list}, we recommend that you still work on the assignment so that you can determine
if you want to stay on the waiting list. If you cannot register for the class by the time the assignment is due, please
email your solutions to Hangfeng He (\texttt{hangfeng@seas.upenn.edu}) with ``CIS 419/519 Homework 0'' in the subject.

    
%\item 
%Consequently, you do not need to turn in this homework; we do hope that you do it, write it down (only then you will make sure you   understand) and compare your solutions to the solutions   we will supply next week.

\ignore{
\item
The homework is due at 11:59 pm on the due date.  Please email an electronic
copy of your write-up and any code to the TA: connor2@uiuc.edu.
The coding part of the homework
is also due at the same time.  Use Compass to hand in your code
electronically.  ({\tt http://compass.uiuc.edu})
}

\end{itemize}
\end{footnotesize}

\begin{enumerate}


\item[1.] [Probability] Assume that the probability of obtaining heads when tossing a coin
is $\lambda$.
\begin{itemize}
\item [a.] What is the probability of obtaining the first head at the
  $(k+1)$-th toss?
\item [b.] What is the expected number of tosses needed
    to get the first head?
\end{itemize}

\item[2.] [Probability] Assume $X$ is a random variable.
\begin{enumerate}
\item [a.] We define the variance of $X$ as: $Var(X) = E[(X - E[X])^2]$.
Prove that $Var(X) = E[X^2] - E[X]^2$.

\item [b.] If $E[X] = 0$ and $E[X^2] = 1$, what is the variance of $X$?
  If $Y = a + bX$, what is the variance of $Y$?
\end{enumerate}

\newpage 
\item[3.]  [Probability] John is a great fortune teller.
    Assume that we know three facts: 
    \begin{itemize} 
    \item If John tells you that a lottery ticket will win, it will win with
    probability 0.99. 
    \item If John tells you that a lottery ticket will not win, it will not win with probability
    0.99999. 
    \item When John sees a ticket he predicts with probability $10^{-5}$ that a ticket is a winning ticket. This also means that
    with probability $1-10^{-5}$, John predicts that a ticket will not win.
    \end{itemize}
  \begin{enumerate}
  \item [a.] Given a ticket, what is the probability that it wins?
  \item [b.] What is the probability that John correctly predicts a winning ticket?
  \end{enumerate}

%\newpage

\item[4.] [Calculus]  Let $f(x,y) = 3 x^2 + y^2 - xy - 11x$
  \begin{itemize}
  \item[a.] Find $\frac{\partial f}{\partial x}$, the partial
    derivative of $f$ with respect to $x$. Find $\frac{\partial
      f}{\partial y}$.

  \item[b.] Find $(x,y) \in \mathbb{R}^2$ that minimizes $f$.
  \end{itemize}


\item[5.] [Linear Algebra] Assume that $w\in \mathbb{R}^n$ and $b$
    is a scalar. A hyper-plane in $R^n$ is the set, $
    \{ x: x \in \mathbb{R}^n, w^T x + b = 0 \}$.
\begin{enumerate}
\item [a.] For $n=2$ and $3$, find two example hyper-planes  (say, for $n = 2$,
$w^T =
  \begin{bmatrix}
    1 & 1
  \end{bmatrix}$ and $b=2$  and for $n = 3$,
$w^T =
  \begin{bmatrix}
    1 & 1 & 1
  \end{bmatrix}$ and $b=3$) and draw them on a paper.
\item [b.] The distance between a point $x_0 \in \mathbb{R}^n$ and the hyperplane $w^T x + b = 0$
can be described as the solution of the following optimization problem:
\begin{align*}
    \min_{x} & \; \| x_0 - x \|^2 \\
	\textrm{s.t. } & w^T x + b = 0
\end{align*}
However, it turns out that the distance between $x_0$
and $w^T x + b = 0$ has an analytic solution. Derive the
solution. ({\em Hint: you may be familiar with another
way of deriving this distance; try your way too.})
\item [c.] Assume that we have two hyper-planes,
    $w^Tx+b_1=0$ and $w^Tx+b_2=0$. What is the distance
    between these two hyperplanes?
\end{enumerate}

\newpage
\item[6.]  [Linear Algebra] One way to define a {\em  \underline{convex}} function is
  as follows. A function $f(x)$ is convex if
\begin{equation*}
  f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)
\end{equation*}
for all $x$, $y$ and $0 < \lambda < 1$.
\begin{enumerate}
\item[a.] Directly from the definition, determine which of the following functions are convex functions?
\begin{enumerate}
\item $(x-5)^2$
\item $g(x)=\max \{f_1,f_2\}$ where $f_1$,$f_2$ are given to be convex functions.
\item $-x^2$
\end{enumerate}
\item[b.] A $n$-by-$n$ matrix $A$ is defined to be {\em
    \underline{positive semi-definite}} matrix if
    $x^T A x \geq 0$, for any $x \in \mathbb{R}^n$ s.t $x \neq 0$.

  Use the definitions to show that the function $f(x) = x^TAx$ is convex if
  $A$ is a positive semi-definite matrix. Note that $x$
  is a vector here. ({\em Hint:
    the solution is somewhat similar to the solution of part (a.)})
\end{enumerate}



\item[7.] [CNF and DNF] Consider the following Boolean
    function written in a conjunctive normal form
    \begin{equation*}
      (x_1 \vee x_2) \wedge (x_3 \vee x_4) \wedge \ldots (x_{15} \vee x_{16})
    \end{equation*}
    If no new variable is introduced, how many clauses do
    you need to write down the same function in disjunctive
    normal form ?
\end{enumerate}



% --------------------------------------------------------------
%     You don't have to mess with anything below this line.
% --------------------------------------------------------------


\end{document} 
