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
1
vote
1answer
79 views

How to prove the my greedy algorithm for placing guards?

Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
0
votes
1answer
35 views

an algorithm to find the shortest path between two vertices whose weight is divided by 3?

I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}_+$ (which means giving every edge in the graph a positive weight), and a source ...
3
votes
0answers
76 views

Remove a subsequence from a string and append it at the end

Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
2
votes
1answer
67 views

Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
0
votes
0answers
34 views

A claim regarding Huffman tree?

I saw the following claim: Given $Q=\{1,2,\dots,n\}$ and $f$ (positive function) such that: $$f(1)>f(2)>\dots>f(n)>f(1)/3$$ Then there are leafs at maximum 3 different levels of Huffman ...
0
votes
0answers
42 views

Find coordinates of points when distance is known amongst them

Lets say I have 6 point name A, B, C, D, E, F. Distance between a point and it's nearest 3-4 points are known i.e the displacement. Now I want to assign x and ...
0
votes
1answer
61 views

Prove Edited Algorithm of Bellman–Ford?

Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that. I am stuck on this question for a week and hope to get some ...
0
votes
0answers
49 views

All strings in a range with a given prefix and suffix

Given a decimal number N (which has at most, 10^6 digits, actually we should look at it as a string!) and another decimal number M (which has K digits, 1 <= K <= 10^6 ), we are asked to find all ...
0
votes
1answer
22 views

List the lengths of all the prefix-suffixes in $O(n^{1+\epsilon})$ time

