CSCE4110 - Exam 1 Flashcards
What is an algorithm
a step-by-step procedure for solving a problem or accomplishing some end
statement is true prior to the first iteration
initialization
if it is true before the iteration of the loop it remains true before the next iteration
maintenance
is true at the end of the loop
termination
j=2, therefore A[i:j-1] is A[1], single element=>sorted
initialization
we move elements until proper position of a[j] is found. therefore if a[1:j-1] is sorted after iteration j A[1:j] is sorted
maintenance
ends when j=n+1; therefore based on maintenance criteria A[1:n] is sorted
termination
time complexity of merge sort
theta(n log n)
how to get time complexity of merge sort
split each node by 1/2 and there are log(n)+1 levels
max-heap: parent
floor( i / 2 )
max-heap: left
2(i)
max-heap: right
2(i) + 1
counting sort
one array of the input, one array of indexing each value, one array of input frequency
radix sort
start sorting with least significant digit
bucket sort
sort numbers into linked list based on first digit
counting sort assumption
maximum value in list is not especially large
radix sort assumption
d is significantly less than log(n)
bucket sort assumption
input is uniformly distributed
worst case time complexity of hash tables
O(n)
average case time complexity of hash tables
O(1)
chaining hash tables
put elements with same hash value into linked list
properties of good hash function
satisfies assumption of simple uniform hashing
derives hash values independent of any patterns in the data
open addressing hash tables
does not use linked list, in event of collision probe until open slot is found
when should hash tables be used
where direct addressing is inefficient
preorder traversal
dot left of node
inorder traversal
dot bottom of node
postorder traversal
dot right of node
role of T.nil
ensures that every leaf is black
if node is red…
both children are black
the root of a red black tree is
black
for each node, all paths from the node to descendant leaves…
contain the same number of black nodes
three advantages of red black trees
ensures some degree of balance
height is guaranteed O(log n)
rotations done in constant time
two key conditions for dynamic programming (greedy algorithms)
optimal substructure
overlapping subproblems
dynamic programming often uses
memorization
optimal substructure is
when an optimal solution contains optimal solutions to subproblems
overlapping subproblems is
recursive algorithms, records subproblems solutions for future use
Longest common subsequence is often used in
genome sequencing
