\documentclass[10pt]{article}

\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}





\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother


\usepackage{natbib}




\renewenvironment{abstract}
  {{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
  {\bigskip}

\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}


\usepackage{authblk}


\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%

\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}










\begin{document}

\title{Problem Solving}



\author[1]{James S. Wang}%
\affil[1]{Johns Hopkins University}%


\vspace{-1em}



  
  \date{May 07, 2024}


\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup








\sloppy




\section*{General Problem Solving}\label{general-problem-solving}

\begin{itemize}
\tightlist
\item
  There are three different levels in the problem solving process:
\end{itemize}

\textbf{Strategy} \textasciitilde{} These are mathematical and
psychological ideas for starting and pursuing problems. \textbf{Tactics}
\textasciitilde{} These are diverse mathematical methods that work in
many different settings. \textbf{Tools} \textasciitilde{} These are
narrowly focused techniques and ``tricks'' for specific situations.

\textbf{Investigation} \textasciitilde{} Don't try to immediately solve
the problem, but instead think about it on a less-focused level. This is
when you start by familiarizing yourself with the problem and
identifying what the problem is asking you to do. \textbf{Argument}
\textasciitilde{} This is when you convince others of your discoveries.

\begin{itemize}
\tightlist
\item
  A good problem solver doesn't give up. He also doesn't just stupidly
  keep banging his head against a wall, but instead \emph{varies each
  attempt.} However, an important part of the problem solver's art is
  knowing when to give up.
\item
  \emph{Just because a problem seems impossible does not mean that it is
  impossible. Never admit defeat after a cursory glance. Begin
  optimistically; assume that the problem can be solved. Only after
  several failed attempts should you try to prove impossibility. If you
  cannot do so, then do not admit defeat. Go back to the problem later.}
\item
  Avoid immediate declarations of impossibility; they are dishonest.
\end{itemize}

\textbf{Creativity} \textasciitilde{} This is the elusive receptiveness
to new ideas. You should never claim that you ``could never have thought
of that,'' but instead think ``Nice idea! It's similar to ones I've had.
Let's put it to work.'' \emph{Learn to shamelessly appropriate new ideas
and make them your own.} * Many of the times, you are letting
self-imposed, unnecessary restrictions limit your thinking. Ask
yourself: ``Am I imposing rules I don't need to? Can I change or bend
the rules to my advantage?''

\textbf{The First Step: Orientation} \textasciitilde{} These are things
that must be done at the beginning of every problem: Read the problem
carefully, Begin to classify, Identify the hypothesis and conclusion,
brainstorm, and summarize. It's RIBS but there's a C after the R. 1.
Read the problem carefully. Pay attention to details such as positive
vs.~negative, finite vs.~infinite, etc. 2. Begin to classify - Is it a
``to find'' or a ``to prove'' problem? Is the problem similar to others
you have seen? 3. Carefully identify the hypothesis and the conclusion.
4. Try some quick preliminary brainstorming * Think about convenient
notation * Does a particular method of argument seem plausible? * Can
you guess a possible solution? Trust your intuition! * Are there key
words or concepts that seem important? For example, might prime numbers
or perfect squares or infinite sequences play an important role? 5. Now
that you've understood the problem, can you summarize the problem in its
simplest terms?

\begin{itemize}
\tightlist
\item
  After you have understood the problem, you may try one or more of the
  four basic ``startup'' strategies: penultimate step, get your hands
  dirty, wishful thinking, and make it easier.
\end{itemize}

\textbf{The Second Step: Strategizing} \textasciitilde{} These are next
steps after orientation and understanding the problem. One of the
following may provide insight into how to solve the problem: Get your
hands dirty, Penultimate step, Wishful thinking, and Make it easier.
It's GPMW (Gold Per Minute, Wealthy).

\textbf{Get Your Hands Dirty} - This is a strategy where you plug in
numbers into the problem and play around with them until you see a
pattern. If you detect a pattern, try to figure out why the pattern is
happening. \textbf{Penultimate Step} - This is a strategy usable after
you find out what the desired conclusion of the problem is. Ask
yourself, ``What will yield the conclusion in a single step?'' For
example, if you want to prove that \emph{A} != \emph{B}, perhaps you
could try to show that A is always even and B is always odd.
\textbf{Wishful Thinking \& Make It Easier} \textasciitilde{} These are
strategies where you ask yourself, ``What is it about the problem that
makes it hard?'' Then, make the difficulty disappear. Temporarily
avoiding the hard part of the problem could prove insightful on how to
solve the harder parts.

