Homework 7

I will talk in class about MergeSort and QuickSort, and go into detail about using Quicksort for arrays. But as usual, we also want to consider linked lists. This homework is a merge sort with linked lists. The base case, as usual, is a list of length 0 or 1; just return the input. For the recursive case, the first problem is to divide the input list into two halves. It doesn't matter which numbers go in which half, as long as they are roughly equal. So let us put element number 1,3,5... in one half, and number 2,4,6... in the other. For this you need two recursive methods. They are

public static intlist odd_members(intlist L)
    if L is null return null
    else return a new list with first member: L.first
                                remaining members: even_members(L.rest)
public static intlist even_members(intlist L)
    if L is null return null
    else return odd_members(L.rest)

Do you see how this works? We'll talk about it in class. Now the function calls itself to sort the two halves. Finally, put the halves together, with a method like this:

public static intlist merge(intlist K, intlist L)
if K is empty
   return L
if L is empty 
   return K;
if(L.first < K.first)
   return a new list with first member: L.first
                          rest: merge(L.rest,K)
  return a new list with first member: K.first
                         rest: merge(L,K.rest)

And there is your answer. As usual, prompt the user and read a list of positive numbers terminated by -1. Put them in a list (we talked about this), sort the list, print the result.
Possible Solution:
Compile two files in the same folder:
                             javac list.java
                            javac homework7.java
Then run:    java homework7

 1/ list.java

class list
{
     public int first;
     public list rest;
   
     public list(int x, list y)
    {
        first = x;
        rest = y;
    }
}

2/ homework7.java

import java.util.Scanner;

public class homework7
{

   public static void main(String[] args)
  {
       int n = 0;
       list l = null, odd_list = null, even_list = null, merge_list = null;

      Scanner scanner = new Scanner (System.in);

      while (n != -1)
     {
          System.out.println("enter a number: ");
         n = scanner.nextInt();
         if (n!= -1)
          l = insert(n, l);
     }
      odd_list = odd(l);
      even_list = even(l);
      merge_list = merge(odd_list, even_list);

     show_list(merge_list);
     System.out.println();

    }

  static list odd(list y)
 {
   if (y == null)
     return null;
   else
     return new list(y.first, even(y.rest));
 }

 static list even(list y)
 {
   if (y == null)
     return null;
   else
     return odd(y.rest);
 }

 static list insert(int x, list y)
 {
   list current = y;
 
   if (y == null)
     return new list(x, y);
   else
   {
     while (current.rest != null)
       current = current.rest;
     current.rest = new list(x, null);
     return y;
   }
 }

 static list merge(list x, list y)
{
  if (x == null)
    return y;
  else if (y == null)
    return x;
  else
  {
    if (x.first < y.first)
      return new list(x.first, merge(x.rest, y));
    else
      return new list(y.first, merge(x, y.rest));
  }
}


 static void show_list(list y)
 {
  if(y != null)
  {
   System.out.print(y.first + " ");
   show_list(y.rest);
  }
 }

}

Homework 6

Write a method that takes two linked lists L1 and L2, both in order, and returns a list, also in order, containing all the numbers in L1 and L2. If one lists is empty, the other list is the answer. If both lists are non-empty, compare L1.item and L2.item. If L1.item is smaller, it is the smallest number of all, and it becomes the first number in the answer list. To find the tail of the answer, recursively combine the tail of L1 with L2. If L2.item is smaller, use the same idea with l1 and l2 changing places. You must use the same IntList class that I have used in the lectures. Sample behavior:

list of integers: 1 3 5
list of integers: 2 4 6
answer: 1 2 3 4 5 6

Possible Solution:
Compile two files in the same folder:
                             javac list.java
                            javac homework6.java
Then run:    java homework6

 1/ list.java

class list
{
     public int first;
     public list rest;
   
     public list(int x, list y)
    {
        first = x;
        rest = y;
    }
}

2/ homework6.java

