Flashcards
Exam 1
Cards in this deck (28)
- 1Data type and examples- a name
- for a set of legal values
- and a set of operations
examples: int, short, byte, long, boolean, double, float, char
String, Object, List, Map, Stack, Queue⦠- 2abstract data type (ADT)a data type that has values and operations not defined in the language itself
- in Java an ADT is implemented using a class (abstract or not) or interface - 3A solution is said to be _________ if it solves the problem within its __________ _________. What are these?Efficient, resource constraints
- space
-time - 4The _____ of a solution is the amount of resources that the solution consumescost
- 5What is the cardinality of B ? B = {2, 3, 5, 7, 3, 2}4
- 6A = {3, 5} and B = {2, 3, 5, 7} Is A a subset of B and why? Is A a proper subset of B and why>A is a subset of B because every element in A is also in B. And A is a subset of B because every element in A is also in B.
- 7π΄={πππ, πππ’π, πππππ} π΅={π¦πππππ€, ππππππ, πππ, ππ’ππππ, πππππ} π΄βͺπ΅? π΄β©π΅? π΄βπ΅? π΅βπ΄?π΄βͺπ΅={πππ, πππ’π, πππππ, π¦πππππ€, ππππππ, ππ’ππππ}
π΄β©π΅={πππ, πππππ}
π΄βπ΅={πππ’π}
π΅βπ΄={π¦πππππ€, ππππππ, ππ’ππππ} - 8Seta collection of distinguishable elements
e.g. {3, 4, 5, 4} = {3, 4, 5} - 9Baga collection of elements with no order but with duplicates as a this
[3, 4, 5, 4] = [3, 4, 4, 5] β [3, 4, 5] - 10sequence (tuple, vector)is a collection of elements with an order which may or may not contain duplicates
<3, 5, 4, 4> β <3, 4, 5, 4> β <3, 4, 5> - 11R is a binary relation over S. How can it be reflexive, symmetric, antisymmetric, or transitive?R is reflexive if aRa for βaβS
R is symmetric if aRb => bRa for βa,bβS
R is antisymmetric if both aRb and bRa hold => a=b for βa,bβS
R is transitive if aRb and bRc => aRc for βa,b,cβS - 12What is an equivalence relatioEquivalence relation: R is reflexive, symmetric and transitive
- 13What is a partial order?R is reflexive and antisymmetric and transitive
- 14The time complexity of an algorithm depends on:the number of basic operations required by the algorithm to process an input of certain size
- 15basic operationan operation whose time to complete does not depend on the particular value of its operands
- e.g. adding two integers doesnβt depend on the values of the integers: 3+5 takes the same time as 73+8734 - 16when working with lists of values to search, sort etc., ____ is the number of elements processedsize
- 17The rate for which the cost of the algorithm grows as the size of the input ________grows
- 18asymptotic upper boundfor the growth of the algorithmβs runtime (highest possible growth rate of the algorithm, worst case) - Big-Oh Notation
- 19asymptotic lower boundfor the growth rate of the algorithm (least possible cost (usually time) required, best case) β Big-Omega Notation
- 20tightest bound- if the worst case Big-Oh and best case Big-Omega are the same within a constant factor (best of all the worst case runtimes) - Big-Theta Notation
- 21Main Memory Space/Time TradeoffYou can often reduce time by sacrificing space and vice versa (usually space/time changes are by a constant factor)
- 22Disk-based Space/Time TradeoffDisk operations (reads and writes are expensive compared to RAM) usually, the smaller you make the disk storage requirements the faster your program will run
- 23recurrence (or recurrence relation)an equation or inequality that describes a function in terms of its value on smaller inputs
- 24Setstore a group of non-duplicate elements
- 25Liststore an ordered* collection of elements
- 26Stackstore objects, process them LIFO
- 27Queuestore objects, process them FIFO
- 28Priority Queuestore objects, process them in order of priorities
Information
- Description
- Flashcards on Exam 1, created by Siah Thomas on 14/06/2023.
- Created by
- Siah Thomas
- Views
- 0
- Rating