\begin{itemize}
\item
  \emph{Time spent thinking about a problem is always time worth spent.
  Even if you seem to make no progress at all.}
\item
  \emph{Don't skimp on experimentation! KEep messing around until you
  think you understand what is going on. Then mess around some more.}
\item
  Common Abbreviaions and Stylistic Conventions in Mathematics:
\end{itemize}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Most good mathematical statements start with clear statements of the
  hypothesis and conclusion. Ending arguments are usually marked with a
  symbol such as the following three:

  \begin{itemize}
  \tightlist
  \item
    \textbf{QED} \textasciitilde{} This means the Latin \emph{quod erat
    demonstrandum} (``which was to be demonstrated''), or the English
    ``quite elegantly done.''
  \item
    \textbf{AWD} \textasciitilde{} This means ``and we're done.''
  \item
    \textbf{W\^{}5} \textasciitilde{} This means ``which was what we
    wanted.''
  \end{itemize}
\item
  Like ordinary exposition, mathematical arguments should be complete
  sentences with nouns and verbs.

  \begin{itemize}
  \tightlist
  \item
    \textbf{Common Mathematical Verbs} \textasciitilde{} These include
    equal to, not equal to, less than or equal to, greater than or equal
    to, less than, greater than, is an element of, is a subset of,
    implies, and is equivalent to. \[\begin{array}{l} = & \neq & \leq & \geq & < & > & \subset & \in & \implies & \iff \end{array}\]
  \end{itemize}
\item
  Complicated equations should always be displayed on a single line, and
  labeled if referred to later. \[\int_{-\infty}^\infty e^{-x^2} dx = \sqrt{\pi}\]
\item
  Often, as you explore the penultimate step of an argument, you want to
  mark this off to your audience clearly. The abbreviation \emph{TS} and
  \emph{ISTS} (``to show'' and ``it is sufficient to show'') are
  particularly useful for this purpose.
\item
  A nice bit of notation borrowed from computer science is slowly
  becoming more common in mathematics and it is ``:='' for ``is defined
  to be.'' For example, we can introduce the variable A as the sum of B
  and C through ``A := B + C.'' Notice the colon distinguishes between
  the left and the right side of the expression, indicating which is the
  new variable.
\item
  A strictly formal argument may deal with many logically similar cases.
  Sometimes it is just as clear to single out one illustrative case or
  example. When this happens, we always alert the audience with
  \emph{WLOG} (``without loss of generality''). Just make sure that you
  really can argue the specific and truly prove the general.
\end{enumerate}

\textbf{Deduction / Direct Proof} \textasciitilde{} This is an argument
that takes the form ``If P, then Q'' or ``P -\textgreater{} Q'' or ``P
implies Q.'' If you have isolated the penultimate step, then you have
reduced the problem to the simple statement: If (penultimate step), then
(conclusion). \textbf{Argument by Contradiction} \textasciitilde{} This
is an argument that starts by assuming what you are trying to prove to
be false and then showing that the assumption leads to a contradiction.
\textbf{Mathematical Induction} \textasciitilde{} This is an argument
for proving assertion that are ``indexed'' by integers. Each assertion
can be put in the form P(n) is true for all integers n \textgreater{}=
n\_0 where P(n) is a statement involving the integer n and n\_0 is the
``starting point.'' There are two forms of this: standard and strong.
\textbf{Standard Induction} \textasciitilde{} This is form of induction
that starts by establishing the truth of P(n\_0) (the base case). Then
it assumes that P(n) is true for some arbitrary integer n, called the
inductive hypothesis. Then it shows that the inductive hypothesis
implies that P(n + 1) is also true. This is sufficient to prove P(n) for
all integers n \textgreater{}= n\_0 since P(n\_0) is true and P(n\_0 +
1) is also true. \textbf{Strong Induction} \textasciitilde{} This is a
form of induction that starts by establishing the truth of P(n\_0) (the
base case). Then we can assume that for some n, all of the following are
true: P(n\_0), P(n\_0 + 1), P(n\_0 + 2), \ldots{}, P(n). Then we use
this assumption to prove that P(n + 1) is true.

Other important strategies: \textbf{Draw a Picture} \textasciitilde{}
This is strategy where you translate the problem into a picture to
visualize how the problem works.

\begin{itemize}
\item
  Instead of drawing a picture, it may be helpful to \textbf{recast the
  problem in other ways}, such as with words, colors, or other branches
  of math.
\item
  It may also help to try to \textbf{change your point of view}.
  Sometimes a problem is hard only because we chose the ``wrong'' point
  of view. Spending a few minutes searching for the ``natural'' point of
  view can prove insightful.
