Algorithms · Algorithm Design Techniques
Official IIT answer key · IIT Kanpur · Audited Aug 2026
GATE CSE 2015 Set 3 Q49 · NAT · 2 marks
DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k - 1
do z ← z^2 mod n
if c[i] = 1
then z ← (z × a) mod n
return z
If k=4,c=⟨1,0,1,1⟩,a=2 and n=8, then the output of DOSOMETHING(c,a,n) is _________.Key concept
No account needed
Sit 5 related Algorithm Design TechniquesPYQs as a guest. We'll score the set and show which traps cost marks — sign in only if you want to save the run.
Topic notes
GATE tests algorithm design techniques through two primary styles: conceptual classification and mechanical algorithmic execution. At the 1-mark level, questions focus on matching standard classical algorithms (such as MST algorithms, shortest paths, and sorting algorithms) to their corresponding paradigms like Greedy, Dynamic Programming, Divide and Conquer, or Backtracking. At the 2-mark level, the focus shifts to quantitative problem solving, such as building a Huffman tree and computing the exact total or expected bit length for encoded messages.
Full Algorithm Design Techniques guide →Suppose c = c[0], ..., c[k - 1] is an array of length k, where all the entries are from the set \0, 1\. For any positive integers a and n, consider the following pseudocode. DOSOMETHING (c, a, n) z ← 1 for i ← 0 to k - 1 do z ← z2 mod n if c[i] = 1 then z ← (z × a) mod n return z If k = 4, c = 1, 0, 1, 1 , a = 2 and n = 8, then the output of DOSOMETHING(c, a, n) is …
Topic-wise GATE CS PYQs with verified steps
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.