CSC 122: Computer Science II, Spring 2006

Recurrence, Haskell, and Linked List Sample Questions

Solve the following recurrence relations:

```
T( 1 ) = 0
T( n ) = T( n-1 ) + 2
			
```
```
T( 1 ) = 1
T( n ) = T( n/2 ) + 1
			
```
```
T( 1 ) = 4
T( n ) = 2T( n/2 ) + n
			
```
```
T( 2 ) = 5
T( n ) = T( n-1 ) + n
			
```
```
T( 1 ) = 1
T( n ) = 2T( n – 1 )
			
```

T( 0 ) = 1
T( 1 ) = 1
T( n ) = T( n – 2 ) + 1

Write the recurrence relation for the running time of this method. You do not need to solve it, just write the relation. Assume that a multiplication is the critical step.
```
public void function( int n ) {
  if ( n == 1 )
    return 1;
  return function( n – 1 ) * 5;
}
				
```
Write the recurrence relation for the running time of this method. You do not need to solve it, just write the relation. Assume that an addition is the critical step.
```
public void test( int n ) {
  if ( n == 1 )
    return 1;
  if ( n == 2 )
    return 2;
  return test( n – 1 ) + test( n – 2 );
}
				
```

Write the recurrence relation for the running time of this method. Assume that otherFunction prints a number of lines equal to its input plus 3. You do not need to solve it, just write the relation. Assume that printing a line of output is the critical step.

public void mystery( int n ) {
  if ( n == 0 )
    System.out.println( "Done at last" );
  else {
    System.out.println( "Recursing..." );
    mystery( n – 1 );
    System.out.println( "Calling other function." );
    otherFunction( n );
    System.out.println( "Done with " + n );
  }
}

Write a Haskell function decrement that takes one parameter, a list of numbers. The function should return a list of numbers so that each element is one smaller than the corresponding element in the original list. For example, decrement( [2, 3, 4] ) should return [1, 2, 3].
Write a Haskell function multiplyAll that takes one parameter, a list of numbers. The function should return the product of all the numbers in the list. If the list is empty, return 1. For example, multiplyAll( [2, 4, 1, 10] ) should return 80.
Write a Haskell function called removeGreaterThan that takes two parameters, a list of numbers and a number. The function should return a list that would result from removing all numbers from the list that are greater than the number given. For example, removeGreaterThan( [6, 3, 8, 2, 1, 9], 5 ) should return the list [3, 2, 1].
Write a Haskell function called count that takes two parameters (a list and an item). The function should return the number of times that the given item occurs in the list. For example, count( [1, 3, 2, 3], 3 ) should return 2.
Write a Haskell function called findSmallest that takes one parameter (a list of numbers). The function should return the value of the smallest item in the list. For example, findSmallest( [1, 3, 19, 4, 12] ) should return 1.
Write a Haskell function called remove that takes two parameters (a list and an item). The function should return a list that would result from removing the first copy of item from the list (all other copies of item should remain). If item is not in the list, return the list unchanged. For example, remove( [2, 4, 6, 4, 8, 10], 4 ) should return [2, 6, 4, 8, 10].
Write a Haskell function called insert that takes two parameters (a list and a number). You may assume that the list consists of 0 or more numbers that are in order. The function should return a list that would result from inserting the number into the list into the appropriate place to keep the list in order. For example, insert( [2, 4, 6, 8], 5 ) should return [2, 4, 5, 6, 8].
Write a Haskell function called selectSort that takes one parameter (a list of numbers). The function should return the list that would result from sorting the list using selection sort. Note: the findSmallest and remove functions should be useful here.
Write a Haskell function called insertSort that takes one parameter (a list of numbers). The function should return the list that would result from sorting the list using insertion sort. Note: the insert function should be useful here, as would an auxiliary function.

Show the stack that would result from the following list of stack commands:

Stack s = new Stack( );
s.push( 5 );
s.push( 9 );
s.push( 14 );
s.pop( );
s.push( 18 );
s.push( 3 );
s.pop( );
s.push( 4 );

Show the queue that would result from the following list of queue commands:

Queue q = new Queue( );
q.enqueue( 'G' );
q.enqueue( 'R' );
q.enqueue( 'H' );
q.enqueue( 'O' );
q.dequeue( );
q.enqueue( 'M' );
q.enqueue( 'E' );
q.dequeue( );
q.enqueue( 'R' );

Write code that fills a Queue with the numbers from 1 to 20 in that order.
Implement a Stack class, using the built-in LinkedList class. Your stack class should contain a constructor and methods named push, pop, and top that work in the obvious way.
Write a method that takes a LinkedList of numbers and returns the sum of the numbers in the list.
Write a method that takes a LinkedList of numbers and returns the smallest of the numbers.
Write a method that takes one integer parameter n and creates a LinkedList containing the numbers from 1 to n in order.
Write a method that sorts a LinkedList of numbers.
Write a method that takes one LinkedList as a parameter. The method should remove all the even numbers from the LinkedList that is passed as a parameter, and return another LinkedList containing all those even numbers in their original order. For example, if we passed the method a LinkedList containing the numbers [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], the original list should be changed to be [1, 3, 5, 7, 9] and the method should return a LinkedList containing [2, 4, 6, 8, 10].
Write a method that takes two LinkedLists, and returns a LinkedList made by interleaving the two lists. For example, if we pass it the lists [1, 6, 4, 9] and [12, 3, 7, 15], it should return [1, 12, 6, 3, 4, 7, 9, 15].

Complete the implementation of this very simple linked list class by writing code for the addFirst, getFirst, and removeFirst methods:

public class LinkedList {
  private class Node {
    public Object data;
    public Node next;
  }

  private Node first;

  public LinkedList( ) {
    first = null;
  }

  public void addFirst( Object obj ) {
  
  }

  public Object getFirst( ) {
  }

  public Object removeFirst( ) {
  }
}

Overview

Schedule

Resources

Assignments

Home

DePauw University, Computer Science Department, Spring 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated