BCA Cyber Security Algorithms — practice questions
66 free MCQs with worked solutions. Tap any question for the answer + explanation, or practice them all in the app.
Practice BCA Cyber Security Algorithms in the app →Which is NOT a limitation of experimental timing studies of algorithms listed in the lecture?Per the lecture, an algorithm is best described asMathematical analysis of an algorithm replaces the stopwatch withPer the lecture, which of these is NOT counted as a single primitive operation?A nested loop runs the inner body `n` times for each of `n` outer iterations, with constant work per inner iteFor `for i = 1 to n: sum = sum + i`, the total operation count is approximatelyWorst-case running time of an algorithm on input size n isLinear search over n elements for key x has best-case and worst-case running times ofWhy does GATE-style algorithm analysis usually use worst case rather than average case?f(n) is in O(g(n)) means there exist constants c > 0 and n_0 ≥ 0 such that for all n ≥ n_0,f(n) = 3n² + 5n + 8 is inFrom slowest to fastest growth for large n, the correct order isPer the lecture, the worst-case lower bound on the number of comparisons made by any comparison-based sort on Why does pre-sorting data pay off in practice?Non-comparison sorts like counting / radix / bucket can run in O(n) becauseThe recurrence relation for merge sort's running time isMerging two already-sorted arrays of total size n takesA sorting algorithm is called STABLE ifStandard quick sort with the first element as pivot has worst caseRandomised quick sort improves on plain quick sort becauseCompared to merge sort, standard quick sort isRadix sort can sort n integers in O(n) time despite the Ω(n log n) lower bound becauseCounting sort runs inIf you need a sort that gives a Θ(n log n) worst-case guarantee AND preserves the order of equal-keyed elementThe generic divide-and-conquer recurrence, with `a` sub-problems of size `n/b` and divide+combine work `g(n)`,The three classical steps of any divide-and-conquer algorithm areWhy does every recursive divide-and-conquer algorithm need an explicit base case?Karatsuba's recurrence for n-digit multiplication isThe recurrence T(n) = T(n/2) + O(1) for binary search solves toPer the lecture, Strassen's algorithm for n×n matrix multiplication obeysThe recurrence T(n) = 2T(n/2) + 2 with T(1) = c solves by iteration toIn the iterative solution to T(n) = a·T(n/b) + Θ(n^d), if a < b^d, the dominant work is atIteratively unrolling T(n) = T(n/2) + c, the total work after reaching T(1) isPer the Master Theorem, the three cases for T(n) = a · T(n/b) + c n^d are decided by comparingApplying the Master Theorem to merge sort, T(n) = 2T(n/2) + n, the matching case and result areWhich recurrence is the Master Theorem (as stated) NOT able to solve?A problem can be solved correctly by a greedy algorithm when it exhibitsThe defining feature of a greedy algorithm is that itCompared to dynamic programming, greedy algorithms areAny spanning tree of a graph with |V| vertices has how many edges?The cut property of MSTs states that, for any cut of the graph,If you remove an edge (u, v) from an MST T, the two resulting sub-treesKruskal's algorithm builds the MST byThe running time of Kruskal's algorithm with Union-Find isWhen Kruskal considers edge (u, v) and `find(u) == find(v)`, the algorithmPrim's algorithm grows the MST byPrim's algorithm with a Fibonacci heap runs inPer the lecture's guidance, choose Kruskal over Prim whenPer the lecture, dynamic programming applies to problems that haveBottom-up dynamic programming (tabulation) differs from top-down memoisation in thatPer the lecture, dynamic programming differs from divide and conquer becausePer the standard DP solution for LCS of two strings of length m and n, the running time isIf the last characters of strings X and Y are equal, LCS recurrence saysIf only the LCS LENGTH is needed (not the actual subsequence string), the DP table can be stored inThe 0/1 knapsack recurrence (max value using first i items, capacity c) isWhy does the value/weight ratio greedy strategy not always solve 0/1 knapsack optimally?The DP for 0/1 knapsack runs in O(nW). Why is this called pseudo-polynomial rather than polynomial?The standard DP solution for matrix-chain multiplication runs inMultiplying A(10×100) · B(100×5) · C(5×50): the cost difference between (AB)C and A(BC) isThe number of distinct parenthesisations of n matrices isBFS finds the shortest path from a source in an unweighted graph becauseOn a sparse graph (E far less than V²), the adjacency list representationChoose BFS over DFS whenDijkstra's algorithm requires thatThe 'relax' operation on edge (u, v) with weight w updates d[v] whenDijkstra's algorithm using a binary min-heap runs in