main.tex

\documentclass[addpoints]{exam}

% Header and footer.
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\runningheader{CS 201 DS II}{Homework I}{Spring 2018}
\runningfooter{}{Page \thepage\ of \numpages}{}
\firstpageheader{}{}{}

\qformat{{\large\bf \thequestiontitle}\hfill[\totalpoints\ points]}
\boxedpoints
\printanswers

\title{Habib University\\CS 201 Data Structures II\\Spring 2018}
\author{Don't Grade Us}  % replace with your team name, e.g. sa00509-sh01703
\date{Homework 1: Interfaces}

\begin{document}
\maketitle

\begin{questions}

\titledquestion{Exercise 1.1*}

This exercise is designed to help familiarize you with choosing the right data structure for the right problem.

For the following problems, you may assume implementations of the interface: Stack, Queue, Deque, USet, and SSet. That is, you can use the name of the Interface to refer to the data structure implementing it.

Each problem below involves reading a text file line by line. You have to propose an appropriate interface--Stack, Queue, Deque, USet, or SSet--which can be used to perform the specified operations on each line. Your proposed solution should be fast enough that even files containing a million lines can be processed efficiently.

For each solution, mention how your proposed data structure can be used to achieve the desired result.

* - adapted from Exercise 1.1 from the book.

\begin{parts}
  \part[5] Read the input one line at a time and then write the lines out in reverse order, so that the last input line is printed first, then the second last input line, and so on.
  \begin{solution}
    % Write your solution here
  \end{solution}
  
  \part[5] Read the first 50 lines of input and then write them out in reverse order. Read the next 50 lines and then write them out in reverse order. Do this until there are no more lines left to read, at which point any remaining lines should be output in reverse order.

  In other words, your output will start with the 50th line, then the 49th, then the 48th, and so on down to the first line. This will be followed by the 100th line, followed by the 99th, and so on down to the 51st line. And so on.

  You should never have to store more than 50 lines at any given time.
  \begin{solution}
    % Write your solution here
  \end{solution}
  
  \part[5] Read the input one line at a time. At any point after reading the first 42 lines, if some line is blank (i.e., a string of length 0), then output the line that occurred 42 lines prior to that one. For example, if Line 242 is blank, then your program should output line 200. This program should be implemented so that it never stores more than 43 lines of the input at any given time.
  \begin{solution}
    % Write your solution here
  \end{solution}

  \part[5] Read the input one line at a time and write each line to the output if it is not a duplicate of some previous input line. Take special care so that a file with a lot of duplicate lines does not use more memory than what is required for the number of unique lines.
  \begin{solution}
    % Write your solution here
  \end{solution}

  \part[5] Read the input one line at a time and write each line to the output only if you have already read this line before. (The end result is that you remove the first occurrence of each line.) Take special care so that a file with a lot of duplicate lines does not use more memory than what is required for the number of unique lines.
  \begin{solution}
    % Write your solution here
  \end{solution}

  \part[10] Read the entire input one line at a time. Then output all lines sorted by length, with the shortest lines first. In the case where two lines have the same length, resolve their order using the usual “sorted order.” Duplicate lines should be printed only once.
  \begin{solution}
    % Write your solution here
  \end{solution}

  \part[5] Do the same as the previous question except that duplicate lines should be printed the same number of times that they appear in the input.
  \begin{solution}
    % Write your solution here
  \end{solution}

  \part[5] Read the entire input one line at a time and then output the even numbered lines (starting with the first line, line 0) followed by the odd-numbered lines.
  \begin{solution}
    % Write your solution here
  \end{solution}

  \part[5] Read the entire input one line at a time and randomly permute the lines before outputting them. To be clear: You should not modify the contents of any line. Instead, the same collection of lines should be printed, but in a random order.
  \begin{solution}
    % Write your solution here
  \end{solution}
\end{parts}


\titledquestion{Exercise 1.2}[5]
A {\it Dyck word} is a sequence of +1's and -1's with the property that the sum of any prefix of the sequence is never negative. For example, +1,−1,+1,−1 is a Dyck word, but +1,−1,−1,+1 is not a Dyck word since the prefix +1 − 1 − 1 < 0. Describe any relationship between Dyck words and Stack push(x) and pop() operations.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 1.4}[10]
Suppose you have a Stack, s, that supports only the push(x) and pop() operations. Show how, using only a FIFO Queue, q, you can reverse the order of all elements in s.
\begin{solution}
  % Write your solution here
\end{solution}

\end{questions}

\end{document}