Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

Filter by
Sorted by
Tagged with
0
votes
2answers
31 views

Can you help me provide some examples of 3-co-SAT?

Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable, namely ...
0
votes
0answers
142 views

Problems/properties of dynamic graphs with strong lower bounds

I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and ...
-1
votes
0answers
40 views

build data-structure

Consider the following operations Build(A[1 . . . n]): Initialises the data structure with the elements of the (possibly unsorted)array A with duplicates. It runs in time O(n). Insert(x): Inserts the ...
1
vote
1answer
36 views

Interactive sort for only top elements

I have a set of objects and a set of comparison results for some of them. I want an algorithm that returns the next comparison I should make to two objects towards having a way to know the full order ...
1
vote
0answers
47 views

Find array of coprime integers whose average is maximized

I am creating a class to store large integers in a residue number system. I want each "integer" to be 4-12GB in size and be comprised of 64-bit moduli. These moduli must be pairwise coprime ...
0
votes
0answers
16 views

Method for minimizing relays in a switching/steering network - combinatorics/CSP algorithm exists?

This question is borne from the electrical engineering world, so I first asked it there, but it's really more of an algorithm optimization problem that everyone here might be better suited to help ...
4
votes
1answer
45 views

Find the segments set with the lowest number of 2D collisions

I am given 2 sets of n 2D Points. I need to find the segment set S where each of the n segments has its start and end in the first and second set respectively. The requirement is that each point must ...
1
vote
1answer
53 views

How should i face this graph problem?

The mentioned problem: Cluster Editing Problem. I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can ...
0
votes
1answer
30 views

Disadvantages of Huffman Encoding

Two main disadvantages of Huffman encoding is that it makes two passes over data: First pass: Find out sequences frequencies $f(\cdot)$ of letters $c \in C$ in the document $D$. Then constructing ...
0
votes
0answers
16 views

Prove the Prefix Code Tree in Huffman Coding is Optimal

Lemma: Let $a$ and $b$ be two characters that are sibling leaves of maximum depth $T $, and $x$ and $y$ are the two charachterts of the minimum frequency $f(\cdot)$. WLOG, assume that $f[x] <f[y]&...
0
votes
1answer
18 views

Algorithm best compare similarities between two data sets in percentage

I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions. Example: Q1: Do you prefer physically demanding tasks? A1: Nope Maybe Yes -...
2
votes
1answer
45 views

Upper-bounding the out-going degree of a graph

Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree. For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
0
votes
0answers
24 views

Moving Average with Time-based Window

Given a stream of data that comes at irregular intervals, is there a sub-linear time solution to get the moving average within a fixed lookback time window given that the query occurs randomly? For a ...
2
votes
0answers
31 views

Variation of the gas station problem

Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
0
votes
1answer
33 views

Failing to calculate the gradient and y-shift for best fit line using sum-squares method. Can anyone help me to pinpoint the issue?

I'm trying to work out how to make the working implementation of fitting the straight line among the set data points. I base my function: ...
0
votes
1answer
12 views

Polynomial-time algorithm for distribution of arbitrary symbols

Is there a polynomial-time algorithm for distribution of clauses of arbitrary symbols (i.e. similar to multiplication distributing over addition)? For simplicity, let's assume the distributive ...
1
vote
1answer
46 views

Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
18 views
0
votes
1answer
32 views

Reader / writer locking algorithm

I'm pretty sure there's a textbook solution to this problem, but I haven't figured it out. I have fixed-size blocks of data arranged in a sequence: block 0, block 1, etc.. There are reader threads ...
1
vote
1answer
39 views

Algorithm to find the path with minimum bending points on a square grid board

Let's suppose we have a square grid board like the one shown in the picture below: I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
2
votes
2answers
390 views

Minimize the expected value of money spent on boxes until the prize is found

There are $n$ closed boxes and one and only one box of them contains a prize. The $i$-th box has probability $p_i$ of containing a prize. A player must pay $c_i$ coins to open the $i$-th box. The ...
1
vote
1answer
24 views

Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
2
votes
1answer
55 views

Best algorithm for solving $A[i] + B[j] = m$

Suppose $A$ and $B$ are arrays of real numbers of length $n$, and $M$ is another real number. One algorithm for finding indices $i$ and $j$ such that $A[i] + B[j] = M$ is to comparison-sort $B$ and ...
0
votes
1answer
14 views

Given an array of n points of the form (x,y), the distance between two points (x1,y1) and (x2,y2) is defined as min(abs(x1-x2), abs(y1-y2))

We need to find mth smallest possible distance by considering all possible pairs. I solved this problem by considering all possible pairs and maintaining a max priority queue. If the max priority ...
0
votes
0answers
29 views

Finding sequences in a binary matrix with recursion

Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion? I know how to solve the problem without recursion ...
2
votes
1answer
55 views

Why recording non-existent children in the pre-order traversal will differentiate different binary trees?

