Tölvunarfræði 2

Weekly note 10

In the sections this week we will cover the last homework.

Problem set 9

1. Assume a singly linked list, where each node contains an integer. You are to write a recursive function in C++ to calculate the sum of squares, i.e. (a₁)² + (a₂)² + ... + (a_n)², where a_i is the integer in node i in the linked list.
   1. Consider the functions below and explain why they do not solve this problem. Describe what is wrong in each instance and say what would happen if the functions were to be executed.

      i)
      	int sumKvrt( node *h )
      	{
      		if( h != NULL )
      			return ( sumKvrt( h->next ) * sumKvrt( h->next ) );
      	}
      
      ii)
      	int sumKvrt( node *h )
      	{
      		if( h == NULL )
      			return 0;
      		return ( h->item * sumKvrt( h->next ) );
      	}
      
      iii)
      	int sumKvrt( node *h )
      	{
      		return 0;
      		if( h->next != NULL )
      			return ( h->item * h->item ) + sumKvrt( h->next );
      	}
      

   2. Write a correct recursive version of this function and explain how your function calculates the sum of squares of the linked list.

2. Is selection sort, as it is written on page 273 in the textbook, stable? If it is stable justify that conclusion in a convinsing way. If it is not stable, show a counter-example and determine if the code can be changed so that it is stable.

3. [Makeup exam 2001] What is the maximum number of times that the largest element is moved between location in the array in insertion sort, if you assume Program 6.3 on page 276 in the textbook?

4. In reality it seems more common that frequency of values is distributed according to Zipf's law than evenly distributed in a particular range. Values is distributed according to Zipf's law if the most common value occurs c times, the second most common item occurs c/2 times, the third most common one c/3 times, and in general that the i-th most common value occurs c/i times. This does of course not hold exactly in most cases, but for instance the frequency distribution of words in books often resembles Zipf's law. The same applies to the popularity of Web pages and various other things.
   You are to write a function that creates a random array of integers according to certain parameters on the frequency of the most common item (c) and the total number of values (n). The function has the header:

       void slembiZipf( int c, int n, int a[] )
    

   Assume that the array a has already been defined is is of size at least n. Note that it is best to start by putting the values into the array in order by their frequency (have the value 1 be the most common one, 2 be the second common one, etc.) and shuffle the array. Shuffling rearranges the items of the array such that all permutations are equally likely. The way shuffling works is that if we have an array a with 100 items then we first look at the item in a[99], pick a random number r between 0 and 99, and swap the items in a[99] and a[r] (note that r could be 99). Then we pick a random number r between 0 and 98, and swap a[98] and a[r]. This is done until we reach 0.
   Compare the speed of insertion sort on evenly distributed array of random numbers and another one whose frequency distribution is according to Zipf's law.

5. Exercise 6.35 on page 292 in the textbook.