A proper prefix of a string $s$ that is also equal to a suffix of $s$ is called a PS (prefix-suffix). Given a string $s$ of length $n$ is there an algorithm listing the lengths of all the PSs in $O(n^{...
0
votes
0answers
17 views

How do I group elements of a list into windows of predefined sizes with minimum cost given longer windows are cost efficient?

You are given a list of days numbered 0 to 365 in the calendar year where you need to be in a hotel. You need to book in advance for the year and need not necessarily be there when you have a booking. ...
1
vote
1answer
32 views

Map two arrays given a map of possible mappings

Given two integer arrays a and b and a map m which for each element ...
0
votes
0answers
42 views

identify nodes with paths of unique length from source

Let us consider a Directed Acyclic Graph $G(V,E)$ such that all edges have unit weight. Let $s$ be a source node, $s\in V$ and a set of destination nodes, $D\in V\backslash s$. My problem is to find a ...
2
votes
1answer
42 views

Alphabetical order under which list of strings is lexicographically sorted

We are given an array of $n$ Strings with total Length $K$, and we are asked to find an alphabetical order (if one exists) with respect to which the array become lexicographically sorted. The time ...
0
votes
1answer
30 views

Extending Suurballe's disjoint path algorithm

I have implemented Suurballe's and Bhandari's algorithms into a project I am currently doing based on this: http://www.macfreek.nl/memory/Disjoint_Path_Finding And it seems to work really well. ...
0
votes
0answers
13 views

Record Linkage - Supervised vs Unsupervised

I've been tasked with figuring out the best way to implement record linkage between multiple data sources. My suspicion is that supervised approaches will increase accuracy over unsupervised ...
-1
votes
0answers
14 views

Fastest type of centrality to compute

I should calculate the centrality (any type) of an unweighted graph. The graph contains 1500000 nodes and Brandes' algorithm for Betweenness centrality is too slow. I have also looked for ...
1
vote
1answer
29 views

Parallel algorithm for finding the maximum in $O(\log \log n)$ time

With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is: If $...
2
votes
1answer
38 views

Number of subsequence with k distinct characters

"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order." Suppose we have string s="aabca&...
0
votes
0answers
69 views

Suggest a Data Structure that support the following operations with time complexity O(log(n))

I’m looking for a data structure that supports that store the salaries of it’s employees. Insert(e) – Insert employee e into the data structure. AvgDecile(k) – Returns the average salary of the k’th ...
1
vote
1answer
46 views

How to find simple polygons in a complex polygon created by two lines

Given the image attached, I am looking for a way/strategy/pseudocode to iteratively find each polygon created either by two blue-dotted line segments, a blue-dotted line segment and an intersection, ...
0
votes
0answers
9 views

Best sparse matrix structure for Lanczos algorithm and/or matrix-vector multiplication

I have written a Lanczos routine which I am using for some problems in physics. Now, I would like to feed it some sparse matrices with very low densities (hamiltonians of large systems), and for that ...
3
votes
1answer
31 views

Algorithm to Compute High Water Mark

I saw this algorithm question which is as below. There is a server that receives request Ids that are positive integers. The High Water Mark (HWM) for the server at any instant of time is defined as ...
1
vote
2answers
38 views

Probability that two specific elements are in uniformly random sample

Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4. Essentially we are given a stream of $N$ elements and wish to maintain a uniformly random sample, $S$, of size ...
0
votes
0answers
23 views

Tangled cable - divide and conquer

Tangled cable: Let's have a long cable, from both ends of which protrudes n wires. Each wire at the left end is connected to just one at the other end and we want to find out which one. To do this, we ...
1
vote
3answers
357 views

Minimum number of increment / decrement operations to make an array distinct?

I've been stuck on this problem for some time now.. Given an array A of size N that ranges between [1..N], a "move" is to increase or decrease an element (by 1). After each move the array ...
1
vote
0answers
29 views

A beginner's question on programs that can search and calculate in very large sets

I am not in the computer science field and was looking for some guidance on books/papers/programs that allow me to learn how to design algorithms for problems that involve very large number of ...
2
votes
2answers
656 views

Meaning of Epilogue in Computing

Wordsense.eu gives a definition of epilogue as (computing) A component of a computer program that prepares the computer to return from a routine. I’d like to know more & haven’t been able to ...
0
votes
2answers
35 views

How to get the expected time complexity of while loop?

How to get the expected time complexity of while loop below? ...
6
votes
1answer
73 views

Number of combinations without given pairs

Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k. I need to count how many combinations of size k exist which ...
3
votes
0answers
53 views

How to replace the max distance of a bounded set of points with a random point in less than $O(n^2)$?

Context Let's say I have a finite set of points of size $N$. I can represent the points in a metric space and then compute distances between them. My goal is to replace a point in the set with another ...
6
votes
0answers
152 views

How to sort a queue using a temporary stack?

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack We are allowed to make only two actions: Action "x": Dequeue an element from the queue and push it ...
0
votes
0answers
17 views

What do you mean by programming the physical layer of the processor?

I was just researching the startup ecosystem for a school project and came across an article which I don't fully understand. The quoted part is: Ravuri says that EdgeQ stands in the middle between ...
12
votes
3answers
2k views

How can I quickly judge whether matrix A is the inverse matrix of B?

How can I quickly judge whether matrix A is the inverse matrix of B? This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution ...
0
votes
2answers
58 views

What is a good path for self-study of CS foundations/fundamentals?

I’m a self-taught software engineer who’s been working in industry for 12 years. I don’t have any formal education in CS and math was never my strong suit (although I’m willing to do the work to make ...
0
votes
1answer
60 views

How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

Can somebody help me with this recurrence please? $T(n)=4T(\sqrt{n}/3)+(\log n)^2$
2
votes
0answers
31 views

Min Cost Max Flow algorithms for providing multiple solutions

Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
0
votes
2answers
48 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
-1
votes
0answers
35 views

FollowUp to previous question, minimum spanning tree?

Regarding my previous question which I am going to quote: Minimum Spanning Tree (MST) in graph? Given an Undirected graph G with with weight on its edges and 2 different minimal spanning trees: T, T' ...
-3
votes
0answers
22 views

Developing a puzzle solver Problem Programing

I have a project at my school. This is problem. I don't have any idea to solve it include of recursion. Please help me give me the solution or any idea to solve it. Many thanks!
2
votes
1answer
82 views

Algorithm to construct a parabola that hits a given target and avoids given boundaries

I'm working on a video game and I'm struggling with the math behind one of the enemies. The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at ...
-2
votes
0answers
47 views

An Dynamic Programming algorithm for this problem(Largest Tower)

We have some blocks of the tower(n) with the same Height(each of them has 1 as its Height) each block has Weight(w) and maximum Tolerable weight(L).each block can withstand a certain weight(L). if a ...
0
votes
1answer
27 views

Find a repeated element in linear time

Given an array of $n$ elements, containing values in the range $[1, n-1] $ (assume $ n > 1 $) this implies there is at least one repeated element. The problem is to get one of the repeated values ...
4
votes
1answer
146 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
2
votes
1answer
64 views

$\epsilon$-approximation Sub-linear time monotonicity testing

I have the following exercise I have been staring at for several hours to no avail. Question: Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ ...
0
votes
0answers
37 views

Classification of a box relative to a line algorithm

I'm having trouble understanding the correctness of the following algorithm: why is the choice of the $p_n$ coordinates correct? Also, in figure 3.8 $n$ is pointing left and up, so according to figure ...
0
votes
0answers
22 views

Is correctness implied by an optimality proof?

New to proofs (in the context of analysis of algorithms). I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
0
votes
1answer
20 views

Best split with conditions

Given this sort of dataset: ID Score1 P1 Flag id1 0.01 0.2 False id2 0.99 0.9 True ... ... ... ... The limitations of each variable are: ID: identifier if each object, unique in the table Score1:...
2
votes
0answers
32 views

Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

We have an algorithm problem in hand, can you please write your ideas about this, thank you! There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
0
votes
2answers
39 views

Is every problem with an output's size that grows polynomialy np?

I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$? My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic ...
0
votes
0answers
26 views

Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem. I understand how the solution is implemented but,...