Design and Analysis of Algorithms Certification — Questions and Answers

Question 1: A social network wants to suggest friends-of-friends. Which algorithm best identifies second-degree connections?

Huffman Coding
Quicksort
Binary Insertion Sort
Breadth-First Search (Correct answer)

Correct answer: Breadth-First Search

BFS explores one hop (direct friends) then two hops (friends-of-friends) from a starting node.

Question 2: What is the time complexity of the classic 0/1 Knapsack DP solution with n items and capacity W?

O(n + W)
O(nW) (Correct answer)
O(n log W)
O(n²)

Correct answer: O(nW)

The 0/1 Knapsack DP fills an n×W table where each cell takes O(1) time, giving O(nW) overall complexity.

Question 3: How do Algorithms professionals contribute to advancing their field?

By competing with colleagues
By maintaining current practices
Individual contribution is not possible
By conducting research, sharing outcomes, mentoring others, and participating in professional forums (Correct answer)

Correct answer: By conducting research, sharing outcomes, mentoring others, and participating in professional forums

This is fundamental to Algorithms practice. By conducting research, sharing outcomes, mentoring others, and participating in professional forums represents the professional standard for research in the Algorithms certification framework.

Question 4: What is memoization in the context of dynamic programming?

Caching results of subproblems to avoid redundant computation (Correct answer)
Converting recursion to iteration
Splitting the problem into independent parts
Sorting subproblems before solving

Correct answer: Caching results of subproblems to avoid redundant computation

Memoization stores the result of each subproblem the first time it is solved so future calls return the cached answer immediately.

Question 5: Matrix Chain Multiplication DP minimizes what?

Total number of scalar multiplications (Correct answer)
Number of matrix additions
Memory used during multiplication
Number of matrices multiplied

Correct answer: Total number of scalar multiplications

Matrix Chain Multiplication finds the optimal parenthesization that minimizes the total number of scalar multiplications when multiplying a chain of matrices.

Question 6: In the context of graph algorithms, what is a topological sort?

Finding the shortest path in a DAG
A linear ordering of vertices such that for every directed edge (u,v), u comes before v (Correct answer)
Sorting edges by weight in a directed graph
Sorting graph vertices by degree

Correct answer: A linear ordering of vertices such that for every directed edge (u,v), u comes before v

Topological sort produces a linear ordering where every directed edge points from earlier to later in the sequence.

Question 7: Which principle best describes why an algorithm professional should prefer a well-known algorithm over a custom solution when both solve the problem equally well?

Known algorithms have documented complexity, edge cases, and community review (Correct answer)
Custom algorithms are always slower
Standard algorithms require fewer lines of code
Custom solutions violate most software licenses

Correct answer: Known algorithms have documented complexity, edge cases, and community review

Established algorithms come with proven correctness proofs, known edge cases, and peer-reviewed complexity guarantees that reduce professional risk.

Question 8: What is the value of written documentation in Algorithms professional communication?

It is only for formal occasions
It creates permanent records, ensures clarity, and provides legal protection (Correct answer)
It replaces verbal communication
It is optional

Correct answer: It creates permanent records, ensures clarity, and provides legal protection

This is fundamental to Algorithms practice. It creates permanent records, ensures clarity, and provides legal protection represents the professional standard for communication in the Algorithms certification framework.

Question 9: An engineer proposes using a heuristic to solve an NP-hard optimization problem. What professional obligation must accompany this proposal?

Prove the heuristic achieves optimal solutions
Avoid heuristics entirely in professional settings
Quantify the approximation ratio or solution quality bounds, and document when the heuristic may fail (Correct answer)
Only propose heuristics if the optimal algorithm is known

Correct answer: Quantify the approximation ratio or solution quality bounds, and document when the heuristic may fail

Professional use of heuristics requires honest disclosure of quality guarantees and known failure modes so stakeholders can make informed decisions.

Question 10: A web crawler must visit billions of URLs without revisiting any. Which data structure most efficiently tracks visited URLs with minimal memory?

