Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
4 views

Specialized Algorithm for Set-Cover with $k=3$

I know that the Set-cover problem with $n$ elements and a universe of size $N$ is NP complete. Also, the problem is Fixed-parameter tractable regarding the number of sets $k$ that should cover the ...
-1
votes
0answers
2 views

What would be the most efficient alghorithm to use in the case of a “expanding pixel” on a 2d field

You have a 2d field of size X, every point on that field can be treated as a pixel so it has a color, at the start all pixels are white. You then select a point on the field with a different color ...
0
votes
0answers
15 views

Algorithm to determine how fuel efficiently a driver is driving

I need to define an algorithm for how fuel efficiently a driver is driving, but I'm a total novice in the area of computational models so I'm not sure if I'm doing this right. I have formulated the ...
0
votes
1answer
15 views

Modify max value multiple times of a list

I have two lists say A and B, each consisting of n positive integers. I make a list C such that each element of C i.e., Ci=Ai*Bi for each element Ai in A and Bi in B. Now I have to update the value of ...
4
votes
3answers
60 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
0
votes
0answers
7 views

Alternative technologies/theories for a “Git for Structured Graph Databases”

Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...
1
vote
1answer
21 views

Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?

In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp. This timestamp is used to order all the events in a distributed system. The rule ...
2
votes
0answers
21 views

Weighted Sorting Algorithm

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...
1
vote
1answer
21 views

Lamport logical clock: what does partial mean in the concept of `Partial ordering`?

In lamport's paper[1], he define two concept The partial ordering and The totally ordering. What does partial mean in ...
-3
votes
0answers
29 views

Write a C program which has a function COM that take two strings (character array) A,B [on hold]

Write a C program which has a function COM that take two strings (character array) A,B and output "A is smaller" or "B is smaller" if string A is smaller than string B. We say A is smaller than B if ...
0
votes
0answers
8 views

Where can I find technical historic information about the facebook? [on hold]

I mean, in which language/s it was programmed in the beginning, and which program components it contained, and how it changed over the years from a technical point of view and the reason for these ...
0
votes
0answers
51 views

Markov's Inequality and Hashing

Let H be a universal family of hash functions from U = {0, 1, . . . , u − 1} into a table of size m. Let S ⊆ U be a set of m elements we wish to hash. Prove that with probability at least 3/4, no list ...
0
votes
0answers
41 views

Expected Number of Collision Pairs

I have been attempting to solve this problem for hours, but cannot seem to comprehend how to come to the solution. Let $H$ be a universal family of hash functions from $U = \{0,1,\ldots, u − 1\}$ ...
0
votes
0answers
15 views

Can ideas of maximum flow be used to solve the problem of traffic?

So I'm considering the problem of traffic congestion. I was wondering if it is possible to solve the problem of Maximum Flow on a graph representing a city, at least in theory (lets say you have ...
0
votes
0answers
17 views

Best data structure to store and query ip-address ranges

I would like some input on what is the best data structure to store and query ip-address ranges. I will have v4 and v6 ip-address ranges. The number of ip-ranges will less than 500.
1
vote
2answers
35 views

Big-O Solving Recurrence Relation by iteration with fractions

I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
0
votes
1answer
20 views

Is this algorithm for partial ordering of sets complete and sound?

I need to build a partial order tree of sets for analysis. Where the order is defined as A <= B <=> for all x in A, y in B, x <= y. I realized that if ...
0
votes
0answers
27 views

Recursion func to get list of objects

I want to write code that returns a list of $X_i$ values base on this logic. Assuming $X> 1$ a positive non decimal number, and $n$ is the number of objects: $X_n = X-X_1$ $X_i = X_{i+1} / 2$ $...
1
vote
0answers
19 views

Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= node). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
2
votes
1answer
18 views

Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy ...
1
vote
0answers
53 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
3
votes
1answer
40 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
-1
votes
0answers
15 views

Codechef SnackDown Question #1 [on hold]

I'm newbie to competitive programming, so tried to solve https://www.codechef.com/SNCKQL19/problems/QUALPREL this question, I've write my solution, and also verified my code on custom inputs, they all ...
1
vote
0answers
12 views

Can we compute edit distance in strongly sub-quadratic time?

Can we compute the edit distance between two strings of length $n$ in strongly sub-quadratic time, i.e., in time $O(n^{2−\epsilon})$ for some $\epsilon>0$?
0
votes
1answer
21 views

Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?

I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says : In computational complexity theory, nondeterministic algorithms are ones that, ...
-1
votes
2answers
25 views

What does “Giving an overall running time” mean in this context?

In the following image The author refers to an overall running time linear to |E|. But the author then says this is at most O(n^2). This seems contradictory because O(n^2) is quadratic time. Did the ...
1
vote
1answer
97 views

Probability that a random hash from a universal family is injective

This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows: In class we saw universal hashing as the solution to ...
-1
votes
0answers
51 views

