Practice General Problem (4.1) - Longest Common Subsequence - Design & Analysis of Algorithms - Vol 3

Practice: General Problem

Lesson 4.1Longest Common Subsequence

Practise this section

9 questions

Flashcard drill
3 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
Define the longest common subsequence (LCS).
Show hintHide hint
Break down the definition into parts: 'longest', 'subsequence', and 'order'.
Question 2.
What does dynamic programming help with in problem-solving?
Show hintHide hint
Think of a way to avoid calculating the same thing multiple times.
3Question 3.
What strategy does LCS utilize to find similarities between sequences?
- Exact matching
- Dropping letters
- Random selection
Show hintHide hint
Consider the goal of finding the longest match, not just short ones.
4Question 4.
True or False: LCS can only be applied to genetic sequences.
- True
- False
Show hintHide hint
Think broadly about how LCS might be useful in texts or sentences.
Question 5.
Given the sequences 'AGGTAB' and 'GXTXAYB', compute the LCS and explain how to arrive at your answer.
Show hintHide hint
Visualize a grid; track matching characters and build on previous results.
Question 6.
Critique the efficiency of LCS utilizing brute force versus dynamic programming.
Show hintHide hint
Understand the relation between the size of input and the number of calculations involved.

5 more questions in this section. Enroll free to practise them all.