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
1answer
32 views

Area preserving distance optimization

I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find ...
2
votes
0answers
94 views

Dynamic job scheduling with earliest time and deadline

I have a real life algorithmic problem and I'm trying to find out if there is any similar widely known algorithmic problem with known solutions that I could adapt to my particular use case. I want to ...
9
votes
0answers
328 views

Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics: Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
2
votes
2answers
185 views

Partitioning a graph into subgraphs with overlapping nodes

I'd like to partition a graph into subgraphs with overlapping nodes. To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...
0
votes
0answers
14 views

When can theta be used for different values? [duplicate]

On the course material I am following we have been given an explanation for theta as being when omega and Oh 'sandwich' the run time, so it is bounded between the two values, at least I think this is ...
2
votes
1answer
53 views

Difficulties proving when a language is in P or is NP-complete

I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$: $L_1 = \{...
2
votes
1answer
20 views

Linear separability

I have an assignment in linear programming and this question was asked: given an input of two data sets $P_1,P_2$ containing points $(x,y)$, create a linear program that finds an equation of a line ...
0
votes
1answer
57 views

Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$

Hope you had a fantastic christmas break :) I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express ...
0
votes
1answer
184 views

number of ways evaluation of expression such that value not changed [closed]

one example: How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
2
votes
2answers
40 views

Prerequisites for studying parametrized complexity

Which areas of CS/Math should one have mastered before diving into parametrized complexity?
1
vote
0answers
24 views

Are there P problems with no known polynomial-time algorithm? [duplicate]

As the title says, I'm just curious if there are any problems with polynomial-time algorithms, but where no polynomial-time algorithm for it is currently known? Of course, this question would be ...
1
vote
1answer
53 views

Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path

Summary: A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain ...
0
votes
0answers
18 views

Extending the token bucket algorithm

I've been looking at implementing a local rate limiting solution satisfying certain guarantees. I've found surprisingly little literature on the extensions of the token bucket algorithm to hierarchies....
4
votes
4answers
191 views

Enumerating all partial permutations of given length in lexicographic order

I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, ...
0
votes
1answer
115 views

Algorithmic challenge: generate a list of random non overlapping squares

For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap. So the challenge is simply: given a two dimensional area $a$ (...
1
vote
0answers
60 views

Can we make at most 3 comparisons in the closest points algorithm instead of 7?

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
3
votes
1answer
75 views

Greedy algorithm for subset sum on powers of 2

I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after ...
1
vote
0answers
19 views

Depth two tree CBQ rate limiting

Context: I'm operating a service with 5 accounts simultaneously servicing tens of millions of users. The accounts using the service have extreme bursts due to various campaigns by each account and the ...
0
votes
6answers
138 views

What algorithm do computers use to compute the square root of a number?

What algorithm do computers use to compute the square root of a number ? EDIT It seems there is a similar question here: Finding square root without division and initial guess But I like the answers ...
0
votes
1answer
21 views

Floyd Warshall with constraints

I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths ...
1
vote
1answer
115 views

Why is backtracking a necessary step in the Maze problem?

The problem I am working on is specifically this: A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower ...
1
vote
2answers
43 views

What are the units for time complexity graphs?

I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one: I know the x-axis represents ...
0
votes
1answer
36 views

LinkedList: Remove the kth node form the end

Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be ...
0
votes
2answers
55 views

How can I get index of combination from element indices

An array of combinations is generated from two arrays, ...
0
votes
1answer
37 views

How to prove that insert complexity in binary search tree is minimum O(log n)?

Is it connected to BST search O(log n) or height log n? How to prove that insert will give give you correct BST in minimum O(log n) time?
9
votes
2answers
271 views

NP-hardness for one-dimensional facility location problem with entrance fee for each customer

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
0
votes
0answers
52 views

Dynamic programming algorithm to find largest triangle in binary square matrix where elements equal “1”

I'm struck how to find DP recurrence for: You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1, q >= 1, L >= 1, p+L >= n+1, and q+L >= n+...
2
votes
1answer
56 views

Find nth number which does not contain the digit c

This problem was given to 9-graders. We write down numbers except for the ones which contain the digit c. Find the nth such number. I looked at the indications, but the algorithm used there stumped me....
0
votes
1answer
37 views

How to read a number from highest place value to lowest?

So we all know it's easy to read a number from lowest place value to highest. A simple algorithm would be like : while(n): a=n%10; n/=10; but the question ...
2
votes
3answers
232 views

For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

in my notes I have one fact: in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
1
vote
1answer
45 views

Determine if there's a $P_3$ as an induced subgraph in a graph $G$

Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices). What I was ...
0
votes
0answers
25 views

Eliminate equal sub-paths of directed cyclic graph

Suppose we have a directed cyclic graph and a list of paths. What is the shortest way (including parallelization) of eliminating all equal paths and paths that are sub-paths of others? For example, ...
0
votes
0answers
27 views

LCA for directed graph with cycles

I am trying to find the lowest common ancestor of 2 nodes in a graph with more than 250000 nodes and ...
2
votes
1answer
31 views

Finding pair of sum in sorted array in time complexity less than $O(n)$

In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. ...
0
votes
0answers
36 views

How to express a parabola as a Bezier curve

I need to create a parabolic shape with a given starting point, maximum point, and end point. I thought the most efficient way to do this is to use a bezier curve. However there is no major ...
1
vote
1answer
58 views

Can the loops be in any order in the Floyd-Warshall algorithm?

I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page: ...
2
votes
1answer
104 views

Comparing two algorithms for all-pairs shortest paths

I read in my notes: If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, ...
0
votes
1answer
77 views

4 Vertex Cover Problem is not NP Complete why?

With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?
0
votes
1answer
74 views

How can I do a subtraction on unary numbers terminated in X on turing machine?

For example, if I have 11X1111X as input, the result should be X. For another example, input: 1111XX -> 1111X. I am a complete beginner and all my tries so far failed to meet the expectation. This ...
0
votes
0answers
35 views

How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk)?

How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk) this is part of answer: my problem is that how do we say the last line? how do we know ${...
1
vote
1answer
35 views

Time complexity of the travelling salesman problem (Recursive formulation)

According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (...
0
votes
0answers
15 views

Min-plus matrix and Shortest path variation

I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes. One method is : let ...
2
votes
1answer
96 views

Number of nodes at given depth in binary tree

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction ...
0
votes
1answer
44 views

How efficient of this prime sieving algorithm?

I just found there is an old program of mine where I implemented the following prime sieving algorithm: ...
-1
votes
2answers
45 views

Write a pseudo code for a Graph algorithm

Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value ...
0
votes
0answers
43 views

For every node of a tree, find the nearest ancestor node such that val[node] is coprime to val[ancestor]

Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note ...
1
vote
1answer
36 views

Runtime Complexity of Memoization

I am struggling to analyze the runtime complexity of the following algorithm formally: Given a string s and a dictionary of words dict(wordDict), add spaces in s to construct a sentence where each ...
2
votes
2answers
153 views

Algorithm To Compute The Gaps Between A Set of Intervals

Problem Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints ...
0
votes
1answer
32 views

Calculate the sum of all sub-arrays with given indices

I am new to Algorithms and Competitive Coding. I have a problem as follow: For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic ...
1
vote
0answers
16 views

Why divide a stack into two parts and store them separately in main-memory and hard-drive a bad idea?

I'm learning data structure and trying to solve problem related to Computer Game like Chess/Go. There is a line in my book on the section of DFS algorithm, which is implemented by two stacks: one for ...

1
3 4
5
6 7
186