\documentclass[11pt]{article}

\usepackage{fullpage}
\usepackage{graphicx,epsfig}

\title{Algorithms Crash Review}
\date{}

\begin{document}

\maketitle

\vspace{-1cm}

Here is a list of fundamental topics studied in algorithms:
\begin{enumerate}
\item Worst case, best case running times. 
  \begin{itemize} 
    \item Binary search runs in logarithmic  time worst case and constant time best case. 
  \end{itemize} 
\item Asymptotic growth of functions ($O, \Omega, \Theta$). Used to talk about complexity of algorithms. 
  \begin{itemize} 
  \item This algorithm runs in $O( n^2)$ worst case. 
  \item This algorithm runs in $\Theta(n \lg n)$ worst case. 
  \end{itemize} 

\item Recurrences and summations. Used to analyze complecity of
  algorithms and in particular recursive algorithms.
  \begin{itemize}
  \item Example: mergesort recurrence: $T(n) = 2T(n/2) + \Theta(n)$ solves to $\Theta(n \lg n)$.
  \end{itemize} 

\item Comparison-based Sorting
%  stable sort, in-place sort
  \begin{itemize}
  \item (quadratic sorts: insertion sort, bubble sort, selection sort)
  \item Mergesort
  \item Quicksort, Randomized quicksort
  \item Heapsort
  \item Comparison-based sorting lower bound: Any sorting algorithm that uses only comparisons to order teh elements must take $\Omega(n \lg n)$ in the worst case. 
  \end{itemize}
\item Linear-time sorting 
  \begin{itemize}
  \item Not a general purpose sort; need additional assumptions,
    usually that the keys to be sorted are integers in a small range.
  \item Example: sort $n$ keys that are all integers in teh range $\{ -10,...,10 \}$.
  \item Counting sort, Radix sort, Bucket sort
    \item Generally run in $O(n+k)$ where $k$ is the range
  \end{itemize}

\item Selection:  given a set of $n$ elements, find the $i$th smallest. 
  \begin{itemize} 
  \item Via sorting, in $O(n \lg n)$ time. 
  \item Direct algorithm in $O(n)$ time 
  \end{itemize} 

\item Data structures:
  \begin{itemize}
  \item Priority queue: supports FIND-MIN, DELETE-MIN, INSERT, DELETE,
    CHANGE-KEY. Max priority queue, min priority queue.
         
  \item Dictionary: supports INSERT, DELETE, SEARCH
  \item Union-Find: supports MAKE-SET, FIND-SET, UNION-SET
  \end{itemize}
\item Data structure implementations
  \begin{itemize}
  \item Heap as priority queue
  \item Balanced binary search trees for dictionaries. 
  \end{itemize} 

  
\item Binary search trees 
  \begin{itemize}
  \item binary search tree property
  \item tree walks
  \item supports INSERT, DELETE, SEARCH, MIN, MAX, PRED, SUCC in $O(h)$ time 
  \end{itemize}

\item Red-black trees
  \begin{itemize}
  \item height is manintained $O(\lg n)$ via rotations 
  \item all operations run in $O(\lg n)$ time
  \end{itemize}

% \item Augmented search trees
%    \begin{itemize}
%    \item augment every node $x$ with some additional information $f(x)$;
%      maintain $f(x)$ under INSERT and DELETE in the same asymptotic bounds.
%    \item Sufficient if $f(x)$ can be computed using only $f(left(x))$ and
%      $f(right(x))$.
%    \item implement SELECT(i), RANK(x) by augmenting every node $x$ with
%      $size(x)$
%    \item Interval tree
%    \end{itemize}

\item Dynamic programming
   \begin{itemize}
   \item technique used for solving optimization problems that have
     optimal substructure, and overlapping subproblems
   \item Classical examples: 0-1 knapsack, rod cutting, longest common
     subsequence, maximum sub-array, weighted interval scheduling,
     subset sum, weighted subset sum (0-1 knapsack), sequence
     alignment, longest common subsequence; also shortest paths:
     Bellman Ford, APSP
   \item approach: express teh problem recursively; store (cache)
     partial solutions in a table.
\end{itemize}

\item Greedy algorithms
  \begin{itemize}
  \item Solves optimization problems by ``quickly'' finding the best
    choice, taking it, and recursing on what's left. The best choice
    is determined greedily by examing only local information, without
    going into recursion.
  \item Classical examples: fractional knapsack, interval scheduling;
    also Dijkstra SSSP, Prim and Kruskal's algorithm for MST are all
    greedy.
  \item Greedy heuristics are used a lot in AI and are good starting
    points for optimization problems.
  \end{itemize}