\end{itemize}

\textbf{Symmetry} \textasciitilde{} This is a way of finding order in a
problem. An object has this property if there are one or more
non-trivial ``actions'' that leave the object unchanged. It is important
because it gives you ``free'' information about the object. This
property can be geometric (rotational and reflectional), algebraic
(pairing), \&\&Actions that do this are called \emph{symmetries} of the
object.\&\&

\textbf{The Extreme Principle} \textasciitilde{} This principle says
that if possible, assume that the elements of your problem are ``in
order.'' Focus on the ``largest'' and ``smallest'' elements, as they may
be constrained in interesting ways. It is often possible to use this
principle with contradiction.

\textbf{The Pigeonhole Principle} \textasciitilde{} This principle says
that if you have more pigeons than pigeonholes, and you try to stuff the
pigeons into the holes, then at least one hole must contain at least two
pigeons. * Solving pigeonhole principle problems is often a three-part
process: 1. Recognize that the problem might require the pigeonhole
principle. 2. Figure out what the pigeons will be and what the holes
must be. 3. After applying the pigeonhole principle, there is often more
work to be done.

\textbf{The Intermediate Pigeonhole Principle} \textasciitilde{} This
more elaborate version of a previous principle says that if you have p
pigeons and h holes, then at least one of the holes contains at least
ceil(p/h) pigeons.

\textbf{Invariants} \textasciitilde{} This is an aspect of a problem,
usually numerical, that does not change, even if many other properties
do change. \textbf{Parity} \textasciitilde{} This is the simplest
divisibility invariant and it is whether an integer is even (divisble by
2) or odd. The \_\_\_ of a sum of a set of integers is odd if and only
if the number of odd elements is odd. The \_\_\_ of a product of a set
of integers is odd if and if there are no even elements in the set.

\begin{itemize}
\tightlist
\item
  Be on the lookout for ``easy'' invariants. Check to see if you can
  rearrange your problem to get simple numbers such as zero or one.
\item
  Whenever a problem involves integers, ask yourself if there are any
  parity restrictions. Experiment with different values than the given
  if necessary.
\end{itemize}

\textbf{Modular Arithmetic} \textasciitilde{} This is the reductino of
our point of view from the infinite set of integers to the finite set of
possible remainedrs modulo m, where m is chosen cleverly.
\textbf{Monovariant/Semiinvariant} \textasciitilde{} This is a quantity
that may or may not change at each step of a problem, but when it does
change, it does so in only one direction. These are often used in teh
analysis of evolving systems, to show that certain final configurations
must occur, and/or to determine the duratino of the system.

\section*{Coding Problems}\label{coding-problems}

\begin{itemize}
\tightlist
\item
  Follow the Problem-Solving Flowchart when solving coding problems:

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \tightlist
  \item
    \textbf{Listen/Read carefully} and pay very close attention to any
    information in the problem description. You probably need \emph{all
    of it} for an optimal algorithm.
  \item
    \textbf{Debug your example} and make sure your example isn't too
    small or is a special case. Is there any way it's a special case? Is
    it big enough?
  \item
    Get a \textbf{brute-force} solution as soon as possible.
  \item
    Optimize your brute-force with BUD optimization:

    \begin{itemize}
    \tightlist
    \item
      \textbf{B}ottlenecks
    \item
      \textbf{U}nnecessary Work
    \item
      \textbf{D}uplicated Work Or try some of the following ideas:
    \item
      Look for any \textbf{unused info}
    \item
      Solve it manually on an example and then \textbf{reverse engineer}
      your thought process. How did you solve it?
    \item
      Solve it \emph{incorrectly} and then think about why the algorithm
      fails. Can you fix those issues?
    \item
      Make a \textbf{time vs.~space tradeoff}.
    \end{itemize}
  \item
    \textbf{Walk through} your optimal solution in \emph{detail}. Make
    sure you understand each detail before you start coding.
  \item
    \textbf{Implement} and write beautiful code. Modularize your code
    from the beginning and refactor to clean up anything that's not
    beautiful.
  \item
    \textbf{Test} your code in the following order:

    \begin{enumerate}
    \def\labelenumii{\arabic{enumii}.}
    \tightlist
    \item
      Test like you would for a code review
    \item
      Test for unusual or non-standard code
    \item
      Look for hot spots like arithmetic and null nodes.
    \item
      Test small test cases
    \item
      Test for special cases and edge cases
    \end{enumerate}
  \end{enumerate}
\end{itemize}

\selectlanguage{english}
\FloatBarrier
\end{document}

