Spaces:
Running
Running
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8"> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <title>Dynamic Programming - Algorithm Animator</title> | |
| <link rel="icon" type="image/x-icon" href="/static/favicon.ico"> | |
| <script src="https://cdn.tailwindcss.com"></script> | |
| <script src="https://cdn.jsdelivr.net/npm/feather-icons/dist/feather.min.js"></script> | |
| <script src="https://unpkg.com/feather-icons"></script> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML" async></script> | |
| <style> | |
| body { | |
| background-color: #0f172a; | |
| color: #e2e8f0; | |
| font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif; | |
| } | |
| .algorithm-selector { | |
| background-color: #1e293b; | |
| border-radius: 8px; | |
| transition: all 0.3s ease; | |
| } | |
| .algorithm-selector:hover { | |
| background-color: #334155; | |
| } | |
| .active-algorithm { | |
| background-color: #334155; | |
| border-left: 4px solid #a78bfa; | |
| } | |
| .visualization-area { | |
| background: linear-gradient(135deg, #1e293b 0%, #0f172a 100%); | |
| border-radius: 12px; | |
| box-shadow: 0 10px 30px rgba(0, 0, 0, 0.5); | |
| } | |
| .dp-table { | |
| border-collapse: separate; | |
| border-spacing: 0; | |
| } | |
| .dp-cell { | |
| width: 50px; | |
| height: 50px; | |
| border: 1px solid #475569; | |
| text-align: center; | |
| vertical-align: middle; | |
| background-color: #1e293b; | |
| transition: all 0.3s ease; | |
| } | |
| .dp-cell.calculated { | |
| background-color: #4f46e5; | |
| color: white; | |
| } | |
| .dp-cell.current { | |
| background-color: #7c3aed; | |
| color: white; | |
| transform: scale(1.1); | |
| box-shadow: 0 0 10px rgba(124, 58, 237, 0.5); | |
| } | |
| .dp-cell.final { | |
| background-color: #10b981; | |
| color: white; | |
| } | |
| .code-block { | |
| background-color: #1e293b; | |
| border-left: 4px solid #a78bfa; | |
| font-family: 'Fira Code', monospace; | |
| } | |
| .complexity-badge { | |
| background-color: #334155; | |
| } | |
| </style> | |
| </head> | |
| <body class="min-h-screen"> | |
| <!-- Navigation --> | |
| <nav class="bg-slate-900 border-b border-slate-700 sticky top-0 z-50"> | |
| <div class="max-w-7xl mx-auto px-4 sm:px-6 lg:px-8"> | |
| <div class="flex items-center justify-between h-16"> | |
| <div class="flex items-center"> | |
| <div class="flex-shrink-0 flex items-center"> | |
| <i data-feather="cpu" class="text-blue-400 mr-2"></i> | |
| <span class="font-bold text-xl text-white">Algorithm Animator</span> | |
| </div> | |
| <div class="hidden md:block"> | |
| <div class="ml-10 flex items-baseline space-x-4"> | |
| <a href="index.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Home</a> | |
| <a href="sorting.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Sorting</a> | |
| <a href="graph.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Graph Algorithms</a> | |
| <a href="#" class="text-white px-3 py-2 rounded-md text-sm font-medium">Dynamic Programming</a> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </nav> | |
| <!-- Main Content --> | |
| <div class="max-w-7xl mx-auto px-4 sm:px-6 lg:px-8 py-8"> | |
| <div class="text-center mb-10"> | |
| <h1 class="text-3xl font-extrabold text-white sm:text-4xl"> | |
| Dynamic Programming Visualization | |
| </h1> | |
| <p class="mt-3 max-w-2xl mx-auto text-xl text-gray-300"> | |
| Understand how dynamic programming solves complex problems by breaking them into simpler subproblems | |
| </p> | |
| </div> | |
| <div class="flex flex-col lg:flex-row gap-8"> | |
| <!-- Algorithm Selection Panel --> | |
| <div class="lg:w-1/4"> | |
| <div class="bg-slate-800 rounded-lg p-6 sticky top-24"> | |
| <h2 class="text-xl font-bold text-white mb-4">DP Problems</h2> | |
| <div class="space-y-3"> | |
| <div class="algorithm-selector p-4 cursor-pointer active-algorithm"> | |
| <h3 class="font-medium text-white">Fibonacci Sequence</h3> | |
| <p class="text-sm text-gray-300 mt-1">Classic recursive problem with overlapping subproblems</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">0/1 Knapsack</h3> | |
| <p class="text-sm text-gray-300 mt-1">Optimization problem with capacity constraints</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Longest Common Subsequence</h3> | |
| <p class="text-sm text-gray-300 mt-1">Finding longest sequence common to both strings</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Matrix Chain Multiplication</h3> | |
| <p class="text-sm text-gray-300 mt-1">Minimizing scalar multiplications</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Coin Change</h3> | |
| <p class="text-sm text-gray-300 mt-1">Finding minimum coins for a given amount</p> | |
| </div> | |
| </div> | |
| <div class="mt-8"> | |
| <h3 class="font-medium text-white mb-3">Controls</h3> | |
| <div class="grid grid-cols-2 gap-3"> | |
| <button class="bg-purple-600 hover:bg-purple-700 text-white py-2 px-4 rounded"> | |
| Play | |
| </button> | |
| <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded"> | |
| Pause | |
| </button> | |
| <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded"> | |
| Reset | |
| </button> | |
| <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded"> | |
| Step | |
| </button> | |
| </div> | |
| </div> | |
| <div class="mt-8"> | |
| <h3 class="font-medium text-white mb-3">Problem Parameters</h3> | |
| <div class="space-y-3"> | |
| <div> | |
| <label class="text-sm text-gray-300">Sequence Length</label> | |
| <input type="range" min="5" max="20" value="10" class="w-full mt-1"> | |
| </div> | |
| <div> | |
| <label class="text-sm text-gray-300">Show Memoization Table</label> | |
| <div class="mt-1"> | |
| <label class="inline-flex items-center"> | |
| <input type="checkbox" class="rounded text-purple-500" checked> | |
| <span class="ml-2">Enabled</span> | |
| </label> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Visualization Area --> | |
| <div class="lg:w-3/4"> | |
| <div class="visualization-area p-6 rounded-xl"> | |
| <div class="flex justify-between items-center mb-6"> | |
| <h2 class="text-2xl font-bold text-white">Fibonacci Sequence Visualization</h2> | |
| <div class="flex space-x-3"> | |
| <div class="complexity-badge px-3 py-1 rounded-full text-sm"> | |
| Time: O(n) | |
| </div> | |
| <div class="complexity-badge px-3 py-1 rounded-full text-sm"> | |
| Space: O(n) | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Fibonacci Sequence Visualization --> | |
| <div class="mb-8"> | |
| <h3 class="font-bold text-white mb-4">Computing Fibonacci(6)</h3> | |
| <div class="bg-slate-800 rounded-lg p-6"> | |
| <div class="overflow-x-auto"> | |
| <table class="dp-table mx-auto"> | |
| <thead> | |
| <tr> | |
| <th class="dp-cell font-bold">n</th> | |
| <th class="dp-cell font-bold">0</th> | |
| <th class="dp-cell font-bold">1</th> | |
| <th class="dp-cell font-bold">2</th> | |
| <th class="dp-cell font-bold">3</th> | |
| <th class="dp-cell font-bold">4</th> | |
| <th class="dp-cell font-bold">5</th> | |
| <th class="dp-cell font-bold">6</th> | |
| </tr> | |
| </thead> | |
| <tbody> | |
| <tr> | |
| <td class="dp-cell font-bold">fib(n)</td> | |
| <td class="dp-cell calculated">0</td> | |
| <td class="dp-cell calculated">1</td> | |
| <td class="dp-cell calculated">1</td> | |
| <td class="dp-cell calculated">2</td> | |
| <td class="dp-cell calculated">3</td> | |
| <td class="dp-cell current">5</td> | |
| <td class="dp-cell">8</td> | |
| </tr> | |
| </tbody> | |
| </table> | |
| </div> | |
| <div class="mt-6 text-center"> | |
| <div class="inline-block bg-purple-900 px-4 py-2 rounded-lg"> | |
| <span class="text-purple-300">fib(6) = fib(5) + fib(4) = 5 + 3 = </span> | |
| <span class="text-white font-bold text-xl">8</span> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Recursion Tree --> | |
| <div class="mb-8"> | |
| <h3 class="font-bold text-white mb-4">Recursion Tree Visualization</h3> | |
| <div class="bg-slate-800 rounded-lg p-6 h-64 flex items-center justify-center"> | |
| <div class="text-center"> | |
| <div class="text-white font-mono text-lg mb-2">fib(6)</div> | |
| <div class="flex justify-center space-x-8"> | |
| <div class="text-center"> | |
| <div class="text-blue-300 font-mono">fib(5)</div> | |
| <div class="text-xs text-gray-400 mt-1">Calculated</div> | |
| </div> | |
| <div class="text-center"> | |
| <div class="text-purple-300 font-mono">fib(4)</div> | |
| <div class="text-xs text-gray-400 mt-1">Calculated</div> | |
| </div> | |
| </div> | |
| <div class="mt-4 text-sm text-gray-400"> | |
| Using memoization to avoid redundant calculations | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Current Step Description --> | |
| <div class="bg-slate-800 rounded-lg p-4 mb-6"> | |
| <h3 class="font-bold text-white mb-2">Current Step</h3> | |
| <p class="text-gray-300">Calculating fib(6) by adding previously computed values fib(5)=5 and fib(4)=3.</p> | |
| </div> | |
| <!-- Pseudocode --> | |
| <div class="code-block p-4 rounded mb-6"> | |
| <h3 class="font-bold text-white mb-2">Memoized Fibonacci</h3> | |
| <pre class="text-green-400 text-sm"> | |
| def fibonacci(n, memo={}): | |
| if n in memo: | |
| return memo[n] | |
| if n <= 1: | |
| return n | |
| memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo) | |
| return memo[n]</pre> | |
| </div> | |
| <!-- Mathematical Explanation --> | |
| <div class="bg-slate-800 rounded-lg p-4"> | |
| <h3 class="font-bold text-white mb-3">Mathematical Analysis</h3> | |
| <div class="math-display text-purple-300"> | |
| \( F(n) = F(n-1) + F(n-2) \text{ for } n > 1 \) | |
| </div> | |
| <p class="text-gray-300 mt-3"> | |
| The Fibonacci sequence exhibits optimal substructure and overlapping subproblems, | |
| making it ideal for dynamic programming optimization. | |
| </p> | |
| <div class="math-display text-purple-300"> | |
| \( \text{Time Complexity: } O(n) \text{ with memoization} \) | |
| </div> | |
| <p class="text-gray-300 mt-3"> | |
| Without memoization, the naive recursive approach has exponential time complexity | |
| \( O(\phi^n) \) where \( \phi \) is the golden ratio. Memoization reduces this to | |
| linear time by storing previously computed values. | |
| </p> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Footer --> | |
| <footer class="bg-slate-900 border-t border-slate-800 mt-12"> | |
| <div class="max-w-7xl mx-auto py-12 px-4 sm:px-6 lg:px-8"> | |
| <div class="md:flex md:items-center md:justify-between"> | |
| <div class="flex justify-center md:justify-start"> | |
| <div class="flex items-center"> | |
| <i data-feather="cpu" class="text-blue-400 mr-2"></i> | |
| <span class="text-white font-bold">Algorithm Animator</span> | |
| </div> | |
| </div> | |
| <div class="mt-8 md:mt-0 md:order-1"> | |
| <p class="text-center text-base text-gray-400"> | |
| © 2023 Algorithm Animator. All rights reserved. | |
| </p> | |
| </div> | |
| </div> | |
| </div> | |
| </footer> | |
| <script> | |
| feather.replace(); | |
| </script> | |
| </body> | |
| </html> | |