\item Graph algorithms
  \begin{itemize}
  \item Graph representation (adjacency list, adjacency matrix)
  \item Graph traversal: BFS 
    \begin{itemize}
    \item $G$ can be directed or undirected
    \item BFS runs in linear time 
    \item BFS used to: find connected components ($G$ undirected),
      check bipartiteness ($G$ undirected), compute shortest paths
      ($G$ un-weighted, all edges have weight $1$)
    \end{itemize}
  \item Graph traversal: DFS
    \begin{itemize}
    \item $G$ can be directed or undirected
    \item DFS runs in linear time 
    \item DFS used for: find connected components, reachability, find
      cycles (back edges), topological sort ($G$ directed, acyclic)
    \end{itemize}

 \vspace{.3cm}
  \item Acyclic directed graphs: topological ordering 
    \begin{itemize}
    \item Ordering of the vertices such that all edges are ``forward''. 
    \end{itemize} 

 \vspace{.3cm}
  \item Minimum spanning tree (MST)
    \begin{itemize}
    \item $G$: connected, undirected, weighted
    \item MST can be computed in $O(E \lg V)$ time with Prim's 
      or  Kruskal's algorithms
    \end{itemize}
 
     \vspace{.3cm}
 \item Single source shortest paths (SSSP): Find shortest paths from a vertex to all other vertices
       \begin{itemize}

         \item  $G$: directed, weighted
         \item On directed unweighted graphs SSSP can be computed by BFS in $O( E + V)$ time
         \item On directed acyclic graphs, SSSP can be computed in $O( E + V)$ time
           with dynamic programming

       \item  Dijkstra's SSSP algorithm
       \begin{itemize}
       \item  Runs in $O( E \lg V)$ time 
       \item Works correctly only if $G$ has  non-negative weights
       \end{itemize}
     
     \item If graphs has negative  edge weights, SSSP can be computed but takes longer than Dijkstra's algorithm (Bellman-Ford's algorithm, $O(EV)$)
     \end{itemize}       
     
  \vspace{.3cm}
   \item All pair shortest paths (APSP): find SP between all pairs of  nodes in $G$
     \begin{itemize}
     \item Floyd-Warsall's algorithm 
     \end{itemize}

 \end{itemize}
     
     

 \item Complexity:
  \begin{itemize}
  \item $P$: problems that can be solved in polynomial time  (on a deterministic Turing machine) 
  \item $NP$: problems that can be verified in polynomial time 
  \item $NPC$: a  problem is in $NPC$ if it is in $NP$ and all problems in $NP$ reduce to it in polynomial time. Intuitively speaking, NPC is the hard core of NP. 
    % \item {\it reducibility and reduction lemma}
    % \item {\it proving a problem is in NPC}
  \item Some NPC problems: SAT (satisfiability: is there an assignment
    that makes a given formula true), traveling salesman (TSP: find minimum-cost tour)
    \item The \$1M  questions: Is $P = NP$? Not known.  Most people believe the answer is NO. 
    % \item open questions
  \end{itemize}
\end{enumerate}




\newpage
\section*{Interview tips}

