CSE 373 -- Data Structures and Algorithms

Winter 2002

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 1

Version 1.1 of January 4

Data Structures Online

Due date and time: Friday, January 18, 2002, (Part A at 6:00 PM, Part B in class).

Turn in Part A of this assignment by filling in the A1 online submission form. Turn in Part B (written on paper) in class.

Title: Data Structures Online.

Purposes: Practice and demonstrate your ability to use online resources and perform research-style academic study. Practice creating and publishing web pages, so that we will be able to easily share our Java applets later in the quarter. Brush up on set theory. Learn to apply it to data structures. Become familiar with the expectations on students for the course.

Part A

Each of you will be given, in class, a question to answer. You may trade questions with another student, but each student will be expected to turn in a unique answer to a unique question. (Some questions may be somewhat more difficult than others. Do the best you can with your topic.) Write your answer on a web page, under your computer account on Dante, one of the UW web servers. (If you are not familiar with how to post web pages, we will be going over this during the optional session on January 14 at 4:30.) Here is a sample solution; use it as a template for your own page, keeping the same color scheme for each of its parts. Then submit your assignment by filling out and submitting the online submittal form. Note: if you don't already have one, you will need to get a UWNetID for this.

Part B

Do the following problems on paper and hand them in at class on Friday, Jan 18.

1. Let S1 = {a, b}, S2 = {c, d, e}, S3 = {0, 1}
a. Write out the elements of (S1 U S2) X S3
b. Write out the elements of S1 X S3 X S3
c. Write out the elements of S1 X (S3 X S3)
2. Let f be a function consisting of the following ordered pairs: { (0, a), (1, a), (2, b), (3, c), (5, e)}
a. What is the domain of f?
b. What is the range of f?
c. Is f a surjection? (Is every element of the range used?)
d. Is f an injection? (No range element is used more than once).
e. Is f a one-to-one correpondence?
f. Let f' be the set of ordered pairs obtained from those in f by reversing their order. Is f' a function?
3. Let us define a "mid-list" to be a data structure that contains a list, but whose elements are always inserted and removed in the middle. If there are n elements in the list and we remove an element, it's the element in position floor(n/2) that gets removed. If we insert an element, the element is added right before the element in position floor(n/2), if any. Assume that our mid-list holds elements of type Integer.
a. Give a formal description of the MID-INSERT operator for a mid-list.
b. Give a formal description of the MID-REMOVE operator for a mid-list.
For each operator, consider it to be a function. Give the domain and range of the function. Then describe how it maps a domain element into a corresponding range element using a symbolic notation.

Individual Work: This assignment requires individual work. Do NOT work in teams on this assignment..