Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
0 answers
33 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
0 votes
1 answer
83 views

Number of ways in which a '?' in a given string can be replaced with numbers from [0-9]

I came across this interesting problem in a test and I couldn't complete it. There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the ...
ABGR's user avatar
  • 101
1 vote
0 answers
43 views

Bottom-up well-balanced mergesort

If you implement mergesort top-down you can always split the input of length $n$ into one of length $\lfloor n / 2\rfloor$ and one of length $\lceil n / 2 \rceil$. This ensures that all merges are ...
orlp's user avatar
  • 13.6k
2 votes
0 answers
26 views

Nested boxes packing

I have many 3D boxes. All boxes are rectangular cuboids (they can rotate 90° so dimensions are interchangeable). The goal is to pack those boxes one into each other to minimize occupied space. There ...
27abf32fca8846's user avatar
0 votes
0 answers
28 views

Algorithm for Minimum Subset Sum Greater Than K While Minimizing Subset Size

Given an array of positive integers and a positive integer K, I need to find the minimum subset sum S greater than K, and the size of the smallest subset that sums to S. I have attempted to first find ...
mertvy's user avatar
  • 1
0 votes
1 answer
48 views

Splitting a binomial heap into 3n/8 and 5n/8 binomial heap whereas 8 divides n with O(log(n)) time

I ran into this exercise that says: With a given binomial heap with n elements and n is divisible by 8, split the heap into 2 binomial heaps, one with 3n/8 elements and the other with 5n/8 elements. ...
The Bulletbroof Joker's user avatar
1 vote
1 answer
38 views

Dynamic Programming as DAGs - Solution Always Shortest Path?

I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
Macroxela's user avatar
5 votes
1 answer
55 views

Given a set of points $S$ which is a subset of a vector space $V$, find the smallest subspace which intersect $S$ in at least $k$ points

Given a set of points $S$ which is a subset of a vector space $V$ I want to want the smallest subspace of $A$ of $V$ such that $|A \cap S| \geq k $. I suspect some variant of this problem would have ...
Sander's user avatar
  • 203
0 votes
1 answer
54 views

Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set

This question is from CLRS (3rd Edition). So, I know that this is true, but I can't seem to prove it. My approach was the following: Let $f(n) = o(g(n)) \Rightarrow 0 \le f(n) < c_2g(n)$ for some $...
Arnav Mangla's user avatar
2 votes
1 answer
37 views

Optimally partitioning the reciprocals of the first n integers

Do we know anything about the hardness of the optimization version of the multiway number partitioning problem when the set of numbers to partition consists of the reciprocals of the first $n$ ...
Alex Frechette's user avatar
0 votes
1 answer
54 views

What is the proper use case for count min sketch

Most of the sources about count min sketch say it usage is to give counts for several "items" stored "inside". However in the following this question What is the proper way to ...
Nick's user avatar
  • 105
4 votes
2 answers
91 views

Fizz Buzz and pseudo-polynomial time

I am currently taking a course on algorithms, and when reading about the 0/1 Knapsack Problem on Wikipedia I came across a technique which uses dynamic programming and supposedly runs in $O(nW)$ time, ...
414Sigge's user avatar
0 votes
1 answer
80 views

What is the proper way to calculate dimensions of count min sketch

I read almost everything I can find for count min sketch. Also look at most of the videos in Youtube, but did not found answer of a simple question - What is the proper way to calculate dimensions of ...
Nick's user avatar
  • 105
0 votes
1 answer
25 views

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define ...
Karlo Vizec's user avatar
0 votes
1 answer
23 views

Model checking algorithms

Given a knowledge base and a proposition alpha we can check if our knowledge base entails alpha using a model checking algorithm that functions as such : we generate a set of all the possible models ,...
red wood's user avatar
3 votes
2 answers
1k views

Find 1s in almost all 0 array using comparisons only

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python): ...
user555076's user avatar
7 votes
3 answers
144 views

Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem ...
tgnome's user avatar
  • 153
