AP CS Assignments
Assignments by week:
Fall Term:
Winter Term:
Spring Term:
Monday, September 24
Description
Loops
Homework
  • Read all of chapter 8 (pages 123-133) in Think Java.
  • Read all of chapter 9 (pages 139-148) in Think Java.
Tuesday, September 25
Description
Arrays and Strings
Homework
  • Write a class that contains the following method:

    public static void recursive(int i) { System.out.println("Iteration " + i); recursive(i+1); }

    Describe (in general terms) the output of the program. Why does this result?

  • Write a method countDown(int n) that counts down from the value n (passed as a parameter) to 1 without using loops (e.g., you must use recursion!).

Thursday, September 27
Description
Recursion
Homework
  • Write a recursive method String reverse(String s) that returns the reverse of the given String (you may assume it is non-null). Extra credit: modify your code to require at most n/2 recursive calls for a string of length n.
  • Write a recursive method int pow(int b, int e) that takes a given base b and raises it to the power e (you may assume both are non-negative). How efficient is your solution? Can you make it more efficient?
Friday, September 28
Description
More Recursion
Homework
  • Consider the following XKCD comic:

    Complete the NPCompleteAppetizers class to generate a solution to the problem posed in the comic.

  • If you're interested in learning more about NP-complete, this video gives a good overview:
  • In a new program, write a recursive method void anagram(String s) that takes a string of characters and prints all possible orderings of those characters to System.out (nothing is returned from the method). For example, if the input string was "APCS", the method would print:
    APCS APSC ACPS ACSP ASCP ASPC PACS PASC PCAS PCSA PSAC PSCA CAPS CASP CPAS CPSA CSAP CSPA SACP SAPC SPAC SPCA SCAP SCPA
    Your ordering doesn't need to match mine; it just needs to print all possible orderings. If your input strings contain duplicate letters, the result will contain duplicate listings (each letter is considered unique). Hint: you will want to write a second method with additional parameters that does the recursive work, and then call that method from the primary method. Though you should use recursion for your solution, you may use loops in combination with recursion to try all the possible combinations.