Chapter 1 - 4 Flashcards
(26 cards)
Abstraction
The generic viewpoint of a system.
Abstract Data Type (ADT)
Data Type whose properties are specified independently
Application
User level. Solves the problem. Create instances
Abstract
What does the data type do?
Interface
Implementation
How the data type works.
Preconditions
Things needed for the methods to work
Postconditions
The results of the method
Benefits of using interfaces
Noticing syntactical errors,
alternate implementations
Polymorphism
An object that can be referenced with different classes
Stack
LIFO struture
Collection
An object that holds other objects
Exceptional Situations/Deviant Cases
Where a exception is thrown, where the case is not normal
Balanced Expressions
When the open and closed expressions are correctly matched
Self-referential class
a class that includes a reference to an object within of the same class
Three complexity cases
Best Case, Average Case, Worst Case
Best Case Complexity
The minimum number of steps required by an algorithm
Average Case Complexity
The average number of steps required by an algorithm
Worst Case Complexity
The maximum number of steps required by an algorithm
Complexity case used for analysis
Worst Case Complexity
O(1) Bounded Time
The amount of work is not dependent on the size of the problem
O(log2N) Logarithmic Time
Algorithms that cut the time in half each step
O(N) Linear Time
Number is proportional to the steps of N
(O)NLogN
repeating algorithm (same as Log multiplied by N)
(O)N^2 Quadric Time
nested for loops, multiple iterations within iterations
