%%Do not change font size
\documentclass[12pt]{article}
\usepackage{amsthm,amssymb,fullpage,graphicx}
\usepackage{floatflt}
\usepackage{hyperref}

\begin{document}

\begin{center}
\begin{tabular}{|c|}
\hline
CS5800: Algorithms Instructor: Virgil Pavlu 
\\
{\bfseries \large Homework 8}\\ \hline
\end{tabular}
\end{center}

%\section{Write here}
% \textbf{\large{Instructions}}

% \begin{enumerate}
% \item Please review the grading policy  outlined in the course information page.
% \item You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.
% \item You should not submit the code, but rather the output on test cases. Do have the code available, we may ask you to demo it.
% \item The grading of these problems is done by demonstration, so you will have to meet the TA and briefly run the code live on a test file.
% \end{enumerate}


\textbf{\large{Problems}}
\begin{enumerate}
\item (50 pts) Implement a hash for text. Given a string as input, construct a hash with words as keys, and word counts as values. Your implementation should include:
\begin {itemize}
\item a hash function that has good properties for text
\item storage and collision management using linked lists
\item operations: insert(key,value), delete(key), increase(key), find(key), list-all-keys
\item each word (key) can only appear once in the datastructure
\end {itemize}

Output the list of words together with their counts on an output file. For this problem, you cannot use built-in-language datastuctures that can index by strings (like hash tables or dictionaries). Use a language that easily implements linked lists. 

