View all courses

AP® Computer Science—Semester B

Code this.

Course Length: 18 weeks
Course Type: AP

Schools and Districts: We offer customized programs that won't break the bank. Get a quote.

Description
Syllabus
Sample

This course has been approved by the College Board, which indicates that the syllabus "has demonstrated that it meets or exceeds the curricular expectations colleges and universities have for your subject." Please contact sales@shmoop.com if you would like to add this course to your official record of AP course offerings.

It has also been granted a-g certification, which means it has met the rigorous iNACOL Standards for Quality Online Courses and will now be honored as part of the requirements for admission into the University of California system.

After a semester of 1337 hacking, you might think you know computers—but you do know you know computers? Any time you're sitting in your IDE, coding away your own version of Samantha and you hit a

NullPointerException

, what is there to help you figure out what's going on?

…Besides Java's extensive API. (Let's face it, those explanations are almost as unreadable as the code itself. )

Sure, you could try to hack around the problem, but the more variables and conditionals throw in, the less your code looks like code, and the more it starts to look like spaghetti.

Stick with us and you'll learn everything you'll need to know about making code that's designed instead of just built. By going more thoroughly into

recursion
sorting algorithms
object-oriented programming
software engineering strategies

you'll get your fill of all the ways code should be built. We'll even throw in a slew of programming assignments so that you can go straight from learning about merge and insertion sort to actually programming them on your own—spaghetti stain cleaner not included.

PS: This is a two-semester course and you're looking at Semester B. Trying to find the place where you learn about for loops and methods? Head on over to Semester A.

_{AP® is a trademark registered and/or owned by the College Board, which was not involved in the production of, and does not endorse, this product.}

Unit Breakdown

7 AP® Computer Science—Semester B - The World of Recursion

From factorials to fractals, we'll be diving into the world of recursion, binary trees, and file systems. Stack overflows come free of charge.

8 AP® Computer Science—Semester B - It Takes All Sorts

Sometimes the only thing you can do with an unruly list is sort it. But to sort it, you're going to need to know some of the most popular algorithms, like merge, insertion, selection, and Quicksort. You've got an as-sort-ment of algorithms to pick from (…yeah, we groaned at that one, too).

9 AP® Computer Science—Semester B - Orienting All the Objects

Now that you know so much more about programming than you did before, we're heading back to the land of object-oriented programming, which happens to be Java's home town. Don't worry: we'll stop it before it tries to take you on a tour of its Great Aunt Betsy's favorite Laundromat.

10 AP® Computer Science—Semester B - In Defense of Software Engineering: A Coder's Manifesto

If programming alone wasn't cutting it for you, don't worry: we're talking about working on projects with others in this unit. We'll talk about all the rules of the road for coding together. Except body odor. That's a personal conversation you'll have to have without us.

11 AP® Computer Science—Semester B - Putting the AP in AP CS

Reviewing for the AP Exam's so important that we're giving you an entire unit to do it. Don't worry: we'll guide you through all the material you need to know. Instead of being the scenic route, though, you'll be on the 30-Minutes-or-Less tour. It might be terrible for tours of national museums, but it's great for rehashing CS concepts you're rusty on.

Sample Lesson - Introduction

Lesson 7.03: Identifying the Cases Lab

A baseball player running towards a base.

Baseball players exemplify the fine balance between infinite recursion and an acceptable base case: they'll just keep running if you don't give them a home base to stop on. Seriously, look at that guy.
(Source)

One of the toughest parts of learning recursion is knowing where to get the base and recursive cases. It's like baseball players trying to find home plate. If

the plate wasn't a different shape
players weren't taught the rules of the game

they would just keep running until they…well, ran out of steam (probably).

Or out of innings.

For those who aren't into America's Favorite Pastime, do you remember learning how to read? That's a huge hurdle for most people. We bet you remember when street signs looked like they were in an alien language.

No? Just us?

Regardless of your sports preferences or planetary origins, you probably read without thinking now—going from one word to the next, connecting the sentence as a whole as if it isn't even a thing.

Stop for just a sec and think about what you're actually doing. You identify each letter, and attach it to a sound. You string those sounds together to make words, which each have their own meaning. In the bigger picture, you understand a sentence, this collection of words combining to make a complicated idea. Even further, you piece together a paragraph, a page, even an entire book.

