COSC 2436 MIDTERM VERIFIED STUDY GUIDE
data structure - Answers - an organization of the data in a way so it can used efficiently
it is implemented an ADT
things to consider when selecting a data structure - Answers - number of data item
number of operations
processing speed
efficiency
two parts of data structure - Answers - interface (what the data structure can do)
implementation (actual definition of how the interface will do what we expect it to)
performance of data structure - Answers - implementation of the interface
(correctness)
run time of operation (time complexities)
memory usage (space complexities)
types of running time - Answers - worst-case - operation do not take longer than f(n)
amortized - cost of typical operation at most f(n)
expected - actual runtime
Big O - Answers - used to describe an algorithm's performance/execution time as input
grows to infinity
O(1) - Answers - constant time
O(N) - Answers - Linear time
O(n^2) - Answers - quadratic time
O(n^c) - Answers - polynomial time
O(c^n) - Answers - exponential time
O(log n) - Answers - logarithmic
List ADT - Answers - underlying data structure has no impact on the program's
execution.
List ADT implementation - Answers - array - constant time
linked list - linear time
Stack ADT - Answers - Collection of data together with operations
data structure - Answers - an organization of the data in a way so it can used efficiently
it is implemented an ADT
things to consider when selecting a data structure - Answers - number of data item
number of operations
processing speed
efficiency
two parts of data structure - Answers - interface (what the data structure can do)
implementation (actual definition of how the interface will do what we expect it to)
performance of data structure - Answers - implementation of the interface
(correctness)
run time of operation (time complexities)
memory usage (space complexities)
types of running time - Answers - worst-case - operation do not take longer than f(n)
amortized - cost of typical operation at most f(n)
expected - actual runtime
Big O - Answers - used to describe an algorithm's performance/execution time as input
grows to infinity
O(1) - Answers - constant time
O(N) - Answers - Linear time
O(n^2) - Answers - quadratic time
O(n^c) - Answers - polynomial time
O(c^n) - Answers - exponential time
O(log n) - Answers - logarithmic
List ADT - Answers - underlying data structure has no impact on the program's
execution.
List ADT implementation - Answers - array - constant time
linked list - linear time
Stack ADT - Answers - Collection of data together with operations