public class homework6
{

 public static void main(String[] args)
 {
   list L1 = new list(1, new list(3, new list(5, null)));
   list L2 = new list(2, new list(4, new list(6, null)));
   list L = merge(L1, L2);
 
   System.out.print("list of integers: ");
   show_list(L1);
   System.out.println();
   System.out.print("list of integers: ");
   show_list(L2);
   System.out.println();
   System.out.print("answer: ");
   show_list(L);
   System.out.println();
 }

static list merge(list x, list y)
{
  if (x == null)
    return y;
  else if (y == null)
    return x;
  else
  {
    if (x.first < y.first)
      return new list(x.first, merge(x.rest, y));
    else
      return new list(y.first, merge(x, y.rest));
  }
}
 

 static void show_list(list y)
 {
  if(y != null)
  {
   System.out.print(y.first + " ");
   show_list(y.rest);
  }
 }
}

Homework 5

Write a recursive method called "occur" that takes two arguments: a linked list of integers L and an integer N. It should return the Boolean true if N occurs in the list L, otherwise false. If L is null the answer must be false. If not, compare N to L.item. If they are equal, the answer is yes. If not, find the answer by calling the same function on the tail of L. Your main method should create a list L with members 1,2,3,4,5 and call the "occur" method twice: once to check if 4 occurs in the list L, and once to check if 9 occurs. Print both results. 
Possible Solution:

Compile two files in the same folder:
                             javac list.java
                            javac homework5.java
Then run:    java homework5

 1/ list.java

class list
{
     public int first;
     public list rest;
   
     public list(int x, list y)
    {
        first = x;
        rest = y;
    }
}

2/ homework5.java

public class homework5
{

 public static void main(String[] args)
 {

   boolean ans;
   int N;
   list L = new list(1, new list(2, new list(3, new list(4, new list(5, null)))));
 
  N = 4;
  ans = occur(L, N);
  if (ans == true)
    System.out.println(N + " is in the list");
  else
    System.out.println(N + " is not in the list");
 
  N = 9;
  ans = occur(L, N);
  if (ans == true)
    System.out.println(N + " is in the list");
  else
    System.out.println(N + " is not in the list");
 
 }

 static boolean occur(list L, int N)
 {
  if (L == null)
    return false;
  else
  {
    if (L.first == N)
      return true;
    else
      return occur(L.rest, N);
  }
 }
 

}

Homework 4

Write a function called "odd" that takes a linked list and returns the odd-numbered elements. Actually, write two functions called "odd" and "even". odd(L) returns a list of the 1st,3rd,5th... items in L. even(L) returns a list of the 2nd,4th,6th... items in L. And each function calls the other. These two functions are based on a simple observation. L.next is like L, but with the first item missing. If we take away the first item, item N+1 becomes item N. So the 2nd,3rd,4th elements of L are the 1st,2nd,3rd elements of L.next. Now if N+1 is odd, N is even, while if N+1 is even N is odd. So the odd members of L.next are even members of L, and the even members of L.next are odd members of L. Then we can compute odd(L) as follows. If L is null return null. Otherwise return a list whose first item is L.item, while its tail is even(L.next). To compute even(L): If L is null return null. Otherwise return odd(L.next). Your main function should read a list of positive integers from the command line, with -1 terminating the list. It should form a linked list containing these integers, compute the list of odd members, and print them.

Possible Solution:

Compile two files in the same folder:
                             javac list.java
                            javac homework4.java
Then run:    java homework4

 1/ list.java

class list
{
     public int first;
     public list rest;
   
     public list(int x, list y)
    {
        first = x;
        rest = y;
    }
}

2/ homework4.java

import java.util.Scanner;

public class homework4
{