Whoa.

Think about the last book you read. Do you remember the sentences in it? How about the words or letters? With the exception of a really great quote, it isn't likely. Yet somehow, you can tell your friend what happened in your favorite book. Even if you don't read a lot, you can apply all of these same things to the last movie or TV show you watched. Once you understand the underlying process, piecing together the greater whole is a breeze.

Even if a couple of scenes and lines get lost along the way.

Learning to think in a programming language is just like that process. You're learning your letters, your words, and how to make sentences. There are times now where you can step back and make abstract sense out of the groups of sentences you put together. Base cases, recursive cases, and infinite recursion are fundamental to making that abstract thought into something tangible.

Pretty soon, you'll be creating "essay-length paragraphs" in your IDE like a pro.

Sample Lesson - Reading

Reading 7.7.03: Reading the Recursion

You'll do all kinds of reading recursive methods today, Shmooper, but before you do, you need to know more about how to read recursive methods.

Remember that book you had all the way back in Semester A? It was called Introduction to Programming with Java: A Problem Solving Approach, written by John and Raymond Dean, remember? Is it near you? If not, go run and get it.

We'll wait.

Once you've got it, turn to page 477 and read through till you hit Figure 11.4 on 479. It's going to explain a great way of following recursive methods using a trace.

You might remember traces from the unit on loops, and…they're pretty much the same(-ish). Loops and recursion are pretty similar, but the key difference here is that you'll need an entire table to follow something recursive.

Whew.

That's pretty organized, but you'll need to be organized to follow a recursive method. If you label out each call to the method in a column and write in the values of the different variables, it's going to be pretty clear how the numbers change.

Now that we're on the topic of loops, though, go ahead and read through Section 11.4 on pages 480 – 484. It's going to go through all the important components that let you convert between loops and recursion.

Like we said, loops and recursive methods are very similar. Depending on the recursion, you can convert between loops—which overtly iterate through items—and recursive methods—which do the same thing, just implicitly. You'll see what we mean when you read it, though.

Take notes on

how you should set up the table to trace a recursive method.
converting between recursion and loops.

You'll need those skills right…about…

Now.

Sample Lesson - Activity

Activity 7.03: Reverse the Recurse

You've already looked at how to identify base and recursive cases, but let's do a bit of a recap. To keep from infinite recursion (and…um, making sure it runs at all) you need to find

the base case, which ends the recursion. Unlike the recursive case, this is the one that just returns a value up the call stack, promising the end to the method. Sometimes it does something before returning—but never after. If it did, that would be like trying to make a method do something after it's already returned. That just doesn't work. There's always at least one base case. If there wasn't one, the fun wouldn't stop. By fun, we mean nightmarish infinite recursion.
the recursive case, which is the star of the show. This calls the method again, usually with a different value that's closer to your overall goal case (read: base case). Sometimes it performs other actions before or after calling itself again. That's because calling itself can happen anywhere before the recursive case itself returns. We always have at least one recursive case involved in recursion. (Cough, cough: recursive, recursion…don't know, they sound kinda related. Just throwing that out there.)
early-exit cases, which are generally used to catch inputs that could make the method run infinitely—or not at all. Humans write code, after all, so don't be surprised if they put in a -39 when you were expecting a positive number. (Ugh, humans, are we right?) These early-exit cases help you handle things gracefully and return a reasonable value. Sometimes, the recursive and base cases cover all possibilities, so you might not need an early-exit case. It just depends.

Then there's this little thing called infinite recursion (maybe you've heard us mention it once or twice?). When the method calls itself without ever stopping, we're in hot water. That's going to happen any time we don't hit a base case or there's a way that you can't reach the base case. Thankfully, as you know, Java sends you an error message, but because recursion has so little written-out code, it's hard to debug those lines.

Here's a concrete example of infinite recursion: if the base case checks whether the argument is less than a certain value, you don't want the recursive case to start higher than that value and go up. In that case, the method would be stuck in an infinite loop calling the method with larger and larger numbers.

