Problem Solving Techniques & Application Skills Flashcards
7 cards from real GATE practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Problem Solving Techniques & Application Skills flashcards as text
A salesperson visits 5 cities. The number of distinct routes visiting each city exactly once and returning to the starting city is:
Answer: 12
For n cities in TSP, the number of distinct tours (fixing start) is (n-1)!/2 = 4!/2 = 24/2 = 12.
If log₂(x) = 5, what is the value of x?
Answer: 32
log₂(x) = 5 means x = 2^5 = 32.
A hash table uses chaining for collision resolution. In the worst case, the time complexity of a search operation is:
Answer: O(n)
In the worst case, all n keys hash to the same slot, creating a single chain of length n, making search O(n).
A problem is in class NP if:
Answer: A proposed solution can be verified in polynomial time
NP (Nondeterministic Polynomial) contains problems for which a given solution (certificate) can be verified in polynomial time.
In a circular arrangement of 6 distinct people, how many distinct arrangements are possible?
Answer: 120
Circular permutations of n objects = (n-1)! = 5! = 120.
Which of the following best describes the time complexity of binary search on a sorted array of n elements?
Answer: O(log n)
Binary search halves the search space at each step, resulting in at most log₂(n) comparisons, giving O(log n) complexity.
A project has tasks A, B, C, D with durations 3, 2, 4, 1 days. B depends on A; C depends on A; D depends on B and C. What is the minimum project duration?
Answer: 8 days
Critical path: A(3) → C(4) → D(1) = 8 days, which is longer than A(3) → B(2) → D(1) = 6 days.