Algorithm Design: Arranging Books on Shelves [on hold]

The public library is opening a new section on 21st century technology books, and have employed you to arrange the books on shelves. The books don’t all fit on a single shelf, so you must decide how ...
0
votes
0answers
24 views

Algorithm for generating formatted numbers

I need an algorithm for generating numbers in this format: xxxxxx xxyyxx xyxyxy Where x & y have value between 0 and 9, and x != y. I guess this is a common problem, can someone point me in ...
0
votes
0answers
13 views

algorithm to static allocation of previously known size and order

I need to allocate and free sizes of memory statically (not in run-time). The different between this and the dynamic allocation problem is that I know exactly when everything is going to happen. e.g. ...
0
votes
0answers
13 views

Can we update a cut-block tree in linear-time?

Every graph $G$ admits a cut-block-forest decomposition. This is a forest $F$ where each node corresponds to a maximal 2-connected component (called block) in $G$ and two nodes are adjacent in $F$ if ...
4
votes
0answers
138 views

Check if two items are equal after replacing

Let's say that an item is either a natural number or a list of items. Examples of items are: 1 [2] [4, [3, 1], 3, 4] A rule states that two items are equal. For example: 1 = 2 3 = [3, 1] [4, 3] = [...
0
votes
1answer
28 views

KMP - longest palindromic prefix

I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word. I've seen this algorithm used for determining if a word is rotation of ...
0
votes
0answers
9 views

Given specification of an iterative program correctness proof (python), then give the loop invariant and the partial correctness

(a) Given an appropiate loop invariant (b) Use your loop invariant from (a) to prove partial correctness (when loop terminates) (c) Define an appropriate expression for the purpose of proving ...
0
votes
1answer
30 views

How do I determine the basic operation of this algorithm?

Admissions: Yes, this is a homework assignment. No, this is not me trying to outsource my homework to the internet. I am honestly fazed by my teacher's explanation of the "basic operation", and the ...
1
vote
1answer
29 views

Proving correctness of search algorithms

I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof. ...
1
vote
0answers
30 views

Definition of PrefixSum function

I came across this paper and attempting to go through the implementation of randomized selection algorithm on page 8. Step 1 of the algorithm suggest to compute $s = PrefixSum(n_i, p)$. Where $p$ is ...
0
votes
1answer
52 views

Similar to point location

I have a following problem: Given a set $S$ consisting $N$ triangles (possibly overlapping). Answer queries (online) of the form: given a point $P$ is there a triangle $T$ in $S$, such that $P$ lies ...
-1
votes
0answers
25 views

Delete Items in a stack recursively using pop, push and isEmpty [on hold]

given a stack, generate 10 random items (numbers), push the items into the stack, and delete an item(x) in the stack using recursion. The catch is you can only the pop, push, isEmpty functions in ...
0
votes
1answer
29 views

Visit all vertices of a graph

I need to find the fastest route passing in all vertices Each vertex is a class. I can choose the number of classes for semester. Some classes have prerequisites (A and B need to be done one semester ...
0
votes
1answer
32 views

Evaluating two different Algorithms, which one will scale better?

I'm evaluating two different algorithms to choose one for my implementation, they just do calculations on top of arrays, get some input of $n$ elements, and produce some output of $m$ elements, and I'...
0
votes
1answer
59 views

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
1
vote
1answer
37 views

What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory?

I am a master computer science student, and I am interested in both geometry and complexity theory. So I would like to know what is the relations between discrete geometry, computer graphics, and ...
0
votes
2answers
47 views

Understanding how quicksort operates

I am having a hard time understanding the quick sort partition operation. I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand ...
1
vote
1answer
45 views

A simple way to find the feasible region of a system with simple constraints

I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem: I start out with this ...
0
votes
1answer
18 views

Longest common sub-sequence code error

I was trying to convert the LCS algorithm (CLRS p. 394) into python code, but finally, the code does not return the expected result. The code takes two sequences and returns the longest common ...
0
votes
1answer
34 views

Trying to find all possible combinations

I am trying to find all the combination of options trades that make the highest profit. Each trade has a maximum profit and maximum loss. I have a list of maximum losses e.g. [5298, 1100, 500]. Each ...
0
votes
0answers
13 views

Signing Files' checksum [closed]

I was having this problem: I have a case where user A sends user B a big file, then user B should check the file and sign it, then send back the signature. My first thought is that a big file would ...
0
votes
0answers
13 views

Reach the nth stair using step a-b while some stairs are broken

Description A person is standing below at a staircase having $N$ steps. Considering he can take a leap of between $a\geq1$ and $b\leq N$ steps at a time. In the meanwhile, some of the stairs are ...
-2
votes
1answer
37 views

Please help, I have been attempting to understand Quicksort for 9 hours now with little luck!

I have done absolutely everything that i could to try to understand this algorithm. I did NOT want to go on without understanding it completely even though I know it might only be a single problem in ...