- 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 the underlying features of lists and how they differ from arrays.
- Be able to use built-in Java lists
- Be able to build a custom list class
- Understand the time costs of various list operations

Lists are data structures, much like arrays. The differences being,

Arrays can hold a collection of primitive data types or a collection of objects, while lists can hold a collection of objects, **not** primitive data types.

The size of array needs to be specified at the time of creating an array. The size of a list need not be specified. You can add as many items as you want to a list (permitting system memory).

With arrays (assuming array name is `arr`

), the only operators you have to work with are `arr.length`

and `arr[i]`

. Anything and everything you need to do must be done using these two operators. Several life-saving methods are applicable on list objects, such as:

`get(int)`

//similar to arr[i]`size()`

//similar to arr.length`add(Object)`

//add item at the end of the list`remove(Object)`

//parameter represents item to be removed`remove(int)`

//parameter represents index`indexOf(Object)`

//parameter represents item being searched`lastIndexOf(Object)`

//parameter represents item being searched

Consider an array `src`

holding 100 integers. Some negative, some positive.
We need to copy all negative items over to a new array `dest`

.

As an example, if

`src`

is `{10, 20, 50, 0, -40, 30, 90, 60, -10, -50, 80}`

`dest`

should be `{-40, -10, -50}`

In order to do this, we need to,

- Count the number of required (negative) values in the array
`src`

- Create an array
`dest`

of that size - Copy items over to
`dest`

.

1
2
3
4
5
6

int count = 0;
for(int i=0; i < src.length; i++) {
if(src[i] < 0) {
count++;
}
}

1

int[] dest = new int[count];

We are copying,

`src[4]`

into `dest[0]`

`src[8]`

into `dest[1]`

`src[9]`

into `dest[2]`

So, in addition to the current index of `src`

, we also need to keep track of the current index of `dest`

into which the item must be copied.

1
2
3
4
5
6
7

int idx = 0; //index where item must be copied
for(int i=0; i < src.length; i++) {
if(src[i] < 0) {
dest[idx] = src[i]; //another item copied
idx++; //move destination index forward
}
}

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

int count = 0;
for(int i=0; i < src.length; i++) {
if(src[i] < 0) {
count++;
}
}
int[] dest = new int[count];
int idx = 0; //index where item must be copied
for(int i=0; i < src.length; i++) {
if(src[i] < 0) {
dest[idx] = src[i]; //another item copied
idx++; //move destination index forward
}
}

A solution to the same problem when `src`

and `dest`

are lists instead of arrays is,

1
2
3
4
5
6

ArrayList<Integer> dest = new ArrayList<Integer>();
for(int item: src) {
if(item < 0) {
dest.add(item);
}
}