Array of all visited URLs
Bloom filter (Correct answer)
Max-heap of URL hashes
Balanced BST of URLs

Correct answer: Bloom filter

A Bloom filter uses multiple hash functions and a compact bit array to answer membership queries in O(1) with minimal memory, accepting a small false-positive rate.

Question 11: A database executes a JOIN between two tables. Which algorithmic technique improves performance when both tables are already sorted on the join key?

Nested loop join
Merge join (Correct answer)
Radix join
Hash join

Correct answer: Merge join

Merge join exploits sorted order to scan both tables linearly, achieving O(n + m) instead of O(n x m).

Question 12: Which DP variant fills the table in a specific order to avoid computing subproblems before their dependencies are ready?

Tabulation (bottom-up) (Correct answer)
Greedy Fill
Divide and Conquer
Memoization (top-down)

Correct answer: Tabulation (bottom-up)

Tabulation (bottom-up DP) explicitly fills the table from base cases upward, ensuring all dependencies are computed before they are needed.

Question 13: What is the Rod Cutting problem in DP?

Sorting rod lengths optimally
Finding the shortest rod path in a graph
Minimizing waste when cutting material
Maximizing revenue by cutting a rod into pieces with given prices (Correct answer)

Correct answer: Maximizing revenue by cutting a rod into pieces with given prices

Rod Cutting determines how to cut a rod of length n into pieces to maximize total revenue, given a price table for each possible length.

Question 14: Which DP problem asks for the length of the longest subsequence common to two strings?

Coin Change
Longest Increasing Subsequence
Longest Common Subsequence (Correct answer)
Edit Distance

Correct answer: Longest Common Subsequence

The Longest Common Subsequence (LCS) problem finds the longest sequence present in both strings in the same order, solved in O(mn) by DP.

Question 15: Isn't it true that algorithms are only used in computers?

B) True
A) False (Correct answer)

Correct answer: A) False

Algorithms are not exclusively used in computers; they are fundamental to problem-solving in many aspects of daily life. Examples include recipes, assembly instructions for furniture, or even a set of directions to a location. Computers merely automate the execution of these step-by-step procedures, but the underlying logic is universally applicable.

Question 16: Under HIPAA, when is it permissible to use patient data to train a clinical prediction algorithm without individual consent?

When the data is de-identified according to HIPAA standards (Correct answer)
Never — all uses require explicit consent
When the algorithm is only used internally
When the hospital owns the data

Correct answer: When the data is de-identified according to HIPAA standards

HIPAA permits use of de-identified health information without authorization because it no longer constitutes protected health information (PHI).

Question 17: What is the space complexity of the standard LCS DP solution, and how can it be optimized?

O(1); already optimal
O(mn); optimized to O(min(m,n)) using two rows (Correct answer)
O(mn²); optimized to O(mn)
O(m+n); no optimization possible

Correct answer: O(mn); optimized to O(min(m,n)) using two rows

Standard LCS uses an O(mn) table, but since each row only depends on the previous row, it can be reduced to O(min(m,n)) space.

Question 18: Which test double returns hardcoded responses and makes no assertions about how it is called?

Fake
Mock
Spy
Stub (Correct answer)

Correct answer: Stub

A stub provides fixed, pre-programmed responses to calls made during a test but does not verify whether or how it was called.

Question 19: What is the time complexity of BFS on a graph with V vertices and E edges?

O(E log V)
O(V + E) (Correct answer)
O(V log V)
O(V²)

Correct answer: O(V + E)

BFS visits each vertex and each edge at most once, giving O(V + E) time complexity.

Question 20: What does the professional principle of 'algorithmic transparency' require in an AI or ML system context?

Publishing source code under an open-source license
Being able to explain how the algorithm produces its outputs, especially for high-stakes decisions (Correct answer)
Using only linear algorithms for interpretability
Avoiding all probabilistic methods

Correct answer: Being able to explain how the algorithm produces its outputs, especially for high-stakes decisions

