CS 3240 Data Structures Fall 2004 written homework #1

Section: Yang

due: October 4, 1:20pm sharp

1. Using big O notation, discuss the time complexity of a single car wash washing n cars. Now consider what the answer should be if there are 2 car washes. Each car still only needs to be washed once. Explain why your answer changes or stays the same.
2. Consider the "space" complexity of "speed dating". For this exercise, assume that one session of speed dating involves n men and n women. Each person gets to spend C minutes with each of the people of the opposite gender. Each couple gets a table for two so that it feels a little more like a real date.
   • Give your answer if we define "space" as the number of tables needed for one session. Briefly explain.
   • Suppose now that each person fills out a form if they would like to meet one of the other people again. Give your answer if we define "space" as the number of forms that are submitted. Briefly explain.
3. Define a lamp as an abstract data type -- list both the attributes and the operations. No code is needed for either this or the next question.
4. Define a fraction as an abstract data type -- list both the attributes and the operations.