- Transition to Processing
- Primitive Operations
- Algorithms
- Variables
- Debugging in Processing
- Conditions
- Loops
- Functions
- Scope
- Compound Data
- Reference Semantics
- Refactoring
- Transition to Java
- Debugging in Java
- Unit Testing
- Classes - Writing your own Types
- Classes - Functions inside objects
- Recursion
- Lists
- Iteration
- Recursive Lists
- Searching

- Logic and Proofs
- Relations
- Mathematical Functions
- Matrices
- Binary Numbers
- Trigonomtry
- Finite State Machines
- Turing Machines
- Counting - Inclusion/Exclusion
- Graph Algorithms

- Algorithm Efficiency
- Algorithm Correctness
- Trees
- Heaps, Stack, and Queues
- Maps and Hashtables
- Graphs and Graph Algorithms
- Advanced Trees and Computability

- Command line control
- Transition to C
- Pointers
- Memory Allocation
- IO
- Number representations
- Assembly Programming
- Structs and Unions
- How memory works
- Virtual Memory

- Version Control with Git
- Inheritance and Overloading
- Generics
- Exceptions
- Lambda Expressions
- Design Patterns
- Concepts of Concurrency
- Concurrency: Object Locks
- Modern Concurrency

- System Models
- Naming and Distributed File Systems
- Synchronisation and Concurrency
- Fault Tolerance and Security
- Clusters and Grids
- Virtualisation
- Data Centers
- Mobile Computing

- Transition to Scala
- Functional Programming
- Syntax Analysis
- Name Analysis
- Type Analysis
- Transformation and Compilation
- Control Abstraction
- Implementing Data Abstraction
- Language Runtimes

- Transition to Coq
- Proof by Induction, Structured Data
- Polymorphism and Higher-Order Functions
- More Basic Tactics
- Logical Reasoning in Proof Assistants
- Inductive Propositions
- Maps
- An Imperative Programming Language
- Program Equivalence
- Hoare Logic
- Small-Step Operational Semantics
- Simply-typed Lambda Calculus

- Understand how larger chunks of data are stored in a program
- Understand how to access these larger chunks of data
- Understand the most common data chunks, arrays

So far we have been working only with *atomic* data. That is data that is “just one thing” and can’t be broken up. This is getting unwieldy. Everytime we have something to draw, we need to have an x-position and a y-position and so we need two variables for something we probably think of as just one thing (the position on the screen).

Wouldn’t it be nice to have just one variable for both? Yes, yes it would.

The facility we need for this is *composite data*. We need a way to put two values (the x and the y positions) into a single variable. What type would this be? Not an `int`

or a `float`

or a `char`

! Processing *does* have types we can use for this, but they act a little differently from the types we already know.

Let me introduce you to one of these types, `PVector`

.

Recall that processing has *values* (like 1,c,4.5) that are grouped into *types* (like `int`

, `char`

, `float`

). It is possible to have a value with two numbers in it, that value would be of the type `PVector`

:

- (1,1) is a
`PVector`

with two values in it,`1`

and`1`

- (10,4) is a
`PVector`

with two values in it,`10`

and`4`

.

So you can see that we have a whole new type and a whole new set of values that fit into that type. Lets play with it.

The Processing website has an example of using `PVectors`

for a bouncing ball program. Study it carefully.

You will notice two interesting features that we will now discuss:

- the use of “dot-notation” to get inside the compound data
- the use of
`new`

for an extra step in the declare-and-initialise process.

So, compound data is *bigger*, so much so, that it can’t fit into a single memory slot. *But* variables can only point to single buckets, so what do we do?

For compound data, a variable will point to one memory location that then tells you *where the larger chunk of memory is*.

```
int[] myArray;
myArray = new int[5];
```

So, an extra step is required, making the memory box point to another, larger, chunk of memory. This is what `new`

does. It finds some free space that is big enough, and sets aside that much space. Lets call this step “memory allocation”.

The other new step is to “follow the arrow” from the memory box to the bigger chunk and to pull out one part from there. This is what the `.`

does. It follows the arrow and then uses the special name that comes after to get one of the values from the larger chunk. Lets call this step “de-referencing”.

Processing actually has two different forms of compound data - objects like `PVector`

(and many others), and arrays. We will focus on arrays from here but feel free to use objects whenenver you like.

Note: objects are often taught with a related concept - classes - however, we will not address classes in any way at this point.

Note that the two different versions of compound data come with two different syntaxes for dereferences - for objects is it `.name`

and for arrays it is `[number]`

. See below for details.

To understand how to use compound data, we will look at the most common compound data type, arrays.

An array is a fixed-sized collection of items, each item of the same type.

So you can have,

- an array of 5 integers
- an array of 20 booleans
- an array of 2000 characters
- an array of 50 Strings
- an array of 400 arrays
- and so on…

There are a few ways to create an array.

The most common way to create an array is by specifying the type and size of the array.

1

type[] arrayName = new type[size];

1

int[] arr = new int[5]; //an array that holds 5 integers

1

boolean[] flags = new boolean[8]; //an array that holds 8 booleans

When you know the values that need to be stored in the array beforehand, you can create an array as,

1

type[] arrayName = {item1, item2, ....};

1

int[] cutoffs = {50, 65, 75, 85};

1

char[] punctuations = {'.', '!', '?', ',', ';', ':'};

The number of items in an array `arr`

is given by `arr.length`

.

Note that, given what we said above this means `.length`

should be read as “follow the reference and see how large the chunk of memory at the other end is”.

For example,

1
2

int[] data = new int[20];
println(data.length); //displays 20

- The first item of an array
`arr`

is at index 0. - The second item of an array
`arr`

is at index 1. - …
- The last item of an array
`arr`

