Longest Common Subsequence (LCS) Visualizer
Step 1: Access the Simulation
- Navigate to the simulation page from the main experiment interface
- The simulation loads with default example sequences "AGGTAB" and "GXTXAYB"
Step 2: Input Sequences
- Enter Sequence A in the first input field (e.g., "ABCDGH")
- Enter Sequence B in the second input field (e.g., "AEDFHR")
- Alternatively, use preset buttons for quick examples:
- Classic: "AGGTAB" vs "GXTXAYB"
- Match-heavy: "ABCDGH" vs "AEDFHR"
- Almost equal: "ABCDEF" vs "ABDFEF"
- Simple: "ABC" vs "AC"
Step 3: Select Algorithm
Choose one of three algorithms to visualize:
- Standard DP (O(n²) space): Shows complete DP table with backtracking
- Rolling Array (O(n) space): Uses only two rows, space-efficient
Step 4: Initialize the DP Table
- Click the Initialize button (or press Ctrl+I)
- Observe:
- Character boxes appear for both sequences
- Empty DP table structure is prepared
- Statistics update with sequence lengths
Step 5: Step Through Execution
- Click Step (or press Space/Enter) to execute one step
- Observe in each step:
- Character Comparison: Two characters are highlighted and compared
- DP Table Update: Corresponding cell in DP table updates
- Explanation: Step-by-step explanation appears in the left panel
Step 6: Auto-play Mode
- Click Play to run algorithm automatically
- Adjust speed using the slider (20ms to 1.5s per step)
- Click Pause to stop auto-play
Step 7: Trace Backtracking
- After DP table is filled, algorithm automatically switches to trace mode
- Watch the backtracking path highlight in yellow
- Observe how LCS is reconstructed character by character
Step 8: Reset and Experiment
- Click Reset to start over with new sequences
- Try different sequence combinations
- Compare different algorithms on the same sequences
Keyboard Shortcuts
- Space/Enter: Step forward
- Ctrl+P: Toggle Play/Pause
- Ctrl+I: Initialize
- Ctrl+R: Reset