411
What is the bisection bandwidth of a ring?
What is the time complexity of selection sort?
O(n^2)
Who is the best CS professor?
Our goat Larry Herman
What does it mean if sets A and B are disjoint?
They don't have elements in common
What is map(fun x -> x*4) [1;2;3]
[4;8;12]
What is the AMAT of a 4-way set associative TLB with an access time of 8 cycles, a page access translation that takes 100 cycles, and a hit rate of 20%? (Can leave unsimplified).
8 + 0.8 * 100
Describe the best case (time complexity) for heap sort and also give the time complexity
The nodes are all the same, O(n)
What is the name of the application TA's use for office hours?
Docket
What is ∼ (p∨q)?
(~p) ^ (~q)
Which fold method utilizes tail recursion?
fold_left
How do you avoid aliasing when using VIPT?
Cache Size <= page size * associativity
What is the goal of Floyd's Algorithm? (Floyd-Warshall)
It finds the least-weight path between each pair of vertices in a directed, weighted, simple, connected graph
How old is Kruskal?
70 years old
If set A has n elements, how many elements does its power set have?
2^n
What does the regex "e?" represent?
exactly zero or one e
When using Node IDs instead of 1 bit per core for reducing directory overhead, what is the inequality you want to satisfy?
N * log(P) < P
What is the definition of the set NP?
The set NP is the set of decision problems such that there exists a polytime algorithm on a NTM which takes an input/instance I and: Q(I) = Yes, Q(I) = No
What is the University of Maryland CS ranking according to USNews?
16th
What is the formula for the permutation of n items of k types?
n! / (n1! * n2! * .. * nk!)
Does this function type check?
fn f(n:[u32]) -> u32 {
n[0]
}
No (array length is not known. Need to fill in len)
What is the Iron Law?
CPU time = instruction count * cycles per instruction * clock cycle time
Radix sort:
312 321 633 313 623 223 213
213 223 312 313 321 623 633
What is the course number for Operating Systems?
CMSC412
How many bits does a full adder add?
3
What is Church's encoding for true?
lambda x. lambda y. x