For each of the following code excerpts, tell us in 50 to 100 words (that's a short paragraph),
- what the base case(s) is/are.
- what the recursive case(s) is/are.
- what the method does.
- what the early-exit case(s) is/are, if any, along with why they're included.
- whether or not this method could be turned into a loop, along with some justification to your answer.
When you do this, you'll probably want to start with the base case and work your way through the method by following the recursive step down to said base case. Once you've figured out those mechanics, you should have a pretty good sense of what it does. Then those early-exit cases should be easy to see.
Having a tough time spotting what's happening? Pull out a piece of paper, set up a tracer table, and send some numbers through to see how the method treats them.
1. ```
public static void example1(int n) {
    if (n < 1) {
        return;
    }

    if (n >= 100) {
        return;
    }

    System.out.print(n + " ");
    example1(n * 2);
} 
```
2. ```
public static int bar(int a, int b) {
    if (b == 0) {
        return 0;
    }

    if (b < 0) {
        return a + bar(a, b + 1);
    }

    return a + bar(a, b - 1);
}
```
3. ```
public static int foo(int n) {
    System.out.print(n + " ");

    if (n < -100) {
        return -1;
    }

    if (n > 100) {
        return 1;
    }

    return foo(n * -2);
} 
```
As we've said thousands of times, the most common problem with recursion is when it doesn't stop. As we've also said thousands of times, infinite recursion is also the most common issue.
So let's give you some practice identifying the infinite side of the recursion. For the following recursive methods, identify the infinite recursion and how to stop it.
Consider each code excerpt carefully. For each example, be sure to answer in 50 – 100 words
- which scenario(s) cause(s) infinite recursion with the method.
- what you can add to stop the infinite recursion (please, make it stop).
1. This method counts down from cur by the amount given with jump. There are two problems with this recursive method, so be sure you catch both.
```
public static void countDown(int cur, int jump) {
    if (cur == 0) {
        System.out.println("Liftoff!");
        return;
    }

    System.out.print(cur + "... ");
    countDown(cur - jump, jump);
}
```
2. This method prints the given String backwards, ending at the given index.
```
public static void printBackwards(String str, int i) {
    if (i < 0) {
        return;
    }

    if (i >= str.length()) {
        return;
    }

    char ch = str.charAt(i);
    printBackwards(str, i);
    System.out.print(ch);
}
```
3. This method takes all the elements in toAdd and adds them to list. At the end, it returns the completed list.
```
public static ArrayList addAll(ArrayList list, ArrayList toAdd) {
    list.add(toAdd.get(0));
    toAdd.remove(0);
    return addAll(list, toAdd);
}
```
Sometimes, you'll want to cover every possible case with a different conditional. We're all for being thorough, but sometimes the number of possibilities just gives too many possibilities. (Yep, it is possible to overthink your code. There, we said it.) A lot of the time, recursion only needs one recursive case and one base case, but those cases can sometimes be hard to see.
For each of the following code excerpts, rewrite the method two ways:
1. The recursive method in its simplest form, with as few base and recursive cases as possible that still do the same thing.
2. A loop-based solution that does…the same thing.
1. The following method calculates a^b.
```
public static double power(double a, double b) {
    if (b == -1) {
        System.out.println("Only positive powers allowed.");
        return -1;
    }

    if (b == 0) {
        return 1;
    }

    if (b == 1) {
        return a;
    }

    return a * bar(a, b - 1);
}
```
2. The following calculates the triangle number of n, which is the sum of itself and all numbers smaller than it (positive or negative). For example, the triangle number of 5 is:
  5 + 4 + 3 + 2 + 1 = 15
```
public static int triangleNum(int n) {
    if (n == 0) {
        return 0;
    }
    
    if (n == -1) {
        return -1;
    }

    if (n == 1) {
        return 1;
    }

    if (n < 0) {
        return n + triangleNum(n + 1);
    }

    return n + triangleNum(n - 1);
}
```
3. This method prints a String the given number of times.
```
public static void repeatStr(String str, int count) {
    if (count < 0) {
        return;
    }

    if (count == 0) {
        return;
    }

    System.out.println(str);
    repeatStr(str, count - 1);
}
```

	Fully Correct	Partially Correct
Answer	Written answers are correct and fully formulated. (40)	Written answers are partially correct or only partially formulated. (20)

Course Length: 18 weeks
Course Type: AP