I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
0
votes
1answer
21 views

How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
0
votes
0answers
14 views

Minimizing cost with selection

I have the following problem: Suppose that we have several points that cover some cities, with a cost associated to each point. This can be represented as a grid: ...
0
votes
0answers
28 views

An idempotent grammar for text decoding?

I'd like to create a function decode(x : string) such that decode(x : string) == decode(decode(x : string)). I believe I can ...
2
votes
1answer
39 views

Proof that any algorithm who builds a spanning tree using Cut and Cycle properties is an MST

The Kleinberg and Tardos Algorithm makes the following claim without proof: Any algorithm that builds a spanning tree by repeatedly including edges when justified by the Cut Property and deleting ...
0
votes
0answers
18 views

Proving Correctness of Knapscap Fraction Algorithm

I am trying to prove correctness of Knapsack algorithm below: Algorithm works by taking rations of values of items to weights and then sort them in decreasing order taking $O(n\log{n})$ time. So to ...
0
votes
0answers
14 views

change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
1
vote
1answer
36 views

algorithm to check the existence of $b-1$ in $(n)_b$?

Given an integer number $n$ (in base 10) and a base $b$, determine whether the representation of $n$ in base $b$, $(n)_b$ has a coefficient with value of $b-1$. ...
-1
votes
0answers
37 views

Graph to the power of 2

Hello. How do I make this graph to the power of 2? How will it look like? https://en.wikipedia.org/wiki/Graph_power
2
votes
4answers
120 views

Why was the fast inverse square root algorithm so ingenious?

In 2005 ID software open source the game Quake 3 Arena. When they did it was discovered was an algorithm that was so ingenious and all it did was calculate the inverse of a square root. The easy way ...
0
votes
1answer
17 views

Proof the recurrence relation of order statistics using induction

I read order statistics from the book The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley As per the algorithm the recurrence relation given T(n)<= cn for ...
1
vote
0answers
39 views

finding max element in a min-max heap structure

I am trying to implement min-max heap structure A min-max heap is a data structure that is identical to a binary heap, but the heap-order property is that for any node, X, at even depth, the element ...
1
vote
0answers
38 views

Median as pivot selection halves array into one third and two thirds

Selecting the median as an approach for pivot selection halves the array into $T(\frac n3)$ and $T(\frac{2n}{3})$, so our $T(n)$ becomes: $$T(n) = T(\frac{2n}{3})+ T(\frac n3)$$ Solution: Approach 1: ...
0
votes
1answer
34 views

Reasoning given with explanation of Halting Problem

I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the ...
3
votes
0answers
30 views

Periodic 4D Triangulations

I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
-2
votes
1answer
28 views

understanding complexity of a function with defined function

this is the algorithm : ...
-3
votes
1answer
171 views

Print all nodes which are the endpoint of the diameter of a tree

Given a tree with n nodes, Print all nodes which are the endpoint of the diameter. 1<= n <=100000. E.g. For Above tree answer would be A,B,F,G I tried the O(n2) approach (Running Dfs from each ...
1
vote
1answer
65 views

Lower bound on comparison-based sorting of $k$-sorted arrays

In $k$-sorting array algorithms, every element is supposed to be $k$ positions from its correct positions. So with that in mind, if we used a randomized QuickSort, we will have $O(n\log{n})$. Now to ...
5
votes
1answer
121 views

Is classical algorithms a dead research field?

I'm starting my masters in CS soon, and I have to decide on a general research topic. In my undergraduate studies, I've enjoyed courses regarding data structures and algorithms the most. I'm also an ...
0
votes
1answer
27 views

Bubble sort on an already sorted collection

When I look at the following algorithm, I believe I understand how bubble sort works. ...
3
votes
1answer
360 views

Stability of QuickSort Algorithm

Def: the stability of algorithm is defined in case of the algorithm preserves same value elements while sorting as the following shows: So for this QuickSort algorithm: ...
1
vote
1answer
19 views

Lower bound for worst case running time for k-clique problem

A naive algorithm for determining whether a graph with $|V|$ vertices has a clique of size $k$ is to list all $k$-subsets of $V$, and check each one to see whether it forms a clique. Why is the ...
0
votes
2answers
59 views

Complexity of sorting $k$-sorted array using QuickSort and HeapSort

Given a $k$-sorted array where each element in the array is $k$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is ...
0
votes
0answers
21 views

Finding matches between an input string and a fixed set of strings

I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
0
votes
1answer
34 views

Solve $T(n) = 3T(\frac n3 + 5) +\frac n2$

Given recursive equation, $T(n) = 3T(\frac n3 + 5) +\frac n2$ $$ \begin{align} T(n) = 3T(\frac n3 + 5) +\frac n2 \tag{1} \label{1} \\ \lt 3T(n- 15) +\frac n2\\ \lt 3 \left(3T\left(\frac{(n- 15)}{3} +5 ...