Introduction to Programmingusing the Processing languageLecturer: Maarten Lamers of the Media Technology MSc program at Leiden University Teaching assistant: Joris Slob Course developed by Bas Haring (2004) Alterations by Maarten Lamers (2005, 2006, 2007) Introduction Lecture I Lecture II Lecture III Lecture IV Lecture V Lecture VI Lecture VII Fun |
|
Programming concepts |
Recursive functions Stacks Queues Data structures Sorting |
Reserved words |
String .charAt() .substring() |
Example VI.1 |
This function multiplies two positive integer values without using the multiplication (*) operator. Note that the function calls itself. This is called 'recursion'; the function is called 'recursive'.
int multiply(int i, int j) {
if (j == 0) {
return(0);
} else {
return(i + multiply(i,j-1));
}
}
Complete source |
Example VI.2 |
Recursion is useful when a process or structure "is repeated within itself". For example, a 'palindrome' is a string spelled the same forward as backward. By definition a palindrome must contain palindromes within itself. Note carefully how recursive functions end their execution. This 'termination criterion' makes sure that the function finally stops running.
boolean palindrome (String s) {
int n = s.length();
if (n < 2)
// Every string of length 0 or 1 is a palindrome!
return (true);
else {
// The first and last character must be equal.
boolean p = (s.charAt(0) == s.charAt(n-1));
// The string inbetween must be a palindrome also.
p = p && palindrome(s.substring(1, n-1));
return (p);
}
}
Complete source |
Example VI.4 |
A 'stack' is a form of 'data structure'. It is designed to store and access data in a specific way.
Stacks work on the Last-In-First-Out principle: the last element added to the stack is always the
first one that is removed.
To add an element to a stack, you use a function that is usually called push().
Elements are removed with a function that is usually called pop().
// Let's assume we have an integer stack called 'st'.
st.push(28);
println(st.pop());
st.push(1);
st.push(19);
println(st.pop());
st.push(68);
println(st.pop());
println(st.empty());
println(st.pop());
println(st.empty());
Complete source (updated!) |
Example VI.5 |
Another common data structure is the 'queue'. It can be used to store and retrieve data in a First-In-First-Out manner. Compare this program to the one above (and their output), and understand how they differ.
// Let's assume we have an integer queue called 'q'.
q.enqueue(28);
println(q.dequeue());
q.enqueue(1);
q.enqueue(19);
println(q.dequeue());
q.enqueue(68);
println(q.dequeue());
println(q.empty());
println(q.dequeue());
println(q.empty());
Complete source (updated!) |
Example VI.6 |
Sorting is an important task done by computers, and many sorting algorithms exist.
This example sorts an array of integer numbers using the "bubble sort" algorithm, a
simple but fairly inefficient sorting method. It repeatedly steps through
the list, and when two adjacent items are in the wrong order, they are swapped.
In this way, small elements "bubble" towards the start of the list. Below is a
description in human language. Study the complete source code to understand how
it works.
repeat until all items are sorted
{
loop over all unsorted items
{
if two adjacent items are in incorrect order
{
swap them.
}
}
// Now at least one more item is sorted!
}
Complete source |
Assignment VI.1 |
Write a recursive function int power(int i, int j) that returns i to the
power of j. Both i and j must have positive integer values.
For example, power(2,8) should return 256, and power(12,0) should return 1. |
Assignment VI.3 |
Create a class for the SortedList data structure. It holds integer values in sorted
order. The class must have methods to insert a new value, to get and remove the item at position i,
and to return the number of items in the list.With the below setup() function, your code should return 2, 1, 68, 28, 19, in that
exact order.
void setup() {
// Create and initialize object s of class SortedList.
SortedList s = new SortedList();
// Insert and remove items from the SortedList.
s.insert(28);
s.insert(1);
println(s.length()); // Print number of items in list.
s.insert(19);
s.insert(68);
println(s.remove(0)); // Remove and print the smallest item.
println(s.remove(s.length()-1)); // Remove and print the largest item.
println(s.remove(s.length()-1)); // Remove and print the largest item.
println(s.remove(s.length()-1)); // Remove and print the largest item.
}
|
Homework Assignment 3 |
Write a game that reacts to user input and involves at least two moving objects. Your game need not be highly complex, but it may not be totally trivial either. Something with the complexity of simple Pong is fine. Also, explain and motivate in no more than 400 words:
|