main.tex

\documentclass[addpoints]{exam}

% Header and footer.
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\runningheader{CS 201 DS II}{Homework 1}{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 Me}  % replace with your ID, e.g. sh01703
\date{Homework 1\\Due: 19h, 2 Feb}

\begin{document}
\maketitle

\begin{questions}

\titledquestion{Exercise 2.1*}[10]

The List method {\tt add\textunderscore all(i, c)} inserts all elements of the Collection {\tt c} into the list at position {\tt i}. (The {\tt add(i, x)} method is a special case where {\tt c = \{x\}}.)

Explain why, for the data structures in Chapter 2, it is not efficient to implement {\tt add\textunderscore all(i,c)} by repeated calls to {\tt add(i, x)}. Design a more efficient implementation.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 2.4*}[5]

Design a method {\tt rotate(a,r)} that ``rotates'' the array {\tt a} so that {\tt a[i]} moves to {\tt a[(i + r) mod length(a)], for all i $\in$ \{0, ... ,  length(a)\}}.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 2.5*}[5]

Design a method {\tt rotate(r)} that ``rotates'' a List so that list item $i$ becomes list item $(i + r) \bmod n$. When run on an ArrayDeque, or a DualArrayDeque, {\tt rotate(r)} should run in $O(1 + \min{r, n-r})$ time.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 2.8*}[10]

Design a variant of ArrayDeque that does not do any modular arithmetic at all. Instead, all the data sits in a consecutive block, in order, inside an array. When the data overruns the beginning or the end of this array, a modified {\tt rebuild()} operation is performed. The amortized cost of all operations should be the same as in an ArrayDeque.

{\it Hint}: Getting this to work is really all about how you implement the {\tt rebuild()} operation. You would like {\tt rebuild()} to put the data structure into a state where the data cannot run off either end until at least $n/2$ operations have been performed.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 3.1}[10]

Why is it not possible to use a dummy node in an SLList to avoid all the special cases that occur in the operations {\tt push(x), pop(), add(x)}, and {\tt remove()}?
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 3.2*}[5]

Design an SLList method, {\tt second\textunderscore last()}, that returns the second-last element of an SLList. Do this without using the member variable, $n$, that keeps track of the size of the list.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 3.4*}[5]

Design an SLList method, {\tt reverse()} that reverses the order of elements in an SLList. This method should run in $O(n)$ time, should not use recursion, should not use any secondary data structures, and should not create any new nodes.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 3.8*}[5]

Design a method {\tt rotate(r)} that ``rotates'' a DLList so that list item $i$ becomes list item $(i + r) \bmod n$. This method should run in $O(1 + \min\{r, n-r\})$ time and should not modify any nodes in the list.
\begin{solution}
  % Write your solution here
\end{solution}

\titledquestion{Exercise 3.19* (challenge)}[0]

Show using pseudocode how the bitwise exclusive-or operator, \^{}, can be used to swap the values of two {\tt int} variables without using a third variable.
\begin{solution}
  % Write your solution here
\end{solution}

* - The question has been modified from the one in the book to exclude implementation. ``Design'' in a question here means to write pseudocode.
\end{questions}

\end{document}