Questions related to design and analysis of algorithms
2
votes
1answer
15 views
Why is the initial state of Zobrist hashing random?
When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?
2
votes
1answer
33 views
Algorithm to determine if an interval is covered by a list of intervals? [on hold]
Given a list of intervals $[s_1, e_1], [s_2, e_2], \ldots$, what's the most efficient way to determine if an interval $[a, b]$ can be covered by the intervals in the list?
1
vote
1answer
34 views
Application of the Monte Carlo method
I am unclear on when to use the Monte Carlo random sampling method for algorithm design. the classic example that i keep seeing is using random points within some bounding rectangle to determine the ...
1
vote
2answers
139 views
Basic action for every data structure O(1)
My lecturer for Algorithms said that most of the data structures I will encounter in the algorithms course I am taking have a basic action which is of O(1).
Ex: Binary heap.
Basic action is:
...
-1
votes
0answers
19 views
If an array is first increasing then decreasing then find the point of contact [on hold]
Q: If an array is first increasing then decreasing then find the point of contact using binary search and linear search , how to do this ?
I have the solution using pair wise but I need optimize ...
0
votes
0answers
20 views
Using a lerp to change color [on hold]
I am trying to create a color lerp where if you have 100%, the color returned is blue, if you have 80%, the color is purple and soforth (i.e. if you have 90% the color is the mixture of blue and ...
5
votes
1answer
122 views
Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors
We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers.
The algorithm was:
Given an array A of length n:
...
3
votes
3answers
155 views
Algorithm Request: “Shortest non-existing substring over given alphabet”
I'm looking for an (efficient) algorithm to solve the following problem:
Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
2
votes
2answers
137 views
Proving the Bubblesort actually sorts
Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$.
To prove that Bubblesort works, we have to prove that it always terminates and that
$$A'[0]\leq A'[1] \leq \dots \leq ...
1
vote
4answers
102 views
Checking if there are 2 elements in an array that sum to X in O(n lg n)
I have thought about the most useful way of checking an array for 2 elements that sum to X.
The trivial solution is to check the sum of every element with every element, and the complexity of this ...
3
votes
2answers
63 views
minimizing the summed cardinality of set unions
this optimization problem, I am working on, is kind of making me crazy. ;)
Given is a list o of sets (with finite cardinality) of strictly positive integer values ...
1
vote
2answers
43 views
Applications of Depth-First Spanning Tree
I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
-1
votes
0answers
13 views
Closest pair of points on a line [closed]
What is the problem in “closest pair of points algorithm” if all points share the same x-coordinate or the same y-coordinate? and how the algorithm will change?
1
vote
1answer
35 views
Proving the correctness of an algorithm, which computes the connectivity of a directed graph
Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not ...
0
votes
0answers
46 views
Finding shortest path in a graph when edge weights depend on the chosen vertices
Here is my problem: I have a directed weighted graph with a substantial amount of vertices (few thousands), no cycles, in fact, it includes a starting node, a final node and an $m \times n$ grid ...
