Asymptotic Complexity
Give the Asymptotic complexity of the following:
f(n) = 6n^3
theta(n^3)
True or False: In hashing, a collision occurs when two distinct keys are mapped to the same hash value.
True: A collision occurs when two distinct keys are mapped to the same hash value in hashing.
Define a graph and its components (vertices and edges):
A graph G is a mathematical structure consisting of a set of vertices (nodes) V and a set of edges E, where each edge connects two vertices. The edges may be directed or undirected, and they may have weights assigned to them.
What is P
Polynomial time are those that can be solved by algorithms whose worst-case running time is polynomial in the size of the inputs.
- Easily Solvable
True or False: The weight of a minimum spanning tree is always less than or equal to the weight of any other spanning tree in the same graph.
True
Give the Asymptotic Complexity of the following:
f(n) = (6n^3 + 20n^4 +8)^2
theta(n^8)
For this recurrence relation problem would you use a recursion tree or substitution:
T(n) = cn^2 + T(n/3) + T(n/sqrt2)
What is a recursive tree?
Define the shortest path problem and its variants:
What is NP
Nondeterministic polynomial time are those for which a given solution can be verified quickly(if a solution is correct), but finding the solution is harder.
- Easily Checkable
True or False: Every connected graph has a unique minimum spanning tree.
False: While every connected graph has at least one minimum spanning tree, it may have multiple minimum spanning trees if there are edges with the same weight.
Give the Asymptotic Complexity of the following:
f(n) = 6 * 4^n + 8 * 2^n+8 +10
theta(4^n)
True or False: Hashing guarantees constant-time insertion, deletion, and search operations.
False: While hashing provides average constant-time insertion, deletion, and search operations, in the worst case, these operations can take O(n) time due to collisions.
Discuss algorithms for finding shortest paths, such as Dijkstra's algorithm:
Dijkstra's algorithm: Finds the shortest path from a single source vertex to all other vertices in a non-negative weighted graph. It maintains a priority queue of vertices based on their tentative distances from the source.
True or False: The Traveling Salesman Problem (TSP) is an example of an NP-complete problem.
True: The Traveling Salesman Problem (TSP) is indeed an example of an NP-complete problem.
True or False: Prim's algorithm can be implemented using either a priority queue or an array-based approach to select the next edge to add to the spanning tree.
True: Prim's algorithm can be implemented using either a priority queue or an array-based approach to select the next edge to add to the spanning tree.
Rank these from highest complexity to lowest:
theta(n^2)
theta(n^n)
theta(n^0.3)
theta(nlog(n))
theta(n!)
theta(n)
theta(n^n)
theta(n!)
theta(n^2)
theta(nlog(n))
theta(n)
theta(n^0.3)
True or False: In a max-heap, the value of each node is greater than or equal to the values of its children.
True: In a max-heap, the value of each node is greater than or equal to the values of its children.
True or False: Dijkstra's algorithm can be used to find the shortest path in a graph with negative edge weights.
False: Dijkstra's algorithm cannot handle negative edge weights. It assumes all edge weights are non-negative.
What is the difference between a problem being in NP and being NP-complete?
Difference between NP and NP-complete: NP refers to the class of decision problems for which a solution can be verified in polynomial time. NP-complete refers to a subset of NP problems to which all other problems in NP can be polynomially reduced.
True or False: If all edge weights in a graph are distinct, then the minimum spanning tree of that graph is unique.
True: If all edge weights in a graph are distinct, then the minimum spanning tree of that graph is unique.
Give the asymptotic complexity of the following:
f(n) = 2 log₂((2n^2 +8) log₂(8n^2 +10)
theta (log(n))
True or False: Heapsort is an in-place sorting algorithm that has a worst-case time complexity of O(nlogn).
True: Heapsort is an in-place sorting algorithm with a worst-case time complexity of O(nlogn), making it efficient for sorting large datasets.
True or False: Dijkstra's algorithm guarantees finding the shortest path from the source vertex to all other vertices in the graph.
True: Dijkstra's algorithm guarantees finding the shortest path from the source vertex to all other vertices in the graph, provided the graph has non-negative edge weights.
Define the concept of polynomial-time reduction and explain how it is used to show NP-completeness.
Definition of polynomial-time reduction: Polynomial-time reduction is a technique used to show that one problem is at least as hard as another. If problem A can be reduced to problem B in polynomial time, and B is NP-complete, then A is also NP-complete.
True or False: For any weighted connected graph, if we remove the maximum-weight edge from any cycle in the graph, the resulting graph must have the same minimum spanning tree as the original graph.
True:Removing the maximum-weight edge from any cycle in a weighted connected graph preserves the graph's connectivity while ensuring that the minimum spanning tree remains unchanged, as the removed edge cannot be part of any minimum spanning tree.