1 vote
0 answers
35 views

Choosing one element from each partition that minimize the difference between max and min

Given an unsorted array $A$ that contains $n$ elements of numbers. Also $A$ partitioned to $k$ lists $A_1,A_2,A_3,\dots,A_k$, each contains at most nearly $\frac{n}{k}$ elements. We choose exactly one ...
ErroR's user avatar
  • 1,942
1 vote
1 answer
53 views

Knapsack Problem: Find Top-K Lower Profit Solutions

In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table": ...
slaw's user avatar
  • 111
0 votes
2 answers
67 views

Correctness proof of bubble sort(bogus proof)

I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction. Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for ...
user146551's user avatar
0 votes
0 answers
28 views

Pseudocode for a noising scheme

I am trying to recreate the code for a paper. The paper describes a noising scheme like the following. $z = f(x) +S(x) \cdot \epsilon$ Where $\epsilon$ is the noise we call echo noise. It is because ...
Partha Thakuria's user avatar
-1 votes
1 answer
72 views

Examples of algorithms best their class that require cyclical data structures

I remember that the Roc Lang website claimed that their choice to forbid any form of cyclic data structures prohibited their customer to implement some of the best in their class algorithms, id est ...
Delfin's user avatar
  • 99
1 vote
1 answer
49 views

Algorithm that finds points that are closest to the middle of rectangles in grid

Suppose I have an array of 2D coordinates {x:number,y:number}[]. What would be an algorithm that could get me the points that, were an X by Y grid of rectangles laid over the cartesian graph created ...
LCIII's user avatar
  • 113
0 votes
1 answer
36 views

Knapsack Problem for Fixed weight and Fixed price

Is the knapsack problem for a target weight, let's say 1000 for example, and a target price, let's say 10000, still an NPC problem?
Arugo's user avatar
  • 59
4 votes
2 answers
127 views

Finding optimal sequence of attacks to minimize number of soldiers needed

The problem Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this: You are given a list of enemy bases ...
user2891462's user avatar
0 votes
1 answer
135 views

what is the complexity of this sorting algorithm?

...
Arugo's user avatar
  • 59
7 votes
1 answer
585 views

Possible Mistake in Skiena's Algorithm Design Manual

In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that $$ mn - m^2 + m \in \Omega(mn) $$ where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
Joshua's user avatar
  • 173
0 votes
0 answers
110 views

Interval scheduling; sort by ending times

You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
Lipid's user avatar
  • 9
2 votes
1 answer
357 views

Potential of Artificial Intelligence to improve algorithm for PI

Recently AI (alphazero) was used to improve practical matrix multiplications by around 10 to 20 percent. Alphageometry and ramanujan machines all came into existence in the recent years as well. Seems ...
siminsimin's user avatar
1 vote
0 answers
42 views

Update priority of existing item in a minmax heap

Say you have a double ended priority queue in the form of a minmax heap as described here. What is the most efficient algorithm to update the priority of an existing item? Assume that I explicitly ...
Bogey's user avatar
  • 133
4 votes
0 answers
123 views

Constructing worst case for L* by D.Angluin

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
12 votes
1 answer
1k views

How to find a "short" walk that visits all vertices of a strongly connected directed graph

I am interested in the following algorithmic problem: Given a strongly connected directed graph $G$, I want a "short" (see below for what I mean by short) walk that starts with an arbitrary ...
Michal Dvořák's user avatar
2 votes
1 answer
163 views

Given two sets of integers find an integer in the first set furthest away from all members of the second set

If given two sets of integers how can I find an integer in the first set furthest away from all members of the second set. The distance of two integers is the absolute value of difference of the two ...
hovnatan's user avatar
  • 123
0 votes
0 answers
42 views

Why we could run the algorithm on Linear Bounded Automata?

Suppose there is an algorithm $\mathcal{A}$ for the problem $\Pi$ that halts on any instance $x\in\Pi$. Someone tells me that we can run $\mathcal{A}$ on Linear Bounded Automata, but I can't ...
ErroR's user avatar
  • 1,942
