Skip to main content
ProofAnvil

Computing

Algorithms

Practice Algorithms with 315 published problems. Preview a problem, explore the course outline, and work through one problem at a time.

Change course
Standard study path · 315 published problemsAll course problems

Practice

Start training
Course and study path

Available problems completed

View progress

Loading course progress…

Preview a course problem

See a problem from Algorithms before you begin.

Course outline

6 topics

  1. Correctness proofs and asymptotic complexity

  2. Divide-and-conquer algorithms

  3. Greedy algorithms and exchange proofs

  4. Dynamic programming and state design

  5. Graph optimization and traversal algorithms

  6. Reductions, NP-completeness, and approximation

Checking available topic links…

See how practice works

Try an example on paper, then open a hint or a worked explanation.

These free examples demonstrate the practice process. They are separate from your selected course and are not graded or saved.

Proof: make a limit precise

For each positive integer \(n\), let \(a_n=n/(n+2)\). Prove from the definition of convergence that \(a_n\to1\).

Show a hint

The definition asks: given any \(\varepsilon>0\), can you make \(|a_n-1|<\varepsilon\) for every sufficiently large \(n\)? First simplify \(|a_n-1|\).

Show worked explanation

Let \(\varepsilon>0\). For every positive integer \(n\), \[ \left|\frac{n}{n+2}-1\right|=\left|\frac{-2}{n+2}\right|=\frac{2}{n+2}. \] Choose a positive integer \(N>2/\varepsilon\). Such an integer exists because the positive integers are unbounded. If \(n\ge N\), all denominators are positive, so \[ \frac{2}{n+2}\le\frac{2}{N+2}<\frac{2}{N}<\varepsilon. \] Thus, for every positive tolerance \(\varepsilon\), this \(N\), chosen for the given \(\varepsilon\), works for every \(n\ge N\). This is exactly the definition of \(a_n\to1\).

Calculation: complete the square

Solve \(x^2-6x+5=0\) over the real numbers by completing the square. Check each solution in the original equation.

Show a hint

Move \(5\) to the other side. Half of \(-6\) is \(-3\), and its square is \(9\). Add \(9\) to both sides to form \((x-3)^2\).

Show worked explanation

The identity \( (x-3)^2=x^2-6x+9 \) explains the completed square. Each step below preserves equality: \[ x^2-6x=-5,\qquad x^2-6x+9=4,\qquad (x-3)^2=4. \] A real number whose square is \(4\) is either \(2\) or \(-2\). Therefore \(x-3=2\) or \(x-3=-2\), giving \(x=5\) or \(x=1\). Check both values: \[ 5^2-6(5)+5=25-30+5=0,\qquad 1^2-6(1)+5=1-6+5=0. \] Both satisfy the original equation. The two square-root cases cover all real possibilities, so the solution set is \(\{1,5\}\).

Physical model: distance and displacement

A cart travels along a straight line: \(18\,\mathrm{m}\) east in \(5\,\mathrm{s}\), then \(12\,\mathrm{m}\) west in \(3\,\mathrm{s}\), with no pause between the two legs. Find its average velocity and average speed for the whole trip.

Show a hint

Take east as positive. Average velocity uses signed displacement divided by total time. Average speed uses total distance traveled divided by total time.

Show worked explanation

With east positive, the displacements of the two legs are \(+18\,\mathrm{m}\) and \(-12\,\mathrm{m}\). The net displacement is \(18-12=6\,\mathrm{m}\) east, while the total distance traveled is \(18+12=30\,\mathrm{m}\). Total time is \(5+3=8\,\mathrm{s}\). \[ \text{Average velocity}=\frac{6\,\mathrm{m}}{8\,\mathrm{s}}=0.75\,\mathrm{m/s}\text{ east}, \] \[ \text{Average speed}=\frac{30\,\mathrm{m}}{8\,\mathrm{s}}=3.75\,\mathrm{m/s}. \] Check: the total distance is at least the magnitude of the displacement, so average speed must be at least the magnitude of average velocity. Here \(3.75\ge0.75\), as expected.