22C:30, 22C:115 Homework 1

Due date: Friday, 9/13

Problem 1
I started with a correctly running C++ program and messed it up by making 4 minor edits. Now the program does not even compile. You have two tasks:

My edits are minor enough that the logic of the program is essentially unchanged. Your solution to this problem should contain the "fixed up" program with your changes clearly identified, followed by a one sentence description of what the program does.

Problem 2
This problem will give you experience using classes in C++. You will need to use the RandGen and the SmallList classes posted on the course page, for this problem.

  1. Add a member function to the SmallList class called makeRandomList that takes as argument a positive integer n, and places in the SmallList object a list of n randomly generated numbers in the range 1 through n. makeRandomList will have to call member functions of the RandGen appropriately to do this. Having the function makeRandomList gives us a way of putting elements into a SmallList object randomly, without having to read elements from the input.
  2. Write a C++ function called CountDistinct that takes as an argument a positive integer n, generates a list of n randomly chosen integers in the range 1 through n, removes duplicates from this list, and finally returns the number of distinct elements remaining in the list. Given that the SmallList class now contains methods to do all of this, CountDistinct should simply call these methods to produce the answer.
  3. Use the CountDistinct function written above as a starting point for an experiment to estimate the number of distinct elements in a randomly generated list of n numbers, where the numbers are in the range 1 through n. To perform this experiment start with n = 100, call CountDistinct 10 times, and compute the average length of the list of distinct elements. The average here is computed over the 10 calls to CountDistinct. Repeat this experiment for n = 100, 200, 300, ..., 1000 and plot the averages. Based on the plot, what can you say about fraction of elements in the list that are distinct? How does this vary with n?
What to submit as solution to this problem: (a) code for makeRandomList (b) code for CountDistinct (c) the plot of lengths of lists and (d) a few intelligent sentences about the plot.

Problem 3
I have placed a class called SysTimer on the course page that you can use to measure the running time of pieces of your code. This is a very handy class for understanding the performance of your program. This problem asks you to measure the time it takes to remove duplicates from a list. Specifically, I want you to time the removeDuplicates function in the SmallList class. Start with n = 1000 and use the makeRandomList method to create a SmallList object with n randomly chosen numbers in the range 1 through n. Then call removeDuplicates, measuring the amount of time it takes. Repeat this for n = 1000, 2000, ..., 10000 and plot the times. What sort of function do you see in the plot? Is it, roughly speaking, a straight line?

What to submit as solution to this problem: (a) program that you used to time removeDuplicates, (b) the plot of the times and (c) a few intelligent sentences about the plot.

Problem 4
Here is the header file for a rational class. Write the implementation of this class.