The following tips were taken from: \emph{Hacking a Google Interview–MIT,
Instructors: Bill Jacobs and Curtis Fonger
http://courses.csail.mit.edu/iap/interview}.

\vspace{1cm}
When asked a question, open a dialog with the interviewer.  Let them
know what you are thinking.  You might, for example, suggest a slow or
partial solution (let them know that the solution is not ideal),
mention some observations about the problem, or say any ideas you have
that might lead to a solution.  Often, interviewers will give hints if
you appear to be stuck.

Often, you will be asked to write a program during an interview.  For
some reason, interviewers usually have people write programs on a
blackboard or on a sheet of paper rather than on a computer.  It is
good to get practice with writing code on the board in order to be
prepared for this.

Here is a list of "do's" and "don't's" when doing a programming
interview:

\paragraph{Do's:}

\begin{itemize} 
\item  Ask for clarification on a problem if you didn't understand
something or if there is any ambiguity


\item  Let the interviewer know what you are thinking

\item  Suggest multiple approaches to the problem


\item  Bounce ideas off the interviewer (such as ideas for data structures
or algorithms)


\item If you get stuck, don't be afraid to let them know and politely ask
for a hint
\end{itemize} 



\paragraph{Don't's: }

\begin{itemize}  
\item Never give up!
This says nothing good about your problem solving skills.


\item Don't just sit in silence while thinking. The interviewer has
  limited time to find out as much as possible about you, and not
  talking with them tells them nothing, except that you can sit there
  silently.


\item If you already know the answer, don't just blurt it out!  They
  will suspect that you already knew the answer and didn't tell them
  you've seen the question before.  At least pretend to be thinking
  though the problem before you give the answer!


\end{itemize}


\newpage
\section*{Sample interview questions}

Taken from Hacking a Google Interview Practice Questions – MIT 
\\
\texttt{http://courses.csail.mit.edu/iap/interview/}.


\begin{enumerate}

\item Question: Searching through an array.  

  Given a sorted array of integers, how can you find the location of a
  particular integer x?

  

\vspace{1cm}
\item Question: Target Sum.  

  Given an integer x and an unsorted array of integers, describe an
  algorithm to determine whether two of the numbers add up to x.  (In
  this case, say that the interviewer hates hash tables.)

 
\vspace{1cm}
\item Question: Nearest Neighbor.  Say you have an array containing
  information regarding n people.  Each person is described using a
  string (their name) and a number (their position along a number
  line).  Each person has three friends, which are the three people
  whose number is nearest their own.  Describe an algorithm to
  identify each person's three friends.


\vspace{1cm}
\item Question: Given an array of integer, find the number of un-ordered pairs
  in that array, say given {1, 3, 2}, the answer is 1 because {3, 2}
  is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3,
    2}, {3, 1}, {2, 1}.

 \vspace{1cm}
\item Question: Obstacle Avoidance.  

  Given an n x n grid with a person and obstacles, how would you find
  a path for the person to a particular destination?  The person is
  permitted to move left, right, up, and down.
 
\vspace{1cm}
\item Question: Axis Aligned Rectangles

  Describe an algorithm that takes an unsorted array of axis aligned
  rectangles and returns any pair of rectangles that overlaps, if
  there is such a pair.

  Axis aligned means that all the rectangle sides are either parallel
  or perpendicular to the x‐ and y‐axis.

  You can assume that each rectangle object has two variables in it:
  the x‐y coordinates of the upper‐left corner and the bottom‐right
  corner.


\end{enumerate}

\newpage
\begin{enumerate}

\item Question: Searching through an array.  Given a sorted array of
  integers, how can you find the location of a particular integer x?

  Good answer: Use binary search.  Compare the number in the middle of
  the array with x.  If it is equal, we are done.  If the number is
  greater, we know to look in the second half of the array.  If it is
  smaller, we know to look in the first half.  We can repeat the
  search on the appropriate half of the array by comparing the middle
  element of that array with x, once again narrowing our search by a
  factor of 2.  We repeat this process until we find x.  This
  algorithm takes O(log n) time.

  Not‐so‐good answer: Go through each number in order and compare it
  to x.  This algorithm takes O(n) time.


\vspace{.8cm}
\item Question: Target Sum.  Given an integer x and an unsorted array
  of integers, describe an algorithm to determine whether two of the
  numbers add up to x.  (In this case, say that the interviewer hates
  hash tables.)

  Good Answer: Sort the array.  For each number $a$ in teh array,
  binary searchfor $x-a$.  This solution takes O(n log n) time because
  we sort the numbers and then perform $n$ binary searches.


\vspace{.8cm}
\item Question: Nearest Neighbor.  Say you have an array containing
  information regarding n people.  Each person is described using a
  string (their name) and a number (their position along a number
  line).  Each person has three friends, which are the three people
  whose number is nearest their own.  Describe an algorithm to
  identify each person's three friends.

  Good answer: Sort the array in ascending order of the people's
  number.  For each person, check the three people immediately before
  and after them.  Their three friends will be among these six people.
  This algorithm takes O(n log n) time, since sorting the people takes
  that much time.


\vspace{.8cm}
\item Given an array of integer, find the number of un-ordered pairs
  in that array, say given {1, 3, 2}, the answer is 1 because {3, 2}
  is un-ordered, and for array {3, 2, 1}, the answer is 3 because {3,
    2}, {3, 1}, {2, 1}.

  Good answer: Obviously, this can be solved by brute force with
  $O(n^2)$ running time, or permute all possible pairs then eliminate
  those invalid pairs. BVut can be done better in $O(n \lg n)$ via
  divide and conquer.

\vspace{.8cm}
\item Question: Obstacle Avoidance.  Given an n x n grid with a person
  and obstacles, how would you find a path for the person to a
  particular destination?  The person is permitted to move left,
  right, up, and down.

  Good Answer: Use BFS, or any shortest path ‐finding algorithm.






\vspace{1cm}
\item Question: Axis Aligned Rectangles

  Describe an algorithm that takes an unsorted array of axis aligned
  rectangles and returns any pair of rectangles that overlaps, if
  there is such a pair.

  Axis aligned means that all the rectangle sides are either parallel
  or perpendicular to the x‐ and y‐axis.

  You can assume that each rectangle object has two variables in it:
  the x‐y coordinates of the upper‐left corner and the bottom‐right
  corner.



  Good Answer: Create a sorted array of the x coordinates of the left
  and right edges of the rectangles.  Then, use a "scanline" to move
  from left to right through the rectangles.  Keep a binary search
  tree containing the y coordinates of the top and bottom edges of the
  rectangles that overlap the scanline.  For each element of the
  array, check whether it is a left or right edge.  If it is a right
  edge, remove the corresponding top and bottom edges from the BST.
  If it is a left edge, search the BST for rectangles that overlap the
  current rectangle; if there is one, return the overlap.  Then, add
  the y coordinates of the top and bottom edges of the rectangle to
  the BST.  The search takes O(n log n) time, since it takes O(n log
  n) time to sort the rectangles and each of the 2n iterations takes
  O(log n) time.



\end{enumerate}


\section*{More interview problems} 

Here is a list of interview questions I have collected from Bowdoin students: 


\begin{enumerate}

\item  You are presented with 9 marbles. All of the marbles look identical
  i.e. same shape, color, and dimensions(except for weight). However,
  8 of the 9 marbles have exactly the same weight; the last marble is
  heavier. The only tool you have to measure weights is an old
  fashioned balance scale. You are only allowed to use the scale 2
  times. How do you find the one marble that is not the same weight as
  the others?

\item Write a program to match parenthesis. Then write a program to make sure all parenthesis, curly braces and brackets are matched properly. 


\item 
Given a list of license plates and a dictionary as a list, find the shortest word in the dictionary that can be made using the characters of the license plate (which may also contain numbers).

\item  Given a binary tree, write a method to verify if the tree is a
  binary search tree in linear time in linear time and constant space.
  (note: between easy and medium)

\item  Write a function to find the kth biggest number in an unsorted array
  in linear time (expected).  (note: easy)

\item  Given an unsorted array and a number K. Find a subset of the array
  whose sum is K. 

  (note: medium - The reason why this is medium is this is the subset
  sum classic problem and a lot of candidates will immediately know
  how to solve it)

  PS: Normally the interviewer would start off asking about the 2-Sum problem, then 3-Sum and then they'd ask to generalize to find any subset. Again, it emphasizes how important the thought process is.


\item   Given k sorted arrays, write a method to merge the into one sorted
  array.

  (note: easy - this problem, however, is often used as an
  intermediate step for harder problems)


\item  How would you implement a data structure that can support push(), pop() and peekMin() in constant time? (note: medium to hard)


\item  Compare Dijkstra and A*.


\item   Write a routine in pseudocode to reverse the bits in a word passed
  as input (using bitwise operations!).


\item   You are in charge of planning a party for a company. The
  company has a hierarchical structure, which forms a
  tree rooted at the president. Each person has a supervisor, and
  possibly some people whom they supervise. Assume everyone
  is listed at the
  highest possible position in the tree and there are no double
  affiliations (everybody has only one supervisor).
  The company also has a (secret?) database which ranks each
  person with a conviviality rating (a real number,
  which can be negative if the person is really difficult or boring).
  In order to make the party fun for everybody, the president does
  not want both a person and his/her immediate
  ``supervisor'' to attend.

  You are given a tree that describes the strucure of a company.
  Each node also holds a name and a conviviality ranking. Describe an
  algorithm to make up a guest list that maximizes the sum of the
  conviviality rankings of the guests. Analyze the running time of
  your algorithm.


\item  Suppose you have an n-stories high building, and a bunch of eggs.
  An egg has a certain level $l$ at which , if
  thrown from any level $\ge l$ , it breaks. For example, an egg might
  have $l=7$ meaning you can safely throw the egg down from levels 1
  through 6, and it will not break; but if you through the egg from a
  level 7 or higher, it breaks.

  You are given a building and a bunch of eggs (all identical) and
  your goal is to find out the level $l$ of the eggs. We can assume
  $n=100$ (i.e. 100-level high building).

\begin{itemize}

\item Describe an approach that only breaks one egg to find out $l$.
  How many throws does it do? \item Describe an approach that
  minimizes the number of throws. How many eggs might it break?

\item Assume now you have two eggs.  Describe an approach that minimizes the number of throws.
What if you had 3 eggs? 
\end{itemize}


\end{enumerate}


\end{document}