is at index`arr.length - 1`

.

Thus you can traverse an array using a loop from `0`

to `arr.length - 1`

as,

1
2
3

for(int i=0; i < arr.length; i++) {
//do what you want with arr[i]
}

Create an array that holds the outcome of 20 dice rolls.

Each dice roll is a random integer between 1 and 6.

1
2
3
4

int[] outcomes = new int[20];
for(int i=0; i < outcomes.length; i++) {
outcomes[i] = (int)random(1, 7); //remember 7 is not included
}

Then we can find out the average outcome as,

1
2
3
4
5
6

int total = 0;
for(int i=0; i < outcomes.length; i++) {
total += outcomes[i];
}
double average = (total * 1.0)/outcomes.length;
//multiplication with 1.0 to convert int to double

For the next example, note that an integer takes up 4 bytes of memory.

The array items are held together in a block.

Consider the following array,

1

int[] arr = new int[4];

If the first item is at memory address 200-203, the second item will be at 204-207, the third item will be at 208-211 and the last item from 212-215.

The array itself holds the starting address, in this case 200.
That’s why we say that an array is a *reference*.

We represent this as,

or a more simplified way of adding the array label above the items.

1

boolean[] flags = {true, false, false, true, false};

Draw the memory diagram for the following code,

1

int[] data = new int[]{50, 90, 30, 20, 60};

Draw the memory diagram for the following code,

1
2
3
4
5
6
7
8
9

int[] data = new int[6];
for(int i=0; i < data.length; i++) {
if(i%2 == 0) {
data[i] = 2*i+1;
}
else {
data[i] = -3*i;
}
}

Write a piece of code that creates the arrays represented in the following diagram.

Draw the memory diagram for the following code,

1
2
3
4

int[] a = {4,8,15,16,23,42};
int[] b = a;
b[2] = 100;
b = new int[]{104,101,108,108,111};

Write a piece of code that creates an array with 100 integers, each between 1 and 20. Count the number of items that are divisible by the item after them.

For example, if the first few items of the array are `{20, 5, 8, 4, 4, ...}`

, 20 is divisible by 5, 8 is divisible by 4, and 4 is divisible by 4, so we have 3 such items so far.

Consider the following piece of code.

1
2
3
4
5

int[] items = new int[10];
items[0] = 1;
for(int i=1; i < items.length; i++) {
items[i] = 2 * items[i-1];
}

What are the contents of the array `items`

?

The ages of 20 people is stored in an array `ageList`

. Write a piece of code that determines the range of the distribution. That is, the age difference between the oldest and the youngest person.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//assuming ageList is a boolean array containing 20 items
int min = ageList[0];
for(int i=1; i < ageList.length; i++) {
if(ageList[i] < min) {
min = ageList[i];
}
}
int max = ageList[0];
for(int i=1; i < ageList.length; i++) {
if(ageList[i] > max) {
max = ageList[i];
}
}
int range = max - min;

The state of 25 electrical switches is held in an array `smartSwitches`

. The states can be “On” (true) or “Off” (false). Write a piece of code that toggles all switches. That is, all switches that are currently “On” should turn “Off”, and all switches that are currently “Off” should turn “On”.

1
2
3
4
5

//assuming smartSwitches is a boolean array containing 25 items
for(int i=0; i < smartSwitches.length; i++) {
smartSwitches[i] = !smartSwitches[i];
}

Assume that we are encoding birthdays as integers where:

- 1st january is 0,
- 2nd january is 1,
- and so on till,
- 31st december is 365

(remember that 29th february will also be given an integer mapping).

The birthdays of 1000 people is stored in an array `bdays`

. Write a piece of code that displays the most frequent date of birth. For the basic version, you may display an integer between 0 and 365. For the advanced version, display the actual data in `DD/MM`

format.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//assuming bdays is an array containing 1000 items
//such that each item is in range [0...365]
/*
frequencies holds number of birthdays on each of the 366 days.
if a birthday falls on 1st jan (coded as 0), frequencies[0] increases by 1
if a birthday falls on 2nd jan (coded as 1), frequencies[1] increases by 1
...
if a birthday falls on 32st dec (coded as 365), frequencies[365] increases by 1
*/
int[] frequencies = new int[366];
for(int i=0; i < bdays.length; i++) {
/*
int idx = bdays[i];
frequencies[idx]++; //another birthday on that day
}
int mostFrequentBday = 0; //1st jan
for(int i=1; i < frequencies.length; i++) {
if(frequencies[i] > frequencies[mostFrequentBday]) {
mostFrequentBday = i;
}
}
println(mostFreqBday);
//advanced:
int[] daysInMonths = {31,29,31,30,31,30,31,31,30,31,30,31};
int currentMonth = 0;
while(mostFreqBday < daysInMonths[currentMonth]) {
mostFreqBday = mostFreqBday - daysInMonths[currentMonth];
}
int dayInMonth = mostFreqBday+1;
println(dayInMonth+"/"+currentMonth);

I keep track of the time taken (in minutes) to run each kilometer over a 100km race (let me dream!). These times are stored in an array `lapTimes`

. For example, if `lapTimes[0]`

is 6.23, it means I ran the first kilometer in 6 minutes 13.8 seconds.

Write a piece of code that determines my fastest lap (for example, display “Kilometer 0-1” if the first kilometer was the fastest, and “Kilometer 63-64” if the 64th kilometer was the fastest.)

1
2
3
4
5
6
7
8

//assuming lapTimes is a float array containing 100 items
int fastestLap = 0;
for(int i=1; i < lapTimes.length; i++) {
if(lapTimes[i] < lapTimes[fastestLap]) {
fastestLap = i;
}
}
print("Kilometer "+fastestLap+"-"+(fastestLap+1));