CSE 326 – Data Structures

CSE 326 – Data Structures – Winter 2002

Homework #1 – Lists and Sparse Vectors

Due Friday, Jan. 18, 2002
Written material – proofs, plots, discussion, etc., - hand in hardcopy in class

Programs – use electronic turn-in – details on course web page

Goals of this assignment:

Introduce the ADTs (abstract data types) for lists and sparse vectors, motivated by an application to information retrieval.
Show the connection between the empirical runtime scaling of an algorithm and formal asymptotic complexity
Gain experience with the Unix tools g++, make, gnuplot, csh, and awk.
Learn how to use templates in C++.

Important: check the course web page over the next several days for example scripts, code fragments you can use, and other helpful advice.

Your written answers to the questions and discussion of results should be precise and concise: a few well-written sentences.

1. Define an ADT for lists using C++ templates that supports the following operations:

· Push – insert element at head of list

· Pop – remove element from head of list

· Empty – return true if the list is empty, false otherwise

· Length – return the length of the list

· Member – return true if the element is a member of the list, false otherwise.

· Create, destroy, and copy using appropriate C++ operators.

Provide an implementation of this ADT using singly-linked lists. Do not use dummy nodes. The only data element contained in the type should be a pointer to a node. The operations Push, Pop, and Empty should run in constant time, and Length and Member in time linear in the length of the list. Methods should throw appropriate errors (e.g. for trying to pop an empty list, for running out of memory, etc.). Make sure there are no memory leaks in your implementation. You will be reusing this code for several other assignments, so make your code as clean and robust as possible.

The textbook provides a lot of code for implementing lists. You will learn the most from this exercise if you first study the examples, and then close the textbook while you are actually writing your own code.

2. Application of lists: Sparse vectors for information retrieval. Free-text search engines (such Google or Altavista) employ information retrieval algorithms in which documents are represented by vectors in a very high-dimensional space. Specifically, there is a dimension for every possible word in some enormous dictionary. The vector for a particular document is assigned a “1” in a particular dimension if the document contains the corresponding word and “0” otherwise. For example, suppose the dictionary is:

[ aardvarks, apples, ants, earwig, eat, fungus … ]

Then a document consisting of only the sentence “Aardvarks eat ants” would be represented by the Boolean vector (1 0 1 0 1 0 … ) where all the “…” are zeros. (Note that sentence “Ants eat aardvarks” receives exactly the same representation.)

Vector representation makes it easy to define various operations on documents and queries (where a query is treated as just another document). For example, the words that two documents have in common can be computed by taking the bit-wise AND of their vectors. For example, the words that “Aardvarks eat ants” and “Ants eat fungus” have in common can by computed as follows:

(1 0 1 0 1 0 …) & (0 0 1 0 1 1 …) = (0 0 1 0 1 0 …)

The obvious problem with this approach is that the number of dimensions – the number of possible words in any document – is huge. Employing a sparse vector representation solves this problem: instead of writing out the entire Boolean vector, simply represent a document by a list of its non-zero dimensions in ascending order. The sentence “Aardvarks eat ants” is represented as (1 3 5). The example of computing the words two documents have in common becomes:

(1 3 5) & (3 5 6) = (3 5)

Define a Sparse Boolean Vector datatype as a specialization of your List template where the data element is of type integer. Make sure that inherited methods work properly or are overridden as appropriate.

Define input (>>) and output (<<) operators for integer lists by overloading the appropriate methods of ostream and istream. On the web page we provide a function for parsing input that makes it much easier to define the input operator. The format of a list is:

(list_item list_item … list_item)

That is: a list begins with a “(“, optionally followed by whitespace, followed by zero or more list items separated by whitespace, optionally followed by whitespace, terminating with a “)”. Whitespace is any combination of blanks, tabs, and newlines. You may assume that list items do not contain parentheses or whitespace. Your input operator should throw appropriate errors for malformed input.

Implement the following three different functions for computing the bitwise AND of two sparse Boolean vectors. Each method should take two SBVs as arguments. After a call to a function, the first list should contain the bitwise AND of the two lists.

· And1 should use only the Push, Pop, and create methods. It should not access the private data of a list or its nodes directly. After execution, the first list will contain the bitwise AND of the two lists, and the second list will contain no elements. Note that you may need to create a third temporary list in the procedure, and that many nodes may be allocated and deallocated in the process. The method should run in time linear in the lengths of the lists.

· And2 is allowed to directly access the nodes in the first list but not the second. It implements the following algorithm:

For each element in List1

if the element is a member of List2

then leave it in List1

else remove it from List1

This method only accesses List2 via the Member method, and leaves List2 unchanged. It may deallocate some nodes that appeared in List1 but never allocates any new nodes. This method should run in time quadratic in the length of the lists.

· And3 is allowed to access the private data of both lists. It should make a single pass over both lists. The second list should be left unchanged. It may deallocate some nodes from the first list but should never allocate any new nodes. The method should run in time linear in the sum of the length of the lists.

Create a program named “sbv” that uses these functions. The command line arguments for sbv should be as follows:

sbv [method] [input filename1] [input filename2] [output filename]

sbv [method] [-n MAX]

[method] should be one of -a1, -a2, or -a3, to indicate the respective method to be employed. In the first form of the command, lists are read from two files, AND-ed, and written to another file. In the second, two lists of length MAX containing the integers from 1 to MAX are created and then AND-ed, but no output is written.

3. Provide a formal proof of the upper-bound (big-O) asymptotic running time of each of the methods And1, And2, and And3, by writing down and solving the expression that represents their running time. Be careful to specify exactly what the variables in the expression stand for.

4. Measure the empirical scaling of the different methods for AND-ing two sparse vectors using the csh “time” command and the -n form of your sbv program. Start with MAX=1 and then double MAX until you reach 32,768 nodes. After you debug your program you will find it easier to run this kind of repeated experiment using a shell script rather than running each time by hand. The features of csh that are most useful for doing this will be discussed in section and linked to the course web page.

Plot the “user time” as reported by the time command using gnuplot. The x-axis should be n (that is, MAX) and the y-axis should be the number of seconds. The command “awk” is useful for manipulating the output of one program – in this case, the output of the “time” command – into a form that is desired by another program – in this case, the form expected by gnuplot, a file containing a sequence of x-y values. You will that your graphs start out relatively constant for the first few values of MAX. Discuss reasons as to why this occurs.

Do you indeed see a nearly straight line for And1 and And3? Measure by hand the slope and intercept of the line to get an estimate of the actual constants in the run-time equation for the methods. How worthwhile is the savings of not allocating and destroying nodes in And3?

The plot of And2 should be a curve. Verify that this curve is in fact a quadratic by plotting it a second time using gnuplot, but with the x and y-axes on a logarithmic scale. (Use the gnuplot command “set logscale y” and “set logscale x”.) On a logscale the curve should be approximately a straight line. Measure the slope of this line: the slope is equal to the exponent in the run-time equation – that is, it should be about 2. Write down the mathematics that explains why the slope does in fact equal the exponent.

Discuss your results. What are the sources of inefficiency in And1 and And2? What kinds of inefficiencies are most significant for large inputs? When is And2 as good or better than And3?