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 |
|
|
Polymorphism? |
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 |
|
|
Interface |
-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 |
|
|
Bag ADT -properties |
-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 |
advantages -allows direct access to individual items by index #, to allow binary search
drawbacks -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: 1)data 2) location of next piece - allows access to each item in list -this is a self-referential data type
advantages -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 |
Array -Copy data from last index into the index of the item you want to remove, and then remove the last index
Node -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? -operations |
-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 -types |
*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 -requirements |
Problem is broken down into smaller problems which are identical in nature to original problem
Requires: 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 |
benefits -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
drawbacks -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 |
