Recently I came across a problem (https://algs4.cs.princeton.edu/44sp/ question #34). I've already devised an algorithm that modifies Dijkstra's algorithm under the assumption that the graph only has positive weights. I was wondering, how would I go about modifying Bellman-Ford (or some other negative weight shortest path algorithm) to solve this problem in $$$O(n^2m)$$$ time?

Note: I also saw something similar in CLRS (bitonic shortest paths), but the solution found here: https://walkccc.me/CLRS/Chap24/Problems/24-6/ is a extremely difficult to understand.

Hello,

How would I go about efficiently finding if an even cycle exists in a directed graph? I know for odd cycles we can simply run a bipartition algorithm and if it doesn't work we know there exists an odd cycle. But how do I do that for even cycles?

Hi, I stumbled across a simple question:

Given $$$4 \le N \le 1000$$$ points on a cartesian plane, count the number of squares where the corner of each squares lie on the points.

The first obvious method would be to put all the points in a map, and perform an $$$O(N^3)$$$ solution to find the last corner point and see if it exists.

The next method would be to find opposite corner points in $$$O(N^2)$$$ time and check if the rest of the two points exist.

Lastly, I was wondering if there's an $$$O(N\log N)$$$ solution or $$$O(N)$$$ solution?

Hi! I have the following problem regarding MSTs.

Given a complete undirected graph $$$G = (V,E)$$$ of edges only costing either 1 or 2, find a subset of the edges $$$|E'|=k$$$ for some $$$k$$$ and vertices $$$V'$$$ such that $$$(V', E')$$$ form a tree and is of minimum cost.

The bounds for this problem is that $$$1 \le n \le 10^3$$$ and $$$1 \le k \le n - 1$$$

To me, this is very similar to an MST problem, but running a classic MST algorithm would be slow and I'm trying to do this in $$$O(|E|)$$$ time by making use of the complete graph property.

A common D&C question is to find the non-dominated points. This can be done in $$$O(n \log n)$$$ by sorting the points by x value, splitting them in half and then finding the solution on each side. We combine them by noticing that we just need to find the right-most point that is not dominated by the right side.

Now, I'm curious to know the opposite. How can we find the dominance factor of all points? That is, how would I go about finding the number of points that dominate point $$$(x_i, y_i)$$$?

I'm thinking about something along the lines of counting inversions but cannot formalize my idea.

I have the following question:

Split a set of n elements into 2 sets based on k conditions.