CSC148/A48 — Exercises

Week 12 Exercise

Solution

Do the Tree part of Assignment 4.

Week 10 Exercise

Solution

Complete isIncreasing by completing helper method m recursively and calling it from isIncreasing. What exactly m accomplishes is up to you. The boundary cases of no integers or one integer are both considered increasing, and we have helped you by handling one of those cases in the best place to do so. Do not use any loops, nor add any code outside the two methods. You do not need to throw an exception if the precondition is violated. You do not need to javadoc your helper method (but as a hint: its header comment would be quite similar to the one for isIncreasing).

  import java.util.Iterator;

  class E10 {

    /**
      Return whether the Integers from it are in increasing order.
      Precondition: it != null and none of its elements are null.
     */
    public static boolean isIncreasing(Iterator<Integer> it) {
      if (!it.hasNext()) {
        return true;
      } else {
        // Fill this in, using m as a helper.
      }
    }

    private static boolean m(Integer i, Iterator<Integer> it) {
      // Fill this in recursively.
    }

  }

Week 9 Exercise

Solution

Purpose

Implement a simple Iterator, use generics a bit more, and begin to use exceptions.

Some Highlights from the Bulletin Board

There's been a lively discussion. Here are some significant posts:

The concepts involved. The following is the core of what you want to accomplish:

  Iterator<Integer> it = new RangeIterator(3, 7);
  System.out.println(it.next()); // prints 3
  System.out.println(it.next()); // prints 4

The A48/148 bit: you are using the generic interface Iterator<> by putting in the type Integer to get a non-generic interface Iterator<Integer> that you use to write a non-generic class RangeIterator. Short summary:

class RangeIterator implements Iterator<Integer> { ... }

Now write the "..." bit: next() and hasNext(). No lists, arrays, iterators or generics are needed in the "...". Oh, there are exceptions you have to throw, and a class you have to make with nothing in it!

But be careful not to make too many assumptions about the order of users calling next() and hasNext().

Errors students have encountered

"AmbiguousMethodException": the Interactions Pane isn't real Java.

"Incompatible types": don't define your own Iterator interface: import Java's.

"Type parameter": don't make RangeIterator generic, i.e. don't declare it as RangeIterator<...>.

The Exercise

Look up the Iterator interface in the Java API.

Write a class RangeIterator implementing Iterator<Integer>, to return a sequence of Integers.

Include the following constructor:

    /** An Iterator producing Integers with values in [start, end) in order: start, start+1, start+2, ..., end-1.
        Precondition: start <= end.
        @param start  value of the first Integer to produce
        @param end    one more than the value of the last Integer to produce */
    public RangeIterator(int start, int end)

For the method remove() simply use the body:

        throw new UnsupportedOperationException();

For the method next(), if there are no more Integers to return then do:

        throw new NoSuchElementException();

Also, make a class BadRangeException extending RuntimeException from the java API. Don't add any code to your class (simply allow Java to provide a default constructor and don't override any of the methods from RuntimeException). If the constructor precondition is violated, throw an instance of BadRangeException.

Note: the Iterator specification doesn't require the user to call hasNext() between calls to next(). And they may call hasNext() more than once between calls to next(). Play around with an ArrayList iterator to check your understanding of iterators.

Marking

Marking will be by automark of correctness, so be sure to test your code. Commenting is not required, nor will style be marked.

Week 6 Exercise

Solutions.

Submission Instructions

Submit classes E1, E2, E3, E4.

UTSC

Submit with command: submit -N week6 csca48s E1.java E2.java E3.java E4.java.

StG

Submit through CDF.

UTM

Submit through the UTM Submit System.

Question 1

Let s(n) be the sum of 1^2, 2^2, ... up to and including n^2.

1. [0 marks: do not hand in] Give two (very similar) recursive definition of s(n), one that relates s(n) and s(n+1), and another that relates s(n) and s(n-1). One of these will be more directly usable in the next part.
2. [1 mark] Write method s below recursively, according to one of your definitions above.

    class E1 {

      /** Return the sum of the squares from 1 to n.
          Requires: n >= 1. */
      public static int s(int n) {

      }

    }

Question 2

Let s(k,n) be the sum of the squares k^2, (k+1)^2, ... up to and including n^2.

1. [0 marks] s(5,10) is a sum of six terms: 5^2 + 6^2 + ... + 10^2.

   Fill in the blanks: s(5,10) = s(__, __) + __^2.

   Fill in the blanks again, differently.

2. [0 marks] Give two significantly different recursive definitions of s(k,n): one recursive in k (i.e. relates different k's, doesn't change n), and the other recursive in n.
3. [2 marks] Write methods sk and sn below recursively, according to your definitions in the above.

    class E2 {

      /** Return the sum of the squares from k to n.
          Requires: k <= n. */
      public static int sk(int k, int n) {
        // The recursive call must be of the form sk(__, n)
      }

      /** Return the sum of the squares from k to n.
          Requires: k <= n. */
      public static int sn(int k, int n) {
        // The recursive call must be of the form sn(k, __)
      }

    }

Question 3

[2 marks] Complete s by filling in the arguments in its call to sHelper. Complete sHelper recursively, by recursing on sumSoFar and next together.

  class E3 {

    /** Return the sum of the squares from 1 to n.
        Requires: n >= 1. */
    public static int s(int n) {
      return sHelper(__, __, __);
    }

    /** Return sumSoFar + next^2 + (next+1)^2 + ... + n^2.
        Requires: 1 <= next <= n. */
    public static int sHelper(int sumSoFar, int next, int n) {
        // The recursive call must be of the form sHelper(__, __, n)
    }

  }