Algorithmic transparency means stakeholders can understand, audit, and challenge how decisions are made, which is a professional and ethical obligation in consequential systems.

Question 21: A spell checker suggests corrections for a misspelled word by finding dictionary words with the fewest character edits. Which algorithm computes this?

Kruskal's algorithm
Longest Common Subsequence
KMP string matching
Edit distance (Levenshtein distance) via dynamic programming (Correct answer)

Correct answer: Edit distance (Levenshtein distance) via dynamic programming

Levenshtein distance uses DP to count the minimum insertions, deletions, and substitutions to transform one string into another.

Question 22: In a sorted array, if you double the number of elements, how many additional steps does Binary Search need?

2 more steps
n more steps
log n more steps
1 more step (Correct answer)

Correct answer: 1 more step

Doubling the array size increases Binary Search steps by exactly 1 because log₂(2n) = log₂(n) + 1.

Question 23: A genomics tool aligns a short DNA read against a reference genome of 3 billion bases. Which algorithmic technique makes this feasible?

DFS over the genome graph
Bubble sort then binary search
BWT/FM-index allowing near O(m) lookup (Correct answer)
Naive string search O(nm)

Correct answer: BWT/FM-index allowing near O(m) lookup

The Burrows-Wheeler Transform with an FM-index compresses the genome and allows extremely fast pattern matching, used in tools like BWA.

Question 24: Which of the following best describes a greedy algorithm?

It makes the locally optimal choice at each step hoping to reach a global optimum (Correct answer)
It exhaustively searches all possible solutions
It always backtracks to find the globally optimal solution
It divides the problem into equal halves and solves recursively

Correct answer: It makes the locally optimal choice at each step hoping to reach a global optimum

Greedy algorithms make the best local choice at each step without reconsidering previous decisions.

Question 25: A machine learning pipeline needs to split a dataset into training and test sets while ensuring the class distribution is preserved. The correct technique is:

Random permutation ignoring class labels
Merge sort by label then split
Stratified sampling (Correct answer)
Reservoir sampling

Correct answer: Stratified sampling

Stratified sampling partitions by class first and samples proportionally from each partition, preserving the original class distribution.

Question 26: How do continuing education requirements benefit Algorithms certified professionals?

They reduce practical skills
They ensure professionals stay current with evolving industry practices and knowledge (Correct answer)
They are unnecessary formalities
They only benefit training providers

Correct answer: They ensure professionals stay current with evolving industry practices and knowledge

This is fundamental to Algorithms practice. They ensure professionals stay current with evolving industry practices and knowledge represents the professional standard for professional standards in the Algorithms certification framework.

Question 27: In mutation testing, what is a 'surviving mutant' an indicator of?

A high-performance optimization
A passing edge-case test
A code change not caught by any test, revealing a test gap (Correct answer)
A bug that was successfully fixed

Correct answer: A code change not caught by any test, revealing a test gap

A surviving mutant means the test suite failed to detect an injected code defect, exposing a gap in test coverage or assertion strength.

Question 28: A web browser maintains a Back button history. Pressing Back retrieves the previous page. Which abstract data type models this?

Priority Queue
Deque
Queue
Stack (Correct answer)

Correct answer: Stack

A stack's LIFO (last-in, first-out) behavior perfectly models browser history where the most recently visited page is retrieved first.

Design and Analysis of Algorithms Certification

Assesses knowledge of algorithm design, analysis, and implementation covering sorting, searching, dynamic programming, graph algorithms, and computational complexity. Validates competency in applying algorithmic thinking to solve real-world computational problems.

Questions

35 min

Time Limit

80%

To Pass

Checking for saved progress...

Exam Rules

You can skip questions and return to them later
Flag questions for review before submitting
No feedback shown until you submit the entire exam
Unanswered questions count as wrong — answer everything
10 pretest questions are mixed in and don't affect your score
Timer auto-submits when time runs out
Your progress is auto-saved every 30 seconds