• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off

Card Range To Study



Play button


Play button




Click to flip

Use LEFT and RIGHT arrow keys to navigate between flashcards;

Use UP and DOWN arrow keys to flip the card;

H to show hint;

A reads text to speech;

30 Cards in this Set

  • Front
  • Back

Access restrictions of classes

-employed to hide implementation details from user, who only needs to know how to use class - data abstraction

1)public declarations through methods give object functionality & interface

2)private declarations hide implementation details

3)protected declarations allow access only within class, subclasses, & package

4) static declarations allow the sharing of a specific method/variable between all instances of the class, rather than separate for each instance

-property of the class, rather than instance

5) final declarations cannot allow assignment, overriding, or subclassing

Variable comparisons?

-difference between reference vs primitive type

Reference variables

- .equals() method compares data contents

- == operator compares memory location

-memory addresses can be assigned but not manipulated

Primitive variables

Use == operator


Memory allocation

-dynamic allocation of objects - exists indefinitely as long as active reference to object

-uses new operator

Making a new class

1)Composition/aggregation - use components from previously defined class, Has a relationship

-no special access to instance variable objects, just implements these methods

2)Inheritance - build new subclass by extending superclass, Is a relationship

-can only have superclass references for subclass objects


Allows superclass & subclass objects to be accessed in a regular, consistent way

-Using inheritance

-allows method overriding when same reference & identical method signature of subclass with superclass

-method associated w/ object, not reference, is executed

-dynamic binding allows code determined by type of object to be executed @ run-time

Abstract class

-gives cohesion to subclasses, while class is not actually implemented/instantiated

-subclasses must implement all abstract methods or be declared abstract

-gets around single inheritance implementation & allows access to object through this abstract reference


-named set of methods

-abstract class w/ no instance data

no static constant/methods allowed

-does not specify data, only specifies behaviors

-function & descriptions handled by comments

-no limit to how many can be implemented by a single class

-must use interface reference, allowing access of only interface methods

Comparable interface allows objects to be sorted

parametrized types

follows class name

-Object types are established & checked @ compile time rather than run-time to allow type checking @ compilation

parts of a data type

encapsulation of

1) data & its representation in memory - instance variables

2) operations to manipulate data - methods - what allows usefulness

abstract data types (ADT)

-how will they be implemented

-language-independent data type where functionality is separated from implementation

-implemented by classes - language-specific structures (can be by more than one class)

-ADTs are interfaces

-representation & implementation details of operations are abstracted out of view of user, but used by implementer

-users only need to know operations (functionality)

-represent collections of data to allow access & organization in specific way

Steps for planning specifications

1) Identifying purpose/effect in normal case, inferred from pre & postconditions

-Preconditions indicate state of ADT before method execution

-Postconditions indicate state of ADT after method execution

2) Identifying unusual cases & how to handle them

-throwing exceptions, returning false, not allowing the opportunity, etc



-Unlimited # of items

-Unspecified order

-Can have duplicates

-homogeneous type, but any type

Bag Array implementation

1)fixed size

2)dynamic resizing, making new array twice the size of old one

In both, physical size is parameter, while logical size is maintained by a counter variable

disadvantages - over-allocation & wasting memory

-uses contiguous memory - locations are next to each other

Advantages & disadvantages of contiguous memory


-allows direct access to individual items by index #, to allow binary search


-need to allocate memory all at once

-inserting/deleting data requires all other elements to be shifted if order matters

How does linked list work

collection of data is stored in small, separate pieces of memory

-each piece = node that has 2 parts:


2) location of next piece - allows access to each item in list

-this is a self-referential data type


-enables allocation of exact # of pieces needed

-shifting is not required for new elements

Variations of linked-list implementations

1) Singly linked list - one-direction

2) Doubly linked list

3) Circular linked list

Different Node implementations for LinkedBag?

1) Node as a private inner class - LinkedBag methods can access private declarations in Node

2) Node as a separate class in the same package - Node can be used outside of LinkedBag class by other LinkedBag classes in the same package

-doesn't violate private class & uses accessor & mutator methods to allow access, better for OOP

-must be parametrized type

Removing items in bag ADT


-Copy data from last index into the index of the item you want to remove, and then remove the last index


-Copy item in front node to target node you want removed

-Remove front node

*Linear run-time

*Returns true or false, not the item

What is a Stack?


-push, pop, peek at items on the top only

-last in first out

-array or linked list implementation

-array requires index decrementation

post-fix expressions

evaluated using stacks

operators follow operands - operations done on #s immediately to left

Measuring execution time of algorithms?

1) measuring empirically

2) asymptotic analysis before program is even written

-determine key instruction that controls run-time behavior (comparison of items, etc) - the run-time is directly proportional to the key instructions

-find formula/function for change in key instructions as problem size (N) increases

-simplify to order of magnitude to get Big-O run-time

How to measure order of magnitude/Big-O

-ignore lower order terms because they get less significant as problem size increases

-ignore constant multipliers b/c distinguish differences between programs, language, computer etc., rather than run-time

Types of run-time

1) Constant run-time - O(1)

-assignment, incrementation

2) Linear run-time - O(N)

-for loop

3) Quadratic run-time - O(N^2)

-nested for loops

Run-time of searches


*Key instruction is comparison

1) Sequential Search - O(N) - single while loop w/ up to N comparisons

2) Binary Search - O(log2N) - cut in half with each iteration, so N goes from 2^k to 2^0 = 1

Amortized time

Average time required over a sequence of operations

-individual operations vary, but this calculates average run-time, so total operations time/# of operations

What is recursion


Problem is broken down into smaller problems which are identical in nature to original problem


1) At least 1 base case where no recursion occurs

2) At least 1 recursive cases - algorithm defined in terms of itself

3) Recursive case leads to base case

Benefits & drawbacks of recursion


-approach to solve problems are more logical & easily understood

-useful when difficult to make iterative approach, such as in multiple recursion & backtracking

-easier to store multiple state information


-have overhead of:

1) space - AR takes up memory on RTS

2) Time - AR takes up time, slower than iterative algorithm

what is divide and conquer?

-solving problem by breaking it down into one or more smaller problems that are a fraction of the size but identical in nature to original problem, then using the solutions of these subproblems to make solution of original problem

what is tail recursion?

-recursive call is last statement in method call

-recursive algorithm is able to be converted into iterative algorithm

what is backtracking?

going forward until reach a point where no solution can be achieved, at which point, go back to a point where can take a different route