test 1 - comp 228

an abstract data type is...

set of values
set of operations that can be performed by these values
specific representation in memory

ADT Logical Level

The use of an ADT to solve a problem. Applicationcode that uses an ADT only needs to know how tocreate instances of the ADT and invoke its operations.

Interface Level

The set of operations that can be used at the logical level to add, remove and access the data maintained in an ADT.

Implementation Level

A specific representation of the data in memory and code that implements the ADT operations

two ways to use the term data structure

any collection of data organized is some fashion, the underlying data structure for a specific ADT implementation

big o bluf

bottom line up front

Big O Notation

gauge how long it takes to execute the algorithms we develop for operations, especially went considering alternative algorithms for a given operation

o(1)

bounded time (good) = execution time essentially the same regardless of how much is processed

o(log2N)

Logarithmic time; each step of the algorithm cuts the amount of work left in half

O(N)

linear time - a loop that is used that potentially processes each of the data elements

O(N log2 N)

n log n time - will do in a pinch some combination of divide and conquer with non-nested loop

O(N^2)

quadratic time - avoid - the nested loop structure is used

tretan

always starts by guessing 1 and adds 1 to his previous guess

Peleg

divides and conquers - start by guessing, 50 and guesses the middle of remaining range after eliminating numbers based on feedback

omega(f(n))

lower bound on execution time to execute an algorithm - best case

O(f(n))

worst case, f(n) an upper bound

Theta(f(n))

average - the time to execute an algorithm but also used for average

WHICH ASSESSMENT WILL BE THE MAIN DRIVER IN DECIDING BETWEEN TWO OR MORE ALGORITHMS THAT CAN BE USED FOR AN ADT OPERATION

big o

how to measure the time complexity of an algorithm

we count the number of basic operations required to complete the algorithm

Collection

An object that holds other objects.Typically we are interested in inserting, removing,and iterating through the contents of a collection

What is generics?

the capability to parameterize types.

What is the key benefit of generics?

to enable errors to be detected at compile time rather than at runtime.

generic class or method

permits you to specify allowable types of objects that the class or method may work with

Generic type

A placeholder for an object type that is not made concrete until the class that refers to it is instantiated. It represents any data type, not exclusive to string or int.

An ADT implementation is a class

that has a public method for each of theADT's operations

Java interface

used to to specify the methods that implement an ADT's operations and these methods are called by application-level code that uses our ADT class

A Java interface is similar to an abstract class

but we implement an interface vs. extendingan abstract superclass

A Java interface can include

abstract method signatures
static methods
default methods
constants
public abstract are default modifiers for methods

A Java interface doesn't include

instance variables:
public static final are the default, and only, modifiers for all attributes

What are references?

Are memory addresses

References are sometimes referred to...

links, addresses, or pointers

A variable of a reference type holds...

the address of the memory location that holds the value of the variable, rather than the value itself

sorted list

placed in a particular order

indexed list

A list in which each element has an index value associated with it

list ADT assumptions

lists are unboundedduplicates are allowedno nullsmake list easy to useminimal preconditions

sorted lists are sorted in increasing order defined by

compareTo

indices for indexed lists are

continguous

list iteration

one element at a time, from first element to the last

two versions of get operations

1. getI(element)
2.get(i) - index

Are string lists unbounded?

no, they are bounded

unbounded

limitless

bounded

limited

Does "remove" maintain insertion order?

no

Java interface is similar to an

abstract class

List ADT Operations

add, remove, size, isEmpty, contains, get

An ADT does not have a specific representation in memory but...

an ADT implementation does

HOW DO WE CREATE A LINK LIST?

Use a node object that includes an instance variable that is a reference to a node object

An ADT implementation that uses an array for its underlying data structure is generally considered

BOUNDED

An ADT implementation that uses a linked list for its underlying data structure is generally considered

unbounded

UNDERLYING DATA STRUCTURES FORADT IMPLEMENTATIONS

array and linked list

The maximum number of elements the ADT can hold is

the size of the array

Linked List

A linear data structure, much like an array, that consists of nodes, where each node contains data as well as a link to the next node, but that does not use contiguous memory.

The node object

Each node object holds a data element and has an attribute (instance variable) that is a reference to a node object

The next pointer

The value of a given node's next attribute points to the next node in the chain of nodes

The next in the last node of the chain is

null

The head

a separate reference variable that refers to the first node in the linked list

Any node in the linked list can be accessed by

starting at the head and following the chain of next pointers

The tail

Sometimes a reference to the last node in the linked list is maintained in addition to the head

DOUBLY LINKED LIST

a linked list in which each element has both forward and backward pointers.

helper method

A method of a class that is used by other methods in a class to help complete a task. Helper methods have access level private.