CCPS 109 Computer Science I, Spring 2012

Ryerson School of Computer Science & Chang School of Continuing Education

Ilkka Kokkarinen

This page is located at: http://www.scs.ryerson.ca/~ikokkari/ccps109.html

News

[May 15] I haven’t had time to grade your exams yet, but I’ll grade them tomorrow and bring them to the lab on Friday, or the class on Monday.
[May 9] Like I said in the class, because this semester runs in double speed, some of you might not have enough time to finish the Sokoban project. Therefore for those students who don’t submit it successfully, I will compute your final grade as (midterm + final + labs) weighted to be out of 80, but with the proviso that your maximum grade can be at most C. So if you want to get a grade that starts with B or A, you need to complete the Sokoban project.
Watch this space for announcements about the course.

Course Information

Lecturer: Ilkka Kokkarinen. Please use the email address ilkka.kokkarinen@gmail.com for all communications, as I don’t really read my Ryerson email regularly.
Hours: Since the spring term proceeds in double pace and lasts only seven weeks instead of 14, the lectures are held twice a week, Mondays and Wednesdays 6:00 at VIC202, and the labs are held Fridays at 6:30 at ENG201 so that each Friday holds a double lab.
Material: The official textbook for the course is Big Java by Cay Horstmann. The latest edition is the fourth, but since I won’t be following the textbook that closely, any edition from second one would be OK. Outside the official material, the website “Introduction to Computer Science using Java” is pretty good.
Grading: Midterm Exam 30 marks, Labs 20 marks, Final Exam 30 marks, Programming Project 20 marks.
Software: If you want to do Java programming on your own computer, first download and install Java SE JDK 7 (note that you need to download the JDK to be able to write and compile your own programs, whereas JRE simply lets you run other people’s Java programs), then download and install the BlueJ integrated development environment. (If you are working on a Mac, you already have Java SE in your machine and don't need to download it, so you just need to download BlueJ.) If you prefer to work with some other Java IDE, particularly Eclipse, that is all right with me, since the Java language itself is the same everywhere.

Course Outline

Lecture 1 (Apr 30): Classes and objects. Introduction to programming. Idea of objects. Classes and objects. The BlueJ programming environment. Methods. Instance variables versus local variables. Built-in data types. Private and public parts of a class. Holder.java
Lecture 2 (May 2): Loops and conditionals. Conditional statements. Loops. Boolean expressions and logical operators. Different types of loops. Nested loops. Methods that return values. Conditions.java Loops.java ReturnValues.java
Lecture 3 (May 7): Objects and references. References to objects. Assignment, comparison and parameter passing for references. Creating new objects. The object life cycle. Constructors, overloading. Static fields and methods. Fraction.java
Lecture 4 (May 9): Loops programming practice. Go through a bunch of old midterm exams to review the topics of the course so far. midtermreview.pdf
Lecture 5 (May 14): Midterm Exam. This week, we also have a lab on Friday.
Lecture 6 (May 16): Creating graphical user interfaces with Swing. ShapePanel.java Nested.java Counter.java Metric.java ImageDemo.java Transformations.java Tree.jpg Selections.java
Monday May 21 is Victoria Day, University is closed.
Lecture 7 (May 23): Arrays and array lists. Built-in arrays and their operations. Array methods. Array lists and other Java collections. Two-dimensional arrays. RummyTool.java GameOfLife.java
Lecture 8 (May 28): Arrays programming practice. Write out a whole bunch of example methods that work with arrays. arrays.pdf ThirdBatch.java Elections.java
Lecture 9 (May 30): Algorithm analysis, sorting and searching. Examine the classic array algorithms, especially sorting and searching. Binary search trees.
Lecture 10 (Jun 4): Recursion. The idea and use of recursion, followed by various exercises about the topic. Sierpinski.java recursion.pdf
Lecture 11 (Jun 6): Software engineering. General issues about programming and software engineering that are independent of the particular programming language used.
Lecture 12 (Jun 11) Example programs. Go through a bunch of example programs that demonstrate the topics of this course.
Lecture 13 (Jun 13): Review of the course material. Go through a bunch of review exercises and old final exams. finalpractice.pdf finalexams.pdf
Lecture 14 (Jun 18): Final exam.

Labs

The weekly labs are not compulsory, but each lab is worth two marks of your total grade. Each lab consists of four problems, and solving each problem correctly is worth half a point of your total course grade. You can work and solve the labs at home on your time and then submit them to the instructor by email, or you can come physically to the lab. Since the spring term proceeds in double speed, each Friday we have two labs.

Lab 1 (May 4): Demonstration of the BlueJ programming environment. No graded problems are assigned or lab marks given for this first lab.

Lab 2 (May 4):

Write a class Greeter that contains a String field name, and the following public methods: (a) void askName() that asks the user for a name in an input dialog box and stores it in the field name (b) void greetDialog() that displays a personalized greeting (for example, “Hello there, Bob!”) for the current name in a message dialog box (c) void greetConsole() that works otherwise the same way as the previous method, but outputs the greeting to the console.
Write a class BankAccount that contains a double field balance, and the following public methods: (a) void outputBalance() that outputs the current balance of that account on the console (b) void deposit(double amount) that increases the balance by the given amount (c) void withdraw(double amount) that decreases the balance by the given amount. Note that this class should not use Swing dialog boxes for anything.
Write a class Temperature that can be used to convert temperatures from Celsius to Fahrenheit and vice versa. The objects of this class remember the current temperature in both Celsius and Fahrenheit scales. (Use two fields of type double for this purpose.) The class should have the following three methods: (a) void setCelsius(double temp) that sets the current temperature to temp degrees Celsius (and calculates what it is in Fahrenheit, updating also that field) (b) void setFahrenheit(double temp) that works the same but for Fahrenheit (c) void outputCelsius() that outputs the current temperature in Celsius (d) void outputFahrenheit() that outputs the current temperature in Fahrenheit. (To convert between Celsius and Fahrenheit temperatures, the conversion formulas are F = 9.0/5.0*C + 32 and C = (F-32) * 5.0/9.0. For example, 100 degrees Celsius equals 212 degrees Fahrenheit.)
Write a main method for the previous class Temperature that creates an object of that type and then calls its methods with some test parameter values that you choose for yourself, outputting the result of each method call to the console.

Lab 3 (May 11):

Write a single class LoopProblems that contains the following four public methods.

void outputCelsiusTable(int start, int end) that outputs on the console a conversion table from Celsius to Fahrenheit. The table should go through the Celsius values from start to end, and output each temperature and the corresponding value in Fahrenheit on a single line.
long factorial(int n) Calculates and returns the factorial of parameter n. The factorial of n is the product of all numbers from 1 to n. For example, the factorial of 5 would be 1*2*3*4*5 = 120. (Hint: this method should initialize a local variable result to one, and then loop from 2 to n. For each value in the loop, multiply it into result. After the loop, return the result.)
long sumOfFactorials(int min, int max) Calculates and returns the sum of factorials of the number from min to max. (Hint: This method should initialize a local variable result to zero, then loop from min to max, use the previous method factorial to calculate the factorial of each value and add it to the result, and after the loop return the result.)
String repeat(String s, int n) Creates and returns a new string that is made by concatenating n copies of the parameter string s. For example, calling this method with the parameters “Hello” and 3 would return the string “HelloHelloHello”. If n is zero or negative, the method should return the empty string.

Last, write a main method for this class. This main method should create a new LoopProblems object and call the previous methods with some suitably chosen (that is, pulled out of the hat) test values, and output on the console the results that these methods return.

Lab 4 (May 11):

We continue practicing writing loops. Write a class MoreLoopProblems and the following methods in it:

void outputDeckOfCards() that outputs on the console the English-language names of all of the cards of a normal deck of cards, one card per line (for example, “ace of hearts”, “four of spades” etc.) Of course, this method should not simply consist of 52 consecutive console output statements, but you should instead use loops to try to make your code as clean and compact as possible.
int promptForNumber(int min, int max) Uses a Swing message dialog box to ask the user to input a number. If the number that the user enters is not between min and max, inclusive, the method keeps asking again. After the user has entered a legal number, the method terminates and returns that number. (Hint: a do-while loop would be really appropriate here.)
int fallingPower(int base, int n) that computes and returns the n:th falling power of base, which is the product of n consecutive terms (base)*(base-1)*(base-2)* … * (base-n+1). For example, fallingPower(10,3) should return 720, which is 10*9*8.
int debtCakulator(double debt, double interest, double payment) that calculates how many years it will take to pay down a debt of debt dollars, when each year the remaining debt is multiplied by the given interest rate and you then make an annual payment of payment dollars. The method should return the integer number of years that it takes to make debt to become zero or less. If the annual payment is not enough to cover the annual interest, the method should output an error message “The debt will never be paid off” on the console and return -1.

Lab 5 (May 18):

In this lab, we shall take a closer look at the String class and its operations, and use it to practice writing loops and prepare for the array operations. First, look up the class String in Java API Reference, and check out the methods charAt and length that you will be needing to implement this week's methods. The method charAt can be used to extract a single character from the given position from a string, where the positions are numbered starting from zero. For example, the call “Hello world”.charAt(4) would return the character 'o', the fifth character in the said string. Note that you can only use charAt to read a character, not modify it inside the string, as the objects of String class are immutable.

For your lab, create a class StringProblems and write the following methods in it:

int count(String s, char c) that counts how many times the character c appears in the string s, and returns that number.
String reverse(String s) that creates and returns a new string that is the same as the parameter string s but reversed. For example, when called with the parameter “Hello”, the method would return the string “olleH”. (Hint: initialize a result string to be empty, then loop over the characters of the string s, adding them to the result in reverse order.)
boolean isPalindrome(String s) that returns true if the parameter string s is a palindrome, that is, the same regardless whether it is read from left to right or from right to left. For example, “eve” and “rotator” are palindromes. (Hint: by using the previous method reverse you can make this a one-liner.)
String disemvowel(String s) that creates and returns a new string that is otherwise the same as the parameter string s, except that all the vowels (aeiou) have been removed. For example, when called with the parameter “Kokkarinen”, the method would return “Kkkrnn”. For simplicity, your method only needs to recognize the lowercase letters aeiou as vowels.

Lab 6 (May 18):

Here are some more problems about writing loops and using strings. First, look up the method substring in the class String and learn how it works. Write a class MoreStringProblems and implement the following methods in there:

String stutter(String s) that creates and returns the string in which each character has been duplicated. For example, when called with the parameter “hello”, this method would create and return the string “hheelllloo”.
String trim(String s) that creates and returns a string that is otherwise the same as the parameter string, but all spaces in the beginning and end of the string is removed. The spaces inside the string between words are untouched. For example, when called with the string “ test pattern ”, the method would return the string “test pattern”. If the string contains nothing but whitespace, the method should return the empty string. (The class String already has a handy method trim that behaves this way, but of course you are not allowed to use it, but you have to write your own.)
String reverseCase(String s) that creates and returns a string that is the same as the original string, but uppercase letters have been turned to lowercase and vice versa, and other characters are left as they are. For example, when called with the parameter “Hello, world!”, the string returned would be “hELLO, wORLD!”. Use the handy static methods isLowerCase and isUpperCase of the class Character to detect whether a character is an upper- or lowercase letter, and the methods toUpperCase and toLowerCase to convert the characters.
int countOccurrences(String text, String pattern) that counts how many times the pattern string occurs inside text. For example, if text is “any man can dance on the pan” and pattern is “an”, the method would return 5.

Lab 7 (May 25):

Here are some exercises about creating interactive components with Swing.

Write a Swing component MyLabels that extends JPanel and contains three labels containing the text “One”, “Two” and “Three”, respectively. Your component should prefer to have a size of 200*100 pixels, and have an etched border around it. Write a main method for your class that creates and opens a JFrame instance that contains three such MyLabels components. (Inside the frame, there will therefore be a total of nine labels showing, that is, three labels in each of your three MyLabels components.)
Write a Swing component MyButtons that extends JPanel and contains three JButton instances titled “Red”, “Green” and “Blue”. Your component should listen to the action events of its three JButton instances. Pressing a button should change the background of your MyButtons component to red, green or blue, respectively. (Use the method setBackground to change the background colour of a Swing component.) Write a main method for your class that creates and opens a JFrame instance that contains three MyButtons components.
Write a Swing component Head that extends JPanel whose method paintComponent draws a simple human head. (Doesn't need to be fancy, just use simple ovals and rectangles.) This component should have a JCheckBox labelled “Hat”. If this checkbox is selected, the head is drawn with a hat on, otherwise the head is drawn without a hat. Make your component listen to the item events of the checkbox so that whenever the user changes the state of the checkbox, the component is repainted.
Write a Swing component Adder that contains two JTextField instances, a JButton labelled “Add” and a JLabel. When the user presses the button, the component should read the numbers from the two textfields, add them up and show the result in the label. If either textfield contains an invalid number, it should just be considered a zero.

Lab 8 (May 25):

Here are some more exercises about creating interactive components with Swing. Write the following components, and for each component write a main method that opens a JFrame that contains one instance of that component.

Write a Swing component ColorGrid that displays a 10*10 grid of geometric rectangles on its surface, so that the entire grid fills the current area of the component. Make this component prefer to be 200*200 pixels in size. Note that the whole thing is one component that displays 100 rectangle shapes on its surface, instead of being 100 components. Each cell in the grid initially shows a random colour (store the cell colours in a 2D array of Color objects). The component should listen to its mouse events so that whenever the user presses the mouse button inside the component, the component detects what cell the press took place in, changes the colour of only that cell to a random colour, and then repaints the entire component.
Let's practice listening and handling key events, since you are going to need them in the Sokoban programming project. Write a Swing component KeyEcho that listens to its key events with an inner KeyListener. Whenever some key is pressed, the keyPressed method asks the parameter KeyEvent object for the key char and key code, and outputs them on the console. To make your component able to gain focus, put the two statements this.setFocusable(true); and this.requestFocus(); in the constructor of your class. Write a main method in your class to try it out.
Add a boolean field mouseInside to your Head class of the previous lab, and make your component listen to its own mouse events with an inner MouseListener. Write the methods mouseEntered and mouseExited so that they just set this field to true and false, respectively, and the other three methods do nothing. Modify your paintComponent method so that if mouseInside is true, the head is drawn with open eyes, and otherwise it is drawn with closed eyes.
Write a Swing component ClickCloud that contains an ArrayList of Point objects. The component should listen to its mouse events and each time the user clicks the mouse on the component, the listener asks the MouseEvent parameter the point that the click took place in (use the MouseEvent method getPoint for this), and adds it to the arraylist. The paintComponent method of this component should loop through the arraylist and draw a 3*3 rectangle at each point stored there.

Lab 9 (Jun 1):

This week, it's array operations time. Create a class ArrayProblems and write the following array methods in it:

boolean isSorted(int[] a) that checks if the elements of the array a are already in sorted order. This method does not modify the contents of the array a in any way, but simply checks if the elements are already in sorted order.
boolean noDuplicates(int[] a) that checks if all elements in the parameter array a are unique, that is, the array does not contain any element twice or more. Note that this parameter array is not assumed to be sorted, so you can't just compare each element to the next one.
ArrayList<Integer> createArrayListOfCubes(int n) that creates and returns a new ArrayList<Integer> that has a total of n elements so that the i:th elements equals the third power of i. For example, if n equals 5, the arraylist returned would contain the numbers 0,1,8,27,64.
int[][] transpose(int [][] a) that creates and returns a two-dimensional array whose element in each location [i][j] is the same as the element a[j][i] in the mirror image location of the original parameter array. You can assume that each row of the parameter array a has the same length.

Lab 10 (Jun 1):

We continue writing code for arrays. Create a class MoreArrayProblems and write the following array creation methods in it:

int[] everyOther(int [] a) that creates and returns an array that contains the elements from the even indices of the array a, that is, the elements a[0], a[2], a[4],... Make sure that the array that you return is exactly the right size to contain these elements, not one more or less.
int[] allFactorials(int n) that creates and returns an array with n+1 integer elements so that the elements with indices 0 and 1 have values 1, and each element with index i has the value of the factorial of i. (Can you write this method so that it contains only one loop, instead of two nested loops?)
ArrayList<Integer> allFactorialsArrayList(int n) that is like the previous question, but now it creates and returns an ArrayList.
int[] stutter(int[] a) that creates and returns an array that contains all of the elements of a, each element duplicated. For example, if called with the parameter array [1,8,3,2], this method would create and return the array [1,1,8,8,3,3,2,2].

Lab 11 (Jun 8):

In this last lab, we do some recursion. You can also today get help for your programming project. All of the following methods must be fully recursive, with no loops at all. Also, write them so that you don’t use any additional fields in the class to store the intermediate results, but you pass all the data that you need as parameters going down and as return values coming up.

double product(double[] a, int start, int end) that calculates the product of array elements from the index start to index end.
boolean allEqual(int[] a, int start, int end) that checks if all elements in the array a from start to end are equal.
void arraycopy(double[] src, int start, double[] tgt, int start2, int len) that copies len elements from the location start of array src to the location start2 of array tgt. (That is, this method works the same as System.arraycopy.) Hint: when len is zero, do nothing, otherwise copy one element and then recursively copy len-1 elements.
boolean linearSearch(int[] a, int x, int start, int end) that checks if the array a contains the element x anywhere between the indices start and end.

The remaining lab Jun 15 has no assigned problem sets for it, but are scheduled for getting help with your Sokoban programming project.

Programming Project

The course contains one programming project, which is personal and worth 20 marks of your grade. The specification and instructions are available on the page sokoban.html. The deadline of the project is Saturday June 16. A separate Sokoban FAQ page answers some problems that seem to occur to many students.