You can test your code on ``Alice in Wonderland'' by Lewis Carroll, at\\ 
\url{http://www.ccs.neu.edu/home/vip/teach/Algorithms/\\7\_hash\_RBtree\_simpleDS/hw\_hash\_RBtree/alice\_in\_wonderland.txt}. \\
The test file used by TA, if different, might be shorter.\\
Try these three values for $m=$MAXHASH : 30, 300, 1000. For each of these m values, produce a histogram over the lengths of collision lists. You can also calculate variance of these lengths.\\
If your hash is close to uniform in collisions, you should get variance close to zero, and almost all list-lengths around $\alpha=n/m$\\
If your hash has long lists, we want to know how many and how long, for example print the lengths of the longest 10\% of the lists.\\\\

(Extra Credit) Find a way to record not only word counts, but also the positions in text. For each word, besides the count value, built a linked list with positions in the given text. Output this list together with the count.

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{5ex}
\item (50points) Implement a red-black tree, including binary-search-tree operations \emph{sort, search, min, max, successor, predecessor} and specific red-black procedures \emph{rotation, insert, delete}. \\
You must implement \emph{delete} with functionality for regular BST (without fixup procedure) but implementing \emph{delete} for RB-trees (including fixup procedure) is Extra Credit.


Your code should take the input array of numbers from a file and build a red-black tree with this input by sequence of ``inserts''. Then interactively ask the user for an operational command like ``insert x'' or ``sort'' or ``search x'' etc, on each of which your code rearranges the tree and if needed produces an output. After each operation also print out the height of the tree.

You can use any mechanism to implement the tree, for example with pointers and struct objects in C++, or with arrays of indices that represent links  between parent and children. You cannot use any tree built-in structure in any language.






% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{5ex}
\item ( Implement Skiplists 50 points). Study the skiplist data structure and operations. They are used for sorting values, but in a datastructure more effficient than lists or arrays, and more guaranteed than binary search trees.  Review Slides \url{skiplists.pdf}  and Visualizer \url{https://people.ok.ubc.ca/ylucet/DS/SkipList.html}. The demo will be a sequence of operations (asked by TA) such as for example\\
insert 20, 
insert 40,
insert 10, 
insert 20,
insert 5,
insert 80,
delete 20,
insert 100,
insert 20, 	
insert 30, 
delete 5, 	
insert 50,
lookup 80, etc\\


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \newpage
% \vspace{5ex}
\item (50 pts). Implement binomial heaps as described in class and in the book. You should use links (pointers) to implement the structure as shown in the figure~\ref{binom_heaps}.  Your implementation should include the operations: Make-heap, Insert, Minimum, Extract-Min, Union, Decrease-Key, Delete
% \begin{itemize}
% \item Make-heap, Insert, Minimum, Extract-Min, Union, Decrease-Key, Delete
% \end{itemize}

\begin{figure}[h]
\centering
 \includegraphics{fig482_01_0}
\caption{binomial heaps}
\label{binom_heaps}
\end{figure}

Make sure to preserve the characteristics of binomial heaps at all times: (1) each component should be a binomial tree with children-keys bigger than the parent-key; (2) the binomial trees should be in order of size from left to right.
Test your code several arrays set of random generated integers (keys).

\item Exercise 16.3-3

\newpage

\item (Optional, no credit) Find a way to nicely draw the binomial heap created from input, like in the figure.


\item (Optional, no credit). Write code to implement Fibonacci Heaps, with discussed operations: ExtractMin, Union, Consolidate, DecreaseKey, Delete. 

\item (Optional, no credit). Figure out what are the marked nodes on Fibonacci Heaps. In particular explain how the potential function works for 
FIB-HEAP-EXTRACT-MEAN and FIB- HEAP-DECREASE-KEY operations.


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{5ex}
\item (DP problem; Optional, no credit) The \textbf{int[]} bag describes a bag of non-negative integers. A bag is the same thing as a set, only it may contain repeated elements. The order of elements in a bag does not matter. Given two bags $A$ and $B$, we say that $A$ is a \textit{sub-bag} of $B$ if $A$ can be obtained by erasing zero or more elements from $B$. The \textit{weight} of a bag is the sum of its elements. Examples: The bags $(1,2,1,3,1)$ and $(3,1,1,1,2)$ are the same, but different from the bag $(1,2,3,3)$. Bags $(1,2)$ and $(3,1,1)$ are sub-bags of the bag $(1,2,1,3,1)$, but bag $(1,2,2)$ is not. The weight of the bag $(1,2,1,3,1)$ is $1+2+1+3+1=8$. The bag will contain less than 50 elements, and each element will be less than 10,000. Write a method that will compute how many sub-bags of bag have a prime weight. Your program should \textbf{not} use more than $3M$ memory, and should pass the following testing cases (the running time of each testing case should be within 3 seconds).

Input 1: \{1,1,1,1,1,1,1,1,1,1\}

Return 1: 4

Input 2: \{4,6,8,10,12,14\}

Return 2: 0

Input 3: \{1,2,4,8,16,32,64,128\}

Return 3: 54

Input 4: \{9947, 9948, 9949, 9950, 9951, 9952, 9953, 9954, 9955, 9956, 9957, 9958, 9959, 9960, 9961, 9962, 9963, 9964, 9965, 9966, 9967, 9968, 9969, 9970, 9971, 9972, 9973, 9974, 9975, 9976, 9977, 9978, 9979, 9980, 9981, 9982, 9983, 9984, 9985, 9986, 9987, 9988, 9989, 9990, 9991, 9992, 9993, 9994, 9995, 9996\}

Return 4: 91378169764810

Input 5: \{9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9947, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934, 9934\}

Return 5: 54

Input 6: \{1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096\}

Return 6: 62648678

Input 7: \{10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991, 9990, 9989, 9988, 9987, 9986, 9985, 9984, 9983, 9982, 9981, 9980, 9979, 9978, 9977, 9976, 9975, 9974, 9973, 9972, 9971, 9970, 9969, 9968, 9967, 9966, 9965, 9964, 9963, 9962, 9961, 9960, 9959, 9958, 9957, 9956, 9955, 9954, 9953, 9952, 9951\}

Return 7: 89655114688016

Input 8: \{9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999\}

Return 8: 4814999

Input 9: \{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000\}

Return 9: 6555
\end{enumerate}

\end{document}
