15-100 Lecture 27 (Wednesday, 2004)

Note the main document this is based on can be found at http://www.intro.cs.cmu.edu along with a sample exam and more information.

The Mastery Exam

Before we begin looking at exactly whats on the mastery exam theres a couple comments that I want to make on the philosophy behind it. The most important thing is that there are approximately four parts and each of the parts is graded on a pass/fail system. This means that although someone will be quickly glancing through your code to make sure that its an honest attempt, and not just a bunch of println statements there will be no partial credit.

Just to make sure that everyone understands, there is NO partial credit on the exam. This means that it is very important to test your code before you turn it in, because a single mistake in the format of your output can cost you 1/4 of the credit on the exam.

Now that we've discussed that on to some better news. In general the content of the exams should be easily doable for you. It will be on things that we've been doing for the last several weeks, so everyone should be able to pass the exam easily. On the other had I can't emphasize enough how important it is to practice for the exam, because there is no partial credit. Also you will probably find that doing timed programming can be a lot more stressful and a lot more difficult then it is to do the homework assignments where you have as much time as you want. A lot of people last year had problems with methods that they could easily write for homework because they simply ran out of time. Another big suggestion is that when you practice make sure that you time yourself, and that you can finish it about an hour. If not you should practice some more.

In general a good study strategy would be to get together with a couple of other people in the class and each make up sample exams, then have everyone else in the group practice doing the exam.

Content

Theres a couple things that you have to remember while taking the exam. This exam is used across the board for all the intro programming classes. However all the intro programming classes are not exactly at the same point. So in general the content of the exam tends to go down to a level that all the intro classes are at.

What this means for you is that you will not be doing Exception handling on the test. Or if you do have to do it, it will be something like having to return a specific value if it is an edge case instead of creating your own exceptions or throwing or catching exceptions.

Once again the actual content on the exam shouldn't be that difficult, but try not to make it anymore complicated then it absolutely needs to be. Your output has to mirror thier output exactly, so even if you see a place that using a more advanced tecnique would make a better method ignore it.

Example Mastery

Today we went over information for the mastery exam. The first thing you should to is to go to the website listed at the top of the page, download the Exam overview and read through it. This page contains the general format of the mastery exam that you will be taking. It provides a general description of the methods that you will have to implement and what you will be expected to do.

Now we're going to quickly go through what you can expect to find on the exam.

First, you must implement a class. It is just like many of the things we have written before (textbook, Definition, etc.).

It should have proper instance variables. int, char, boolean, and double are all primitives, so you can use >, =, and < on them. Strings are objects, however, so you need .compareTo() or .equals() to compare them.

Your constructors should initialize all variables, you will probably have to set some to a default value (eg. count=0) and assign some values as parameters (eg. this.maxSize = maxSize)

You will have to do standard accessor methods (eg. getDefinition()), which take in no parameters and return a specified instance variable's value.

You will also have to do standard mutator methods (eg. setPrice()), which take in a parameter and changes an instane variable, returning nothing.

You will also have to write a toString() method for your class, which should generally print the string representation of all of the instance variables. Make sure that your code looks exactly like the sample output, so if the exam has a sample that says "Bob weighs 180 pounds and is 19 years old" do this exactly and not a toString() that says "name: Bob, weight: 180, age: 19"

A tester will be provided for you. You should run this tester when testing your code because this will be the tester that your code will be graded on. The way that it will be graded is that the tester will be run and the output produced will be compared to the output that they provide you with, and if your output matches exactly you get the points, if not you get 0.

Part 2 should be a simple filter method. You will need to through and print all objects that meet a certain criteria, which would probably just be through brute force search. In fact this is a good example of a place not to make it more complicated then absolutely necessary. Just get a simple brute force search out of the way instead of worrying about doing things like a binary search.

Part 3 is insertion, part 4 is a remove. There are 4 major policies:

1.) Set with "up by one" promotion

Insertion: If the item is already in the array, swap it with the one in front of it using a standard swap technique. If it is already at the front do nothing. If it's not in the array, put it at the end.

Remove: Remove the item from the array, shifting evrything to the left to fill the hole.
2.) Set with "move to front" operations
Insertion: Try to find the thing you're inserting. If it isn't there, put it at the end of the list. If it is there, store that value in a temporary variable, create a hole where the old copy was, shift everything in front of the hole backward, and insert the new item into the front.

Remove: Remove the value from the array, filling in the hole. The order at the end should be the same.
3.) Multiset with ordered values
Insertion: This is an insert in order. One key thing to notice is that if there are multiple things with the same value, the newly inserted item should be IN FRONT OF all of previous inserted (ie to the left of it in the array), so if you start at the end, you will keep shifting while the element before you is >= the value to insert.

Remove: This removes only the first occurrence of the value. Remove it, fill in the hole.
4.) Multiset with counted values
Insertion: This question will only be done with the class we wrote. If we try to add something and it isn't there, we add it to the end. If we find it, we increment the count of that variable. .

Remove: Decrease count by one. If count becomes 0, remove it from the array, and shift everything down.
5.) Priority Queue with searching
Insertion: Insert it to the beginning of the array, so shifts all the elements in the array to the right and inserts the new element at front.

Remove: Remove the item with the highest priority. If there are multiple items that have the same highest priority, remove the one closest to the end of the array (ie furthest to the right.) So if you start at the end, you will only change the index of maxPriority if the element to the left is > the previous max, and if you start at the left, you will change it if the element is <= the previous max.
6.) Priority Queue with sorting
Insertion: This is an insertInOrder, with those with highest priority going in the FRONT of the array. If two vales have the same priority, the new values should be inserted in front (to the right? some confusion).

Remove: Remove the item with the highest priority (the first item in the array). Fill in the hole.
7.) Sequence
Insertion: insertAt will store the value at the specified index of the array, moving all items at and beyond the index back. If you are given an invalid index, print out the specified error message (System.out.println, no exception handling needed).

Remove: Remove the item at the index. If you are given an invalid index, print out the specified error message (System.out.println, no exception handling needed).

Suggestions

Get together in STUDY GROUPS! Get started studying early! Come see TAs and Kesden, ask us questions. We will help you.