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
30 views

Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
0
votes
1answer
47 views

Dynamic Programming - Tiling Question

I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
1
vote
0answers
68 views

Minimum vertex cover and odd cycles [closed]

Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
0
votes
1answer
32 views

Approximate bin-packing?

Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to ...
0
votes
1answer
51 views

Algorithm to find all connected objects

I'm creating a webapplication in which I render multiple objects using Three.js. These objects are saved in a list and can be connected to each other (but don't have to be), and when they are, they ...
1
vote
1answer
65 views

When and Why do I Rehash?

I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash? One reason to ...
0
votes
0answers
41 views

Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
0
votes
1answer
39 views

social network analysis - relations between people with weights

I asked this question on datascience.stackexchange but they directed me here. I have a social network represented as a set of people S and individual weights for each of person (weight is the cost of ...
2
votes
1answer
89 views

Calculate the area of the shape created by multiple paths

I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example: Basics 4 separate paths (A,B,C,D) which are a collection of ...
0
votes
1answer
27 views

Latin-1 Supplement Unicode Characters

The unicode characters under the "Basic Latin" unicode block from U+0001 to U+007F are the characters that characters we use in English. However, the "Latin-1 Supplement" block ...
1
vote
1answer
81 views

Minimum number of given operations in order to group letters in a string

Description Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
0
votes
1answer
45 views

Find Index In Sorted Array Such That A[i] = C1 * i + C2

I'm already know that there is an algorithm that can solve A[i]=i in O(log(n)) in a sorted array. But I want to know if there is any kind of algorithm that also can solve A[i] = C1 * i + C2 (witch C1 ...
0
votes
1answer
23 views

Remove features with too little variation

I have the following messy chart; As you can see some features are very stable through the time series (post-2011) like Extraversion. Is there an algorithm to remove features that do not have much ...
1
vote
0answers
9 views

Why Burrow's Wheeler Matching (FM-Index) is favored for DNA read matching

I noticed that FM-indexing is a preferred way to match strings in large data sets, and in particular DNA sequencing wiki-article. I know that with this method, it can eliminate space dependencies ...
1
vote
1answer
41 views

How does each element in the output array of a DFT correspond to a specific frequency?

I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of ...
1
vote
0answers
41 views

2SAT problem testcase does not have any strongly connected components

My task is to solve the 2SAT problem. I have read online that a good method to solve this problem would be to construct an implication graph, where each statement of the form ...
1
vote
0answers
29 views

Understanding the proof of “DFS of undirected graph $G$, yields either tree edge or back edge” better with graph for each statement in proof

I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. ...
0
votes
3answers
382 views

Greedy algorithm for vertex cover

Given a graph $G(V, E)$, consider the following algorithm: Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$) Let $v$ be one of the vertices with ...
1
vote
1answer
32 views

Why selection sort is a stable sort algorithm?

One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm. Why selection sort is unstable and ...
1
vote
1answer
53 views

Interview q: Small possible length of stick from an array of stick lengths

I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here ...
2
votes
1answer
72 views

what will be space complexity for snippet for(i=1 to n) int x=10;?

The space complexity of the code snippet given below: ...
0
votes
0answers
34 views

'Traders's Route' problem optimization algorithm

I've come up with a problem which we'll call the Trader's Route Problem (If it's an already understood problem that would be great as well, let me know). Say there exist N cities, with some arbitrary ...
1
vote
1answer
38 views

Difficulty in understanding a portion in the proof of the $\text{“white path”}$ theorem as with in CLRS text

I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path ...
1
vote
1answer
81 views

Distributed predicate computation on event stream

My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work. I'm working on a program that computes a predicate value (true or false) for ...
0
votes
0answers
24 views

Is this distribution of amount to set by weight a type of Bin Packing Problem and what are names of common algorithms to solve?

Does the following requirement, or subsets of it, have a problem name I can use to explore optimal solutions? I struggled to find a good Question Title. I need to distribute an amount(Freight) to ...
-5
votes
2answers
95 views

solving recurrence T(n) = T(√n) + theta((lg lg n))