   public static void main(String[] args)
  {
       int n = 0;
       list l = null, new_list = null;

      // Create a scanner to read from keyboard
      Scanner scanner = new Scanner (System.in);
 
      while (n != -1)
     {  
          System.out.println("enter a number: ");
         n = scanner.nextInt();
         if (n!= -1)
          l = insert(n, l);
     }
      new_list = odd(l);

     show_list(new_list);
     System.out.println();
 
    }

  static list odd(list y)
 {
   if (y == null)
     return null;
   else
     return new list(y.first, even(y.rest));
 }

 static list even(list y)
 {
   if (y == null)
     return null;
   else
     return odd(y.rest);
 }

 static list insert(int x, list y)
 {
   list current = y;
  
   if (y == null)
     return new list(x, y);
   else
   {
     while (current.rest != null)
       current = current.rest;
     current.rest = new list(x, null);
     return y;
   }
 }

 static void show_list(list y)
 {
  if(y != null)
  {
   System.out.print(y.first + " ");
   show_list(y.rest);
  }
 } 

}

Homework 3

Do homework 1 over, but with recursion instead of a loop. First write the function

static void printrow(int i,int j)

This function prints the characters of the i-th row, starting at column j. If j is 8, we have printed all the characters already. Just print a newline and quit. If j < 8, print one characters. Use the numbers i and j to decide between 0 and X, just as before. Then the function calls itself. The first argument stays the same, but the second argument goes up by one -- because we are moving to the next column. Now write the function

static void printall(int i)

This function prints the rows from row i to the end. If i=8 we are done -- do nothing. If i < 8, use the function printrow to print the i-th row (start at column 0). Then call printall again, with the row number increased by one. Your main function just calls printall(0).

Possible Solution:

public class board
{

    public static void main(String[] args)
    {
        printall(0);
    }
  
    static void printrow(int i,int j)
     {
        if (j == 8)
            System.out.println();
       else
       {
            if(i % 2 == 1 || j % 2 == 1)
                System.out.print('X');
            else
                System.out.print('O');  
                       
            printrow(i, ++j);
          }
    }

    static void printall(int i)
    {
        if (i == 8)
            System.out.println("Done");
       else
       {
           printrow(i, 0);        
           printall(++i);
       }
    }  
  
}

Homework 2

Write a recursive function that takes a floating point number A and an integer N, and returns A to the N-th power. Your program should prompt the user for the values of A and N, in that order, then print the result. Like this:

enter real number: 5.0
enter exponent: 3
answer: 125.0

Solution: 

import java.util.Scanner; 

class Power
{
  public static void main ( String[] args )
  {
   float A, R;
   int N;
   
   // Create a scanner to read from keyboard
   Scanner scanner = new Scanner (System.in);
   
   System.out.println("enter real number: ");
   A = scanner.nextFloat();
   System.out.println("enter exponent: ");
   N = scanner.nextInt();
   R = pow(A, N);
   System.out.println("answer: " + R);  
  }  
  
 static float pow(float a, int n) 
 { 
   // Base Cases: 
   if (n == 0)
  return 1;
   else if (n == 1)
    return a;
   // Recursive Case:  
   else 
  return a * pow(a, n-1);     
 }  
} 

Homework 1

We have already seen how to draw a checkerboard, here is a similar problem. The desired output looks like this:

OXOXOXOX
XXXXXXXX
OXOXOXOX
XXXXXXXX
OXOXOXOX
XXXXXXXX
OXOXOXOX
XXXXXXXX

It is an 8 by 8 board. The odd-numbered rows are X's, and the odd-numbered columns are X's. The other characters are O's.

Solution (just for reference, please write your own code):

class Checkerboard
{
  public static void main ( String[] args )
  {
        int i, k;
        
        for (i = 0; i < 8; i++)        
        {
            if ((i % 2) == 1)
                for (k = 0; k < 8; k++)
                    System.out.print("X");
            else
                for (k = 0; k < 8; k++)
                    if ((k % 2) == 1)
                        System.out.print("X");
                    else
                        System.out.print("O");    
            System.out.println();
        }    
  }
}