Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

1 vote

Finding a Hamiltonian Cycle in a directed graph - graph problem

You can introduce a network $G_{new}$ such as follows: For each vertex i (or town) in G introduce two vertices $i'$ (for north gate) and $i''$ (for south gate) which are connected to each other; i.e. ...
user avatar
6 votes

Number of Inversions found in Selection sort vs Exchange sort

Here's another perspective. Less mathematical, but I think also insightful. Using a fabulous sort visualizer (taken from this), here's random data and how the data looks midway through sorting with ...
user avatar
4 votes
Accepted

Number of Inversions found in Selection sort vs Exchange sort

Interesting question! Indeed, the expected numbers are quadratic and linearithmic respectively. Assumptions For ease of analysis, assume the numbers in the given array are distinct. This assumption ...
user avatar
  • 33.2k
0 votes

Dynamic Programming - Difficult Jumping Frog Problem

We shall use bottom-up dynamic programming, where subproblems of smallest size are solved first, and their solutions are used to update the solutions to larger subproblems. Let $A$ be a two-...
user avatar

Top 50 recent answers are included