My solution: let m = lg n. Then n = 2^m. T(2^m) = T(2^(m/2)) + theta(lgm). Let S(m) = T(2^m). Then S(m) = S(m/2) + theta(lgm). Applying master theorem, I get m^(lg1) = 1 which is asymptotically ...
0
votes
1answer
36 views

Fast query on the number of elements in a quarter plane

I have a scatter of 2D elements on a 2D plane. I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary). The quarter plane is defined by ...
2
votes
1answer
100 views

Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
2
votes
2answers
56 views

Algorithm for Estimating Number of Unique Monthly Visitors

Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as ...
0
votes
0answers
36 views

Devising an algorithm to remove “complete” sets of numbers from a list of numbers

Suppose I have a list of numbers consisting of numbers 1 through 5, where some numbers repeat. Define a set of numbers to be "complete" if it consists of each of the numbers 1-5 exactly once....
10
votes
1answer
255 views

Shortest Path in a Directed Acyclic Graph with two types of costs

I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$...
0
votes
0answers
20 views

Value Maximisation Algorithm with multiple costs

So in front of me lies different items. To buy each item you will need a certain amount of multiple things. For example, to buy a lamp, you will need to pay 3 apples, 4 oranges and 17 bananas. Each ...
0
votes
1answer
42 views

shortest paths algorithm - why backtrack from the end node instead of starting from the starting node?

I was watching a dynamic programming video by Erik Demaine . He says here https://youtu.be/OQ5jsbhAv_M?t=2133 , finding the shortest paths from S to V for all V, by guessing the node after the ...
0
votes
1answer
40 views

Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths

I have a graph like this that starts from one top node and has cycles: I need to write an algorithm to figure if node1 depends on ...
0
votes
1answer
49 views

Distribution of resources from providers to maximum number of receivers

Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what ...
0
votes
0answers
48 views

simplyfing common data values (parts of a string) in an array - by merging same attributes (data values)

I have arrays comprised of string elements like the following 2 examples. Each of the following lines is a string element of the array. example1: ...
3
votes
1answer
48 views

Merkle tree sorting leaves and pairs

I am implementing a Merkle tree and am considering using either of the two options. The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input ...
1
vote
1answer
46 views

Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked ...
1
vote
1answer
38 views

foresightful acceleration and decelerations

I am programming a CNC machine (using matlab). In order to generate a surface with a "high" shape accuracy (order of $1\mu m$) and "small" micro roughness (order of few nm) I need ...
-1
votes
1answer
43 views

How to answer the following queries on a tree?

Given a tree of "N" nodes(each node has been assigned a value A[i],node-"1" is the root of the tree), and a constant "K" , we have Q queries of the following type : [w] (...
0
votes
0answers
14 views

Encoding a arbitrary stack trace into a fixed length value

Background I would like to store the nodes of a Calling Context Tree using in a key value store. I need to be able to directly access a node by it's method name and complete stack trace. In addition ...
0
votes
0answers
34 views

Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem. I am given access to an ...
2
votes
0answers
38 views

How do you convert an NP problem which runs in O(f(x)) time in a SAT instance with O(f(x)*log(f(x))) variables in O(f(x)*log(f(x)))

I looked at the Cook's theorem at Wikipedia which presents a way to convert any NP problem to SAT but it seems to require O(f(x)^3) variables. Is it possible to remove some of the checks in the ...
0
votes
0answers
15 views

Interval scheduling problem implementation

I am learning the Interval scheduling problem, and I came up after some reading with an implementation. I'll list my steps and the code, please let me know if this is correct or there is a more ...
3
votes
1answer
67 views

Algorithm to compute average length of a simple path

Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?
3
votes
0answers
104 views

Time taken by virus to reach all nodes

Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
3
votes
0answers
40 views

I'ld like a better algorithm for scheduling tutors to fill a set of shifts

My problem is as follows: I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm. ...
2
votes
1answer
61 views

Is there a way to determine whether a list of integers can be a prefix function?

Say you had (0,0,0,1,2,3,4,5,6,7,8,9,10) or (0,1,0,1,0,1,2,3,0,1,0,0,1) Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a ...
0
votes
1answer
49 views

Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations: ...
0
votes
0answers
14 views

Global-input-local-output p-time algorithms

Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. It’s the satisfiability (SAT) problem. Each clause ...