2 votes
1 answer
45 views

Why does Hopcroft-Karp only work on bipartite graphs?

I have a simple question which I cannot answer, and it relates to this question. What I cannot answer is this: Why does a graph with bidirectional edges destroy the "bipartiteness" of the ...
Joff's user avatar
  • 155
1 vote
0 answers
28 views

Inefficient double lengthening PRG [closed]

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
Stevie's user avatar
  • 141
0 votes
0 answers
22 views

Search a list of conditions

If I have a list of conditions: and(a,or(b,c)) not(b) or(a,c) and(a,d) or(or(or(a,b),c),d) and I'm given values for these conditions, let's say, ...
Gatonito's user avatar
  • 111
2 votes
1 answer
67 views

Seeking help in designing an algorithm

I am not a computer science nor a math person, but if given a pseudo-code or a English outline of steps. I can probably fumble my way through and write some code. I Apologize for the wall of text/...
Scott Watson's user avatar
2 votes
0 answers
122 views

Find the longest northeast path in $O(n\log n)$ time

Given a set $Z$ of $n$ points $(p_1,p_2,p_3, \ldots,p_n)$. The coordinates of these points are arbitrary numbers and are unsorted. If they give me $s$ and $t$ to be two points in $Z$. A northeast path ...
coding's user avatar
  • 121
1 vote
1 answer
97 views

Quick sort with $K-1$ pivots

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
Haaziq Jamal's user avatar
0 votes
0 answers
28 views

Page miss in 2Q Cache Replacement

I am studying about 2Q Cache Replacement Policy and i came across this post. They have worked out an example with the following page keys [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] and cache memory of 5 ...
user avatar
1 vote
1 answer
147 views

SAT solvers for counting the number of solutions

Are there existing SAT solver libraries that can count the number of solutions of a boolean formula? Can you give examples? I mean implementations more efficient than the naive approach, i.e. each ...
Fabius Wiesner's user avatar
2 votes
2 answers
67 views

Turning stacked overlapping intervals (with associated data) into non-overlapping intervals

I'm looking for an efficient algorithm to merge a list of overlapping intervals (each of which has data associated) into non-overlapping intervals. In case two or more intervals overlap, the latter ...
Johannes Weiss's user avatar
0 votes
0 answers
59 views

CSES Sliding Cost - why is this formula for updating the cost correct?

In the CSES problem Sliding Window Cost, given an array and an integer k, we are asked to compute the minimum cost for each sliding window of fixed size ...
Andrei Onoie's user avatar
1 vote
1 answer
63 views

Find all the induced paths with a start vertex

Let $G$ be a graph and let $v$ be a vertex. Is there a polynomial algorithm for the following operation? Operation. Find all the induced paths in $G$ with first vertex $v$. Background This problem is ...
licheng's user avatar
  • 405
1 vote
0 answers
43 views

Is there a proof for camerinis algorithm for finding a minimum bottleneck spanning tree?

Does someone know a proof for Camerinis Algorithm for finding a minimum bottleneck spanning tree? To my knowledge its the only algorithm that performs in linear time to solve this task but I cant find ...
identicon's user avatar
0 votes
0 answers
23 views

Given two paths, how can I merge them in a Divide-and-Conquer algorithm to find the optimum earning route given a set of points with rewards?

The problem statement is the following: given a non-empty set P of (x, y) points with an associated reward, find the path through P that gives the maximum earning. The earning of a path is the sum of ...
synzgrsck's user avatar
1 vote
1 answer
82 views

Disconnection of a directed and weighted graph

Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive. In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$. The question asks to find a ...
Daniel's user avatar
  • 71
0 votes
0 answers
61 views

Find an independent set in which the cumulative sum of weights is maximized

I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such ...
Farah Mind's user avatar
1 vote
1 answer
104 views

Complexity of recursive function using Master theorem

this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out ...
Arugo's user avatar
  • 59