podsni/algorithm-animator
0
1<!DOCTYPE html>2<html lang="en">3<head>4 <meta charset="UTF-8">5 <meta name="viewport" content="width=device-width, initial-scale=1.0">6 <title>Dynamic Programming - Algorithm Animator</title>7 <link rel="icon" type="image/x-icon" href="/static/favicon.ico">8 <script src="https://cdn.tailwindcss.com"></script>9 <script src="https://cdn.jsdelivr.net/npm/feather-icons/dist/feather.min.js"></script>10 <script src="https://unpkg.com/feather-icons"></script>11 <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML" async></script>12 <style>13 body {14 background-color: #0f172a;15 color: #e2e8f0;16 font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;17 }18 19 .algorithm-selector {20 background-color: #1e293b;21 border-radius: 8px;22 transition: all 0.3s ease;23 }24 25 .algorithm-selector:hover {26 background-color: #334155;27 }28 29 .active-algorithm {30 background-color: #334155;31 border-left: 4px solid #a78bfa;32 }33 34 .visualization-area {35 background: linear-gradient(135deg, #1e293b 0%, #0f172a 100%);36 border-radius: 12px;37 box-shadow: 0 10px 30px rgba(0, 0, 0, 0.5);38 }39 40 .dp-table {41 border-collapse: separate;42 border-spacing: 0;43 }44 45 .dp-cell {46 width: 50px;47 height: 50px;48 border: 1px solid #475569;49 text-align: center;50 vertical-align: middle;51 background-color: #1e293b;52 transition: all 0.3s ease;53 }54 55 .dp-cell.calculated {56 background-color: #4f46e5;57 color: white;58 }59 60 .dp-cell.current {61 background-color: #7c3aed;62 color: white;63 transform: scale(1.1);64 box-shadow: 0 0 10px rgba(124, 58, 237, 0.5);65 }66 67 .dp-cell.final {68 background-color: #10b981;69 color: white;70 }71 72 .code-block {73 background-color: #1e293b;74 border-left: 4px solid #a78bfa;75 font-family: 'Fira Code', monospace;76 }77 78 .complexity-badge {79 background-color: #334155;80 }81 </style>82</head>83<body class="min-h-screen">84 <!-- Navigation -->85 <nav class="bg-slate-900 border-b border-slate-700 sticky top-0 z-50">86 <div class="max-w-7xl mx-auto px-4 sm:px-6 lg:px-8">87 <div class="flex items-center justify-between h-16">88 <div class="flex items-center">89 <div class="flex-shrink-0 flex items-center">90 <i data-feather="cpu" class="text-blue-400 mr-2"></i>91 <span class="font-bold text-xl text-white">Algorithm Animator</span>92 </div>93 <div class="hidden md:block">94 <div class="ml-10 flex items-baseline space-x-4">95 <a href="index.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Home</a>96 <a href="sorting.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Sorting</a>97 <a href="graph.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Graph Algorithms</a>98 <a href="#" class="text-white px-3 py-2 rounded-md text-sm font-medium">Dynamic Programming</a>99 </div>100 </div>101 </div>102 </div>103 </div>104 </nav>105 106 <!-- Main Content -->107 <div class="max-w-7xl mx-auto px-4 sm:px-6 lg:px-8 py-8">108 <div class="text-center mb-10">109 <h1 class="text-3xl font-extrabold text-white sm:text-4xl">110 Dynamic Programming Visualization111 </h1>112 <p class="mt-3 max-w-2xl mx-auto text-xl text-gray-300">113 Understand how dynamic programming solves complex problems by breaking them into simpler subproblems114 </p>115 </div>116 117 <div class="flex flex-col lg:flex-row gap-8">118 <!-- Algorithm Selection Panel -->119 <div class="lg:w-1/4">120 <div class="bg-slate-800 rounded-lg p-6 sticky top-24">121 <h2 class="text-xl font-bold text-white mb-4">DP Problems</h2>122 <div class="space-y-3">123 <div class="algorithm-selector p-4 cursor-pointer active-algorithm">124 <h3 class="font-medium text-white">Fibonacci Sequence</h3>125 <p class="text-sm text-gray-300 mt-1">Classic recursive problem with overlapping subproblems</p>126 </div>127 <div class="algorithm-selector p-4 cursor-pointer">128 <h3 class="font-medium text-white">0/1 Knapsack</h3>129 <p class="text-sm text-gray-300 mt-1">Optimization problem with capacity constraints</p>130 </div>131 <div class="algorithm-selector p-4 cursor-pointer">132 <h3 class="font-medium text-white">Longest Common Subsequence</h3>133 <p class="text-sm text-gray-300 mt-1">Finding longest sequence common to both strings</p>134 </div>135 <div class="algorithm-selector p-4 cursor-pointer">136 <h3 class="font-medium text-white">Matrix Chain Multiplication</h3>137 <p class="text-sm text-gray-300 mt-1">Minimizing scalar multiplications</p>138 </div>139 <div class="algorithm-selector p-4 cursor-pointer">140 <h3 class="font-medium text-white">Coin Change</h3>141 <p class="text-sm text-gray-300 mt-1">Finding minimum coins for a given amount</p>142 </div>143 </div>144 145 <div class="mt-8">146 <h3 class="font-medium text-white mb-3">Controls</h3>147 <div class="grid grid-cols-2 gap-3">148 <button class="bg-purple-600 hover:bg-purple-700 text-white py-2 px-4 rounded">149 Play150 </button>151 <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded">152 Pause153 </button>154 <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded">155 Reset156 </button>157 <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded">158 Step159 </button>160 </div>161 </div>162 163 <div class="mt-8">164 <h3 class="font-medium text-white mb-3">Problem Parameters</h3>165 <div class="space-y-3">166 <div>167 <label class="text-sm text-gray-300">Sequence Length</label>168 <input type="range" min="5" max="20" value="10" class="w-full mt-1">169 </div>170 <div>171 <label class="text-sm text-gray-300">Show Memoization Table</label>172 <div class="mt-1">173 <label class="inline-flex items-center">174 <input type="checkbox" class="rounded text-purple-500" checked>175 <span class="ml-2">Enabled</span>176 </label>177 </div>178 </div>179 </div>180 </div>181 </div>182 </div>183 184 <!-- Visualization Area -->185 <div class="lg:w-3/4">186 <div class="visualization-area p-6 rounded-xl">187 <div class="flex justify-between items-center mb-6">188 <h2 class="text-2xl font-bold text-white">Fibonacci Sequence Visualization</h2>189 <div class="flex space-x-3">190 <div class="complexity-badge px-3 py-1 rounded-full text-sm">191 Time: O(n)192 </div>193 <div class="complexity-badge px-3 py-1 rounded-full text-sm">194 Space: O(n)195 </div>196 </div>197 </div>198 199 <!-- Fibonacci Sequence Visualization -->200 <div class="mb-8">201 <h3 class="font-bold text-white mb-4">Computing Fibonacci(6)</h3>202 <div class="bg-slate-800 rounded-lg p-6">203 <div class="overflow-x-auto">204 <table class="dp-table mx-auto">205 <thead>206 <tr>207 <th class="dp-cell font-bold">n</th>208 <th class="dp-cell font-bold">0</th>209 <th class="dp-cell font-bold">1</th>210 <th class="dp-cell font-bold">2</th>211 <th class="dp-cell font-bold">3</th>212 <th class="dp-cell font-bold">4</th>213 <th class="dp-cell font-bold">5</th>214 <th class="dp-cell font-bold">6</th>215 </tr>216 </thead>217 <tbody>218 <tr>219 <td class="dp-cell font-bold">fib(n)</td>220 <td class="dp-cell calculated">0</td>221 <td class="dp-cell calculated">1</td>222 <td class="dp-cell calculated">1</td>223 <td class="dp-cell calculated">2</td>224 <td class="dp-cell calculated">3</td>225 <td class="dp-cell current">5</td>226 <td class="dp-cell">8</td>227 </tr>228 </tbody>229 </table>230 </div>231 232 <div class="mt-6 text-center">233 <div class="inline-block bg-purple-900 px-4 py-2 rounded-lg">234 <span class="text-purple-300">fib(6) = fib(5) + fib(4) = 5 + 3 = </span>235 <span class="text-white font-bold text-xl">8</span>236 </div>237 </div>238 </div>239 </div>240 241 <!-- Recursion Tree -->242 <div class="mb-8">243 <h3 class="font-bold text-white mb-4">Recursion Tree Visualization</h3>244 <div class="bg-slate-800 rounded-lg p-6 h-64 flex items-center justify-center">245 <div class="text-center">246 <div class="text-white font-mono text-lg mb-2">fib(6)</div>247 <div class="flex justify-center space-x-8">248 <div class="text-center">249 <div class="text-blue-300 font-mono">fib(5)</div>250 <div class="text-xs text-gray-400 mt-1">Calculated</div>251 </div>252 <div class="text-center">253 <div class="text-purple-300 font-mono">fib(4)</div>254 <div class="text-xs text-gray-400 mt-1">Calculated</div>255 </div>256 </div>257 <div class="mt-4 text-sm text-gray-400">258 Using memoization to avoid redundant calculations259 </div>260 </div>261 </div>262 </div>263 264 <!-- Current Step Description -->265 <div class="bg-slate-800 rounded-lg p-4 mb-6">266 <h3 class="font-bold text-white mb-2">Current Step</h3>267 <p class="text-gray-300">Calculating fib(6) by adding previously computed values fib(5)=5 and fib(4)=3.</p>268 </div>269 270 <!-- Pseudocode -->271 <div class="code-block p-4 rounded mb-6">272 <h3 class="font-bold text-white mb-2">Memoized Fibonacci</h3>273 <pre class="text-green-400 text-sm">274def fibonacci(n, memo={}):275 if n in memo:276 return memo[n]277 278 if n <= 1:279 return n280 281 memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)282 return memo[n]</pre>283 </div>284 285 <!-- Mathematical Explanation -->286 <div class="bg-slate-800 rounded-lg p-4">287 <h3 class="font-bold text-white mb-3">Mathematical Analysis</h3>288 <div class="math-display text-purple-300">289 \( F(n) = F(n-1) + F(n-2) \text{ for } n > 1 \)290 </div>291 <p class="text-gray-300 mt-3">292 The Fibonacci sequence exhibits optimal substructure and overlapping subproblems, 293 making it ideal for dynamic programming optimization.294 </p>295 <div class="math-display text-purple-300">296 \( \text{Time Complexity: } O(n) \text{ with memoization} \)297 </div>298 <p class="text-gray-300 mt-3">299 Without memoization, the naive recursive approach has exponential time complexity 300 \( O(\phi^n) \) where \( \phi \) is the golden ratio. Memoization reduces this to 301 linear time by storing previously computed values.302 </p>303 </div>304 </div>305 </div>306 </div>307 </div>308 309 <!-- Footer -->310 <footer class="bg-slate-900 border-t border-slate-800 mt-12">311 <div class="max-w-7xl mx-auto py-12 px-4 sm:px-6 lg:px-8">312 <div class="md:flex md:items-center md:justify-between">313 <div class="flex justify-center md:justify-start">314 <div class="flex items-center">315 <i data-feather="cpu" class="text-blue-400 mr-2"></i>316 <span class="text-white font-bold">Algorithm Animator</span>317 </div>318 </div>319 <div class="mt-8 md:mt-0 md:order-1">320 <p class="text-center text-base text-gray-400">321 © 2023 Algorithm Animator. All rights reserved.322 </p>323 </div>324 </div>325 </div>326 </footer>327 328 <script>329 feather.replace();330 </script>331</body>332</html>333