<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Content title</title>
<!-- Global styles -->
<link rel="stylesheet" href="../../../assets/css/base.css" />
<link rel="stylesheet" href="../../../assets/css/chapters.css" />
<!-- Library styles -->
<link rel="stylesheet"
href="<https://cdn.jsdelivr.net/npm/pseudocode@latest/build/pseudocode.min.css>" />
<link rel="stylesheet"
href="<https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.11.1/styles/default.min.css>" />
<!-- MathJax global config (must come BEFORE MathJax) -->
<script src="../../../assets/js/mathjax-config.js"></script>
<!-- Library scripts (deferred) -->
<script defer
src="<https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js>"></script>
<script defer
src="<https://cdn.jsdelivr.net/npm/pseudocode@latest/build/pseudocode.min.js>"></script>
<script defer
src="<https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.11.1/highlight.min.js>"></script>
<script defer
src="<https://cdn.jsdelivr.net/npm/highlightjs-line-numbers.js@2.8.0/dist/highlightjs-line-numbers.min.js>"></script>
</head>
<body>
<!-- Left Nav Bar -->
...
<!-- Text and Explanation Block -->
...
<!-- Figure -->
...
<!-- Pseudo Code -->
...
<!-- Code Highlighting -->
...
<!-- Framework scripts -->
<script type="module" src="../../../assets/js/main.js"></script>
<script type="module" src="../../../assets/js/chapter-page.js"></script>
</body>
</html>
This is an example how you construct the side bar …
<aside id="page-sidebar" class="sidebar">
<div class="sidebar-header">
<a class="home-link" href="../../../index.html">🏠 Home Page</a>
<button
id="sidebarToggle"
class="sidebar-toggle"
aria-label="Toggle sidebar"
aria-expanded="true"
>
☰
</button>
</div>
<div class="sidebar-inner">
<nav>
<h3>
<a class="section-link" href="../index.html">📖 Algorithms</a>
</h3>
<ul class="book-nav">
<li class="chapter-details">
<details>
<summary>Chapter 4: Paths in Graphs</summary>
<ul
id="toc-ch04"
class="toc-list"
data-src="04-paths-in-graphs.html"
></ul>
</details>
</li>
<li class="chapter-details">
<details>
<summary>Chapter 5: Greedy Algorithms</summary>
<ul
id="toc-ch05"
class="toc-list"
data-src="05-greedy-algorithms.html"
></ul>
</details>
</li>
<li class="chapter-details">
<details open>
<summary>Chapter 6: Dynamic Programming</summary>
<ul id="toc-ch06" class="toc-list" data-src="self"></ul>
</details>
</li>
<li class="chapter-details">
<details>
<summary>Chapter 7: Linear Programming & Reductions</summary>
<ul
id="toc-ch07"
class="toc-list"
data-src="07-linear-programming.html"
></ul>
</details>
</li>
</ul>
</nav>
</div>
</aside>
<section id="recap-shortest-path-dags">
<div class="explanation-block">
<div class="original-text-container">
<p><strong>The Sledgehammers of Algorithm Design</strong></p>
<p class="original-text">
<em
>In the preceding chapters we have seen some elegant design
principles-such as divide-andconquer, graph exploration, and
greedy choice-that yield definitive algorithms for a variety
of important computational tasks. The drawback of these tools
is that they can only be used on very specific types of
problems. We now turn to the two sledgehammers of the
algorithms craft, dynamic programming and linear programming,
techniques of very broad applicability that can be invoked
when more specialized methods fail. Predictably, this
generality often comes with a cost in efficiency.</em
>
</p>
</div>
<div class="explanation-text">
<p>
This paragraph introduces
<strong>dynamic programming</strong> (DP) and
<strong>linear programming</strong> as powerful, general-purpose
problem-solving techniques. It contrasts them with more
specialized methods like greedy algorithms or
divide-and-conquer, which are elegant but only work for specific
problem structures. Dynamic programming is presented as a
"sledgehammer"—a versatile and powerful tool that can solve a
very wide range of problems, especially when other methods fail.
</p>
</div>
</div>
</section>
<figure>
<img
src="../../../assets/images/algorithms/chpt_6_imgs/figure-6-2.png"
alt="A directed acyclic graph representing the LIS problem."
width="700"
/>
<figcaption>
Figure 6.2: The dag of increasing subsequences.
</figcaption>
</figure>
<pre class="pseudocode" id="bfs-code">
\\begin{algorithm}
\\caption{Breadth‑First Search}
\\begin{algorithmic}
\\Procedure{BFS}{$G, s$}
\\ForAll{$u \\in V$}
\\State $\\text{dist}(u) \\gets \\infty$
\\EndFor
\\State $\\text{dist}(s) \\gets 0$
\\State $Q \\gets [s]$
\\While{$Q$ is not empty}
\\State $u \\gets \\text{eject}(Q)$
\\ForAll{$(u,v) \\in E$}
\\If{$\\text{dist}(v)=\\infty$}
\\State $\\text{inject}(Q,v)$
\\State $\\text{dist}(v) \\gets \\text{dist}(u)+1$
\\EndIf
\\EndFor
\\EndWhile
\\EndProcedure
\\end{algorithmic}
\\end{algorithm}
</pre
>
<pre><code class="language-python">for i in range(n):
print(A[i])
</code></pre>