What is the comparison sorting lower bound?
A O(1)
B Omega of log n
C Omega of n log n
D O(n squared) minimum
Answer: C. Omega of n log n. Comparison sorts require order n log n comparisons in the general case.
Why is comparison sorting lower bounded by n log n?
A Arrays cannot be indexed
B Every key must be hashed
C Input must be copied twice
D Decision tree needs many leaves
Answer: D. Decision tree needs many leaves. A comparison decision tree must distinguish among n factorial possible orders.
What does counting sort use to order values?
A Pairwise comparisons only
B Graph traversals
C Frequency counts
D Recursive pivots
Answer: C. Frequency counts. Counting sort counts occurrences of keys in a bounded integer range.
What does radix sort process repeatedly?
A Digits or key positions
B Array halves only
C Hash buckets by collision
D Edges by weight
Answer: A. Digits or key positions. Radix sort orders keys across digit positions using a stable subroutine.
What assumption often supports counting sort?
A Keys are arbitrary objects
B Small integer key range
C Input is a graph
D Every value is unique
Answer: B. Small integer key range. Counting sort is efficient when the key range is not too large relative to input size.
What does bucket sort distribute values into?
A Tree rotations
B Value ranges
C Graph components
D String prefixes
Answer: B. Value ranges. Bucket sort distributes keys into buckets based on their value ranges.
What is a binary search lower bound operation?
A Last array value always
B Middle value only
C First duplicate in any list
D First value at least key
Answer: D. First value at least key. A lower bound finds the first position whose value is at least the target.
What is quickselect used to find?
A Every sorted element
B Shortest graph path
C Element of a given rank
D Common string prefix
Answer: C. Element of a given rank. Quickselect partitions data to select a ranked element without fully sorting.
What is randomized quickselect's expected time?
A O(n)
B O(n log n)
C O(log n)
D O(n squared) always
Answer: A. O(n). Random pivots give linear expected work for selection.
What does KMP use to avoid repeated matching work?
A Heap ordering
B Hash load factor
C Prefix function
D Graph indegrees
Answer: C. Prefix function. KMP uses prefix information to shift the pattern after a mismatch.
What does Rabin Karp compare for pattern search?
A Tree heights
B Rolling hashes
C Graph cuts
D Sorted indices
Answer: B. Rolling hashes. Rabin Karp uses rolling hashes to screen candidate text windows.
What is a trie useful for?
A Prefix based string lookup
B Minimum spanning trees
C Numeric heap extraction
D Sorting arbitrary records
Answer: A. Prefix based string lookup. Tries organize strings by characters or symbols along shared prefixes.
What does a perfect hash function provide for a fixed key set?
A No collisions among those keys
B Constant worst case sorting
C Negative lookup always
D A sorted array automatically
Answer: A. No collisions among those keys. A perfect hash maps a fixed key set to distinct table locations.
What is an approximation algorithm for?
A Only array indexing
B Exact string matching
C Reading source code
D Hard optimization problems
Answer: D. Hard optimization problems. Approximation algorithms return near optimal answers with a bound for difficult optimization tasks.
What does an approximation ratio compare?
A Input length to memory only
B Algorithm value to optimum
C Runtime to processor clock
D Hash keys to buckets
Answer: B. Algorithm value to optimum. An approximation ratio quantifies how close a solution is to the optimum.
What is class P informally?
A Problems with no algorithms
B Only sorting problems
C Problems requiring exponential time
D Problems solvable in polynomial time
Answer: D. Problems solvable in polynomial time. P contains decision problems solvable in polynomial time by a deterministic algorithm.
What is class NP informally?
A Problems never decidable
B Only graph problems
C Solutions verifiable in polynomial time
D Algorithms using no memory
Answer: C. Solutions verifiable in polynomial time. For NP, a proposed solution can be checked in polynomial time.
What makes a problem NP complete?
A Only solvable by recursion
B In NP and NP hard
C Always has linear algorithm
D Cannot be verified efficiently
Answer: B. In NP and NP hard. NP complete problems are in NP and are at least as hard as every NP problem under reductions.
What does an NP hard problem require?
A Membership in P
B At least NP complete difficulty
C A sorted input
D A constant time solution
Answer: B. At least NP complete difficulty. NP hard problems are at least as difficult as NP problems; they need not belong to NP.
What is a polynomial time reduction used for?
A Sort one input array
B Balance a search tree
C Count hash collisions
D Relate problem difficulty
Answer: D. Relate problem difficulty. A reduction transforms instances to compare the computational difficulty of problems.
What is an online algorithm?
A Makes decisions as input arrives
B Requires all input first
C Always uses random choices
D Only sorts a static array
Answer: A. Makes decisions as input arrives. An online algorithm must act without seeing future input.
What is a streaming algorithm designed for?
A Process data in limited memory
B Store every input item
C Sort all possible records
D Build a full graph matrix
Answer: A. Process data in limited memory. Streaming algorithms process data sequentially while keeping small summaries.
What does parallel speedup compare?
A Memory use to input length
B Two sorting outputs
C Serial time to parallel time
D Hash capacity to load factor
Answer: C. Serial time to parallel time. Speedup is the serial execution time divided by parallel execution time.
What limits ideal parallel speedup in Amdahl's law?
A Number of array indexes
B Input alphabet size
C Hash function choice
D Serial fraction of work
Answer: D. Serial fraction of work. The portion that cannot run in parallel limits total speedup.
What does an algorithm invariant help establish?
A Correctness across steps
B A faster processor clock
C A smaller source file
D A sorted input requirement
Answer: A. Correctness across steps. An invariant is a property maintained through execution and used in correctness proofs.