1 of 31

COMP 210

Lecture 6

1

2 of 31

Announcements

TA Office Hours now in SN008!
My office hours tomorrow moved to 8am-10am
Review session tomorrow at 5:30pm in this room and on zoom
Ask questions anonymously at: pollev.com/kakiryan876

2

3 of 31

Quiz 01 Topics

General OOP Concepts
Abstract Data Types, Interfaces
Big-O / Code Analysis
Lists (Through what we get through today)

3

4 of 31

Big-O Continued

4

5 of 31

Code Analysis: Loops (2/2)

O(worst case # of iterations) * O(loop body)
Example:

for (i=0; i<N; i++) { // O(# iterations) = O(N)

// O(loop body) = max of:

int prefix_sum = 0; // O(1)

for (j=0; j<i; j++) { // O(inner for loop)

prefix_sum += data[j];

System.out.println(“Sum of first “ + i

+ “ items: “ + prefix_sum);

}

O(N) * (O(N) * O(1)) = O(N) * O(N) = O(N^2)

5

6 of 31

Code Analysis: Divide and Conquer Recursion (1/2)

O(recursive method) = O(depth of recursion) * O(width of recursion)

“Width” of recursion is maximum sum of O(recursive cases) at any given “level”

Common case:

Recursion divides problem into a fixed number of equal sized subproblems (usually 2)

O(depth of recursion) = O(log N)

Maximum width at bottom of recursion with N base cases that are each O(1)

O(width of recursion) = N * O(1) = O(N*1) = O(N)

Total for recursion: O(log N) * O(N) = O(N log N)

6

7 of 31

Code Analysis: Divide and Conquer Recursion (2/2)

Total for recursion: O(log N) * O(N) = O(N log N)

Example:

static int recursiveSum(int start, int end, int[] data) {

if (start == end) {

return data[start];

} else {

int first_half_sum = recursiveSum(start, (start+end)/2, data);

int second_half_sum = recursiveSum(((start+end)/2)+1, end, data);

return first_half_sum + second_half_sum;

}

7

8 of 31

Code Analysis: Divide and Conquer Recursion (2/2)

static int recursiveSum(int start, int end, int[] data) {

if (start == end) {

return data[start];

} else {

int first_half_sum = recursiveSum(start, (start+end)/2, data);

int second_half_sum = recursiveSum(((start+end)/2)+1, end, data);

return first_half_sum + second_half_sum;

}

8

9 of 31

Beware Exponential Recursion

Not all recursions are divide-and-conquer
Consider classic recursive fibonacci:

static int fib(int n) {

if (n < 2) {

return 1;

} else {

return fib(n-2) + fib(n-1);

}

O(fib) = sum of total number of calls to fib = O(2^N)

9

10 of 31

Example Problem 1

In terms of length of data array (call it N), what is O(findMax)?

public static findMax(int[] data) {

int max = data[0];

for (int i=0; i<data.length; i++) {

if (data[i] > max) {

max = data[i];

}

return max;

}

10

11 of 31

Example Problem 2

In terms of N, what is O(fun):

public static long fun(int N) {

int x = 2;

for (int i=N; i>0; i--) {

for (int j=i; j<i+8; j++){

for (int k=0; k<i; k++) {

x += i-j*k

}

return x;

}

11

12 of 31

Example Problem 3

In terms of N and K (i.e., lengths of arrays a and b respectively), �what is O(foo)?

12

13 of 31

Object -- The Universal Reference Type

13

14 of 31

Object: the universal reference type (and null)

An object has an is-a relationship with:

Its own class
Any interfaces that its class implements
Object

A name typed as Object can refer to any object of any type.
null : the universal reference value

AnyReferenceType a = null; Always OK no matter what AnyType is.

Object : the universal reference type

Object o = any_reference_type; Always OK no matter what type any_type is.

14

15 of 31

Generics

15

16 of 31

Parameterized Types

We can use generics so that we only have to write out the implementation once and it can operate over objects of different types.
User defined classes, interfaces and methods can be declared as generic!

16

17 of 31

An Aside: Method Access

References to objects in memory have access to only to methods defined for their declared type.

Assumptions: Person is an interface that has 2 methods -- breathe and eat. Student implements this interface. Additionally, Student has another method called study.

Person kaki = new Student(); // ok

kaki.breathe(); // ok

kaki.study(); // bad!

Student adin = new Student();

adin.study(); // ok

adin.eat(); // ok

17

18 of 31

Lists

18

19 of 31

The Behavior of List

Ordered elements

0 to n-1 where n = size of list

Basic Operations

Create
Insert at end
Extends list, making it one element larger
Insert at a position
Retrieve by position
Remove by position
Query size
Test for empty
Query element

19

20 of 31

Axiomatic Specification

A formal way of specifying the behavior of an ADT
Provides a way to reason about ADT operations.

Specify relationships between operations.
Identify pre- and post- conditions that must be true.

Three steps:

Develop a functional specification of ADT operations.
Identify canonical operations
Specify axioms of non-canonical operations

20

21 of 31

Functional Specification of List<E>

Abstract model of ADT operations
Written in a functional style

Stateless
Product of operation is considered a new instance

21

22 of 31

Canonical Operations

The minimum set of operations needed to produce any instance of the data type.
Suppose our list is: [3, 5]
All of the following operation sequences will produce this list:

rem (ins (ins (ins (new(), 8, 0), 5, 1), 3, 0), 1)
ins (ins (new(), 5, 0), 3, 0)
ins (ins (new(), 3, 0), 5, 1)
ins (ins (rem (ins (rem (ins (new(), 1, 0), 0), 2, 0), 0), 3, 0), 5, 0)

Any sequence of operations that uses rem can be rewritten in a simpler form that does not use rem.
Which operations are absolutely required to be able to produce any given list?

These are the canonical operations.
In this case: new, ins

22

23 of 31

Axioms of Behavior

Generate axioms by applying each non-canonical operation to each canonical operation.

Canonical: new, ins
Non-canonical: rem, get, find, size, empty

23

24 of 31

Axioms of Behavior

Generate axioms by applying each non-canonical operation to each canonical operation.

Canonical: new, ins
Non-canonical: rem, get, find, size, empty

24

25 of 31

Axioms of Behavior

Generate axioms by applying each non-canonical operation to each canonical operation.

Canonical: new, ins
Non-canonical: rem, get, find, size, empty

25

26 of 31

Axioms of Behavior

Generate axioms by applying each non-canonical operation to each canonical operation.

Canonical: new, ins
Non-canonical: rem, get, find, size, empty

26

27 of 31

Implementations of List

Two main approaches for implementing List

Storing elements in an array.
Resizing the array as needed.

Storing elements in a “linked list”

Create a “node” structure for each element with two parts:

Element stored at this node.
Reference to node of the next element in the list.

List has a reference to the first node and keeps track of the overall size.

27

28 of 31

List<T>

List

Interface definition
Note how placeholder “T” is used for type of element.

When we use List, we will provide a specific type for T
Same idea for when we write a class that implements List<T>

Some methods have multiple forms

This is called “method overloading”.
Different forms are distinguished by differences in the number and/or types of parameters required.

28

29 of 31

Concrete Implementation of List

Strategy:

Use an array of Object to store elements.
Start with an array of some initial size.
Unfortunately, can’t use type placeholder for arrays.

T[] my_array = new T[size]; // Can’t do this.

Remember Object is the universal reference type

Everything has an is-a relationship with Object.
So an array of Object can store anything.
Object[] my_array = new Object[size]; // Can do this.
my_array[index] = t_obj; // t_obj is of type T

Keep track of size of list.

Tells us which indices in underlying array are being used.

Resize array to be bigger as needed.

29

30 of 31

Linked List

Another strategy for implementing List
Define a “node” abstraction.

Two parts to a node
Value : The thing stored in this node.
Next node : A reference to another node.

null indicates that there is no next node.

Using the node abstraction, implement List

Keep track of size like we did with our array-based implementation.
Store a reference to the “head” of the list.

The first element in the list.
If list is empty, head is just null.

To get to a particular element in the list

Start at the head and “walk” from one node to the next keeping track of how many you have visited to which index you are at.

30

31 of 31

Array List vs. Linked List on the Heap

31