CS106A Lecture 3 Notes

Lecture 3 of CS106A covers the last 3 chapters of Karel the Robot. In particular, it covers stepwise refinement, algorithms as well as gives more details about SuperKarel and what extras he can do. Karel is coming to an end after this lecture, at which point you will move on to specific Java rather than being stuck at Java with the limitations of Karel.

Although all lectures are important to watch and take note, this one provides some good examples of the top-down design approach and how you break a program down/decompose it with stepwise refinement. It’s well worth watching and paying attention to this part.

Infinite Loop

One of the first items mentioned in class is the Infinite Loop. An infinite loop is created when the conditions of the program can never be false and thus, the program gets stuck in an endless/infinite loop. An example shared is of Karel the Robot being told to turnLeft() while his front is not blocked. If Karel is in the middle of the grid, or simply away from all four walls then Karels front will never be blocked and he will be stuck in an infinite loop turning left continually. These conditions need to be watched out for and can be easy to get stuck in.

This is also a reason why a good top-down design approach can be used. If you just create a long list of individual statements that are not broken down in to manageable chunks then finding the cause of an infinite loop can be made a lot harder. On the flip side, if your program is broken down then you simply need to find the method which instructs Karel to turnLeft() while his front is clear and you can more easily spot the mistakes.

Off By One Bug

If you have already worked on Assignment 1, you might have already come across an OBOB error. OBOB means that your program is off by one. This commonly happens when you use a loop to check if a condition is valid. In the case of Karel, when you get to the wall on the Stone Mason assignment, you will likely exit out of the loop before checking the last column. This is fine and you can simply add in another check column after the loop… but you need to make sure you know why this happens and what can be done to prevent a program finishing slightly too early with the task uncompleted.

Why you need comments

When programming in any language, you need to comment your code. The reason for this is that you let others who might work on your code at a later date know exactly what is happening in English. Likewise, you also let your self know should you return to make changes later on down the line.

Comments in Java can be created in two different ways.

Multi-line comments

/*
* This is a comment block
* that can have a number of lines
* the stars on each line are not
* mandatory (except the opening
* and closing slash * and * slash
* but stars help make it more readable.
*/

import stanford.karel.*;

Single line comments

Alternatively, you can write just single comment lines… perhaps within your code explaining what a particular variable is for. Single line comment lines begin with a double slash //.

// Just a comment

import stanford.karel.*;

//another comment
//You can put double slashes on to
//two lines is you wish
//but the slash * as above is recommended

Comments are used in various locations such as the header of your .java files. These give information such as the author, copyright and a brief description of what the class does. Smaller comments or method comments should include pre and post-conditions such as:

/*
* pre-condition: Karel needs to be facing east
* post-condition: Karel needs to be returned to his original location facing east
* 
* This method collects beepers on the column of the corner of where Karel is standing.
*/

Decomposing Problems

As mentioned above, this particular lecture has a great demonstration on top-down design and what it means to decompose a problem. Simply put, you need to break your program down in to more easy bits of information. A real world example of brushing your teeth can be used. You might know how to brush teeth, but to break that down you could go in to more detail about putting tooth paste on the brush, how to brush, how to rinse etc… Each of those can be decomposed even further.

The lowest level you can decompose to is a basic command such as move(); although it might not be necessary to go down to that low level each and every time.

Overall, another impressive lecture. Although a lot of the early examples are fairly easy to understand, you will find when you tackle your first assignments that it is harder to create some code and an algorithm to make it work. Keep practicing though and you will eventually grasp it.