Question 4

[2 marks] Complete s by filling in the arguments in its call to sHelper. Complete sHelper recursively.

    class E4 {

      /** Return the sum of the squares from 1 to n.
          Requires: n >= 1. */
      public static int s(int n) {
        return sHelper(__, __);
      }

      /** Return 1^2 + 2^2 + ... + next^2 + sumSoFar.
          Requires: 1 <= next. */
      public static int sHelper(int sumSoFar, int next) {

      }

    }

Week 5 Exercise

Solutions.

A tester.

Submission Instructions

Submit only class E.

UTSC

Submit with command: submit -N week5 csca48s E.java.

StG

Submit through CDF.

UTM

Submit through the UTM Submit System.

The Exercise

This exercise is about simple first-rest recursion on a sequence of items: Strings as a sequence of characters, and Lists as a sequence of elements. Complete each method by replacing the comments that say "FILL THIS IN".

import java.util.*;

public class E {


  /** Return the number of characters in s. */
  public static int length(String s) {
    if (s.equals("")) {
      // FILL THIS IN.
    } else {
      char first = s.charAt(0);
      int lengthOfRest = length(s.substring(1));
      // FILL THIS IN.
      // The only variables you may mention are first and lengthOfRest.
    }
  }

  /** Return the number of elements in l. */
  public static <T> int length(List<T> l) {
    if (l.isEmpty()) {
      // FILL THIS IN.
    } else {
      T first = l.get(0);
      int lengthOfRest = length(l.subList(1, l.size()));
      // FILL THIS IN.
      // The only variables you may mention are first and lengthOfRest.
    }
  }


  /** Return whether s contains c. */
  public static boolean contains(String s, char c) {
    if (s.equals("")) {
      // FILL THIS IN.
    } else {
      char first = s.charAt(0);
      boolean containsOfRest = contains(s.substring(1), c);
      // FILL THIS IN.
      // The only variables you may mention are first, containsOfRest and c.
    }
  }

  /** Return whether l contains t. */
  public static <T> boolean contains(List<T> l, T t) {
    if (l.isEmpty()) {
      // FILL THIS IN.
    } else {
      T first = l.get(0);
      boolean containsOfRest = contains(l.subList(1, l.size()), t);
      // FILL THIS IN.
      // The only variables you may mention are first, containsOfRest and t.
    }
  }


  /** Return a copy of s. */
  public static String copy(String s) {
    if (s.length() == 0) {
      // FILL THIS IN.
    } else {
      char first = s.charAt(0);
      String copyOfRest = copy(s.substring(1));
      // FILL THIS IN.
      // The only variables you may mention are first and copyOfRest.
    }
  }

  /** Return a LinkedList with all the elements of l, in the same order. */
  public static <T> LinkedList<T> copy(List<T> l) {
    if (l.isEmpty()) {
      // FILL THIS IN.
    } else {
      T first = l.get(0);
      LinkedList<T> copyOfRest = copy(l.subList(1, l.size()));
      // FILL THIS IN.
      // The only variables you may mention are first and copyOfRest.
    }
  }


  /** Return a copy of s but with the characters in reverse order. */
  public static String reverseCopy(String s) {
    if (s.length() == 0) {
      // FILL THIS IN.
    } else {
      char first = s.charAt(0);
      String reverseCopyOfRest = reverseCopy(s.substring(1));
      // FILL THIS IN.
      // The only variables you may mention are first and reverseCopyOfRest.
    }
  }

  /** Return a LinkedList with all the elements of l, but in reverse order. */
  public static <T> LinkedList<T> reverseCopy(List<T> l) {
    if (l.isEmpty()) {
      // FILL THIS IN.
    } else {
      T first = l.get(0);
      LinkedList<T> reverseCopyOfRest = reverseCopy(l.subList(1, l.size()));
      // FILL THIS IN.
      // The only variables you may mention are first and reverseCopyOfRest.
    }
  }

}

Week 4 Exercise

Solutions.

A tester.

Submission Instructions

Submit only class E. Do not include the Stack and Queue interfaces, nor the StackImp and QueueImp classes. You must of course have compiled and tested your code: non-working code will likely get a zero.

UTSC

Submit with command: submit -N week4 csca48s.

StG

Submit through CDF.

UTM

Submit through the UTM Submit System.

The Exercise

Consider the following interfaces and classes implementing them:

interface Stack<T> {
    void push(T o);
    T pop();
    int size();
}

interface Queue<T> {
    void enqueue(T o);
    T dequeue();
    int size();
}

class StackImp<T> implements Stack<T> {
    public StackImp(int capacity) { /* Implementation not shown */ }
    /* Rest of class not shown. */
}

class QueueImp<T> implements Queue<T> {
    public QueueImp(int capacity) { /* Implementation not shown */ }
    /* Rest of class not shown. */
}

Complete the two methods in class E below. Do not add any other code. The only objects you may create are instances of classes QueueImp and StackImp.

public class E {

    /** Reverse the order of the ith through jth elements of s,
        where the numbering starts from 0 at the top.
        Requires: 0 <= i <= j < s.size().
        @param i  first index of the elements to reverse
        @param j  last index of the elements to reverse */
    public static <T> void reverse(Stack<T> s, int i, int j) {


    }

    /** Reverse the order of the ith through jth elements of q,
        where the numbering starts from 0 at the front.
        Requires: 0 <= i <= j < q.size().
        @param i  first index of the elements to reverse
        @param j  last index of the elements to reverse */
    public static <T> void reverse(Queue<T> q, int i, int j) {

    }

}

Week 3 Exercise

Was delayed. We're now considering it part of Assignment 0, due this Thursday.