Stack Exchange Network

Stack Exchange network consists of 175 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

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.

1
vote
2answers
105 views

Could all CPU instructions get fundamentally faster if a better multiplication method was developed

I was reading the article Integer multiplication in time O(n log n) by David Harvey and Joris Van Der Hoeven, 2019. Could this discovery increase the throughput of future CPU's? If so could we ...
3
votes
0answers
77 views

How to cover holes with disks of a fixed radius? [closed]

So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These ...
1
vote
2answers
35 views

Space-efficient representation of potentially very large arbitrary-precision rationals?

I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to: 2/3 1/10 4 * 10 ^ 1,000,000,000,000 I know arbitrary precision ...
3
votes
0answers
47 views

Self intersection in a simple polygon

Suppose I have a simple polygon whose vertices are $p_1,\ldots,p_n$ each $p_i \in \mathbb{R}^2$. Suppose now I pick two distincts vertices $p_i,p_j, i\neq j$ Is there some algorithm I can use to test ...
2
votes
1answer
43 views

What is an approximation factor for the Greedy Motif Search algorithm?

What is approximation factor for the Greedy Motif Search algorithm? I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native ...
1
vote
0answers
23 views

Grouping numbers so they approximate their total divided by two

Given an array of numbers, I would like to find an algorithm which divides them into two groups, such that the sum of the numbers in each group is as close as possible to half of the sum of all ...
1
vote
1answer
19 views

How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

If I have the following system, I am wondering how to calculate the number of valid strings it contains. The system is something like this, which can have arbitrary variations. Only consists of an ...
0
votes
1answer
38 views

Worst Case Scenario for Quicksort algorithm with pivot element n/2

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the ...
2
votes
1answer
95 views

Solve Maze Without Feedback

Suppose that we have the following maze (_ = open, + = blocked), and we can move left,right,up,down: ...
3
votes
1answer
51 views

Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

I'm TA'ing a course and have trouble solving an exercise. Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[...
2
votes
2answers
166 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
1
vote
0answers
81 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function: $$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$ where $...
0
votes
0answers
15 views

What is the correct way for beta reduction of lambda terms

my answer : (\x.\y.y)(xx) -> (\y.y)x -> y correct answer: (\x.\y.y)(xx) -> (\y.y) I was wondering would it be reduced one by one from left to right ? it seems the correct answer takes the whole (xx) ...
2
votes
1answer
42 views

In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
0
votes
0answers
15 views

Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
0
votes
1answer
33 views

Is it possible to compute how many iterations this algorithm will take?

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always ...
0
votes
0answers
7 views

Linear time addition of binary numerals using only primitive recursion and case analysis

Given binary numerals encoded like (in Haskell for example): data Bin = Z | T Bin | TI Bin With Z being 0, ...
5
votes
3answers
391 views

How do we place $8n$ objects in a grid of size $n \times n$?

How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in ...
0
votes
2answers
24 views

Don't understand minimax algorithm in terms of chess

I'm new to minimax algorithm, but i understand it's entire concepts as it's easy, my biggest issue is understanding it's implementation to my chess game, no internet solution answers this question ...
1
vote
3answers
78 views

Do all recursive problems have optimal substructure?

I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved ...
1
vote
1answer
32 views

Algorithm To Process Purchases Efficiently and Apply Constraint

I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows: ...
2
votes
1answer
180 views

The origin of list data structure

Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
2
votes
2answers
51 views

Is purely functional programming in some situations less efficient than imperative programming?

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
1
vote
1answer
25 views

Time complexity of finding subsequences of a string segmented into parts

Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3. Then, we split $S$ into $N/3$ equal parts, each of length 3. For each equal part,...
3
votes
3answers
81 views

How to check if a list of XY coordinate meet the safety distance to each others?

My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I ...
1
vote
0answers
34 views

Time complexity of an algorithm for finding a cycle of fixed length

I am considering the following algorithm for obtaining a cycle $C_k$ of fixed length $k$ in an undirected graph $G$. Assuming $G$ is in adjacency list form, say $r \in G$ is the root for a truncated ...
4
votes
4answers
257 views

Algorithms for 2-colouring a 2 x N matrix

Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions. An example of all possible ...
0
votes
2answers
80 views

Is this a new sorting algorithm?

I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements. Is this new? And if so, what should I do with it? https:/...
2
votes
1answer
22 views

Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at ...
1
vote
1answer
27 views

Comparison-based lower-bound for finding duplicates in an array of $n$ numbers

Decision Problem: Given $n$ real numbers, give an algorithm that outputs "1" iff there are at least two numbers that are identical and outputs "0" otherwise. (Assume that comparison between any two ...
3
votes
0answers
132 views

Count horizontal segments that intersect with a vertical segment

I have a set of $n$ horizontal line segments. I want to preprocess them and store them in a data structure, so that given a vertical segment $Q$ I can efficiently count the number of line segments ...
1
vote
0answers
28 views

How to reduce independent set to longest path

A friend and I have tried for several hours to try and find a reduction from independent set to longest path, but the results have not been fruitful. We have tried many methods of graphing and ...
2
votes
0answers
38 views

Algorithm to optimize redistribution of balls amongst urns [closed]

Here is the question: Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ...
0
votes
0answers
37 views

Interval scheduling with shared resources between steps

I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
0
votes
1answer
35 views

How to create disjoint sets out of an adjacency list

I'm not a computer scientist, so please bear with me if I'm misusing some terminology. What I'm trying to do is to find the different components of an undirected graph. I have an array of pairs that ...
3
votes
1answer
32 views

Given 5 curves, find the maximum total you can get for each possible level

Problem Constraints I have a collection of curves, $C$. It is a two dimensional array. The inner array contains rational numbers, where the next is greater or equal to the previous. $$C_{k.i} = v\\ ...
2
votes
0answers
24 views

Transform Double Metaphone code into regex

I am using hyperscan to search through large texts for a lot of regexes. One addition should be selective phonetic search for individual words. The algorithm of choice is Double Metaphone (but please ...
0
votes
0answers
12 views

are there any other strategies used in connect 4 and are they better or worse than minmax with alpha beta? [duplicate]

Just curious about ai strategies that people use for connect 4 besides minimax with alphabeta pruning because I see a lot of people using minimax + evaluation in the internet. Are there other ...
1
vote
1answer
22 views

Hungarian Algorithm - Bipartite Graph Approach

I have been having some difficulty making sense of the Hungarian Algorithm outlined here. It seems incomplete and/or erroneous to me. The main issue is the line: If R_T ^ Z is nonempty, then ...
1
vote
1answer
26 views

Priority queue with a buffer for delayed insertion and other tweaks

I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.). One possible optimisation is to delay insertions ...
1
vote
1answer
33 views

What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the ...
1
vote
1answer
26 views

What is the relation between an algorithm and its implementation at the level of code?

Is there any isomorphism or equivalence relation? What strictly bind these two together?
0
votes
0answers
60 views

Given n strings, how to output their order after k phases of the radix sort (huge constraints)?

Disclaimer This is not from an ongoing contest, this is from my course of ITMO on edx.org, which is a paid code so I cannot give you a direct link to the course. Problem You are given $\...
2
votes
1answer
57 views

Is there a path of length $k$ between given vertex to a subset of vertices in a connected directed graph

I am trying to find an efficient algorithm that on input $ (G,s,A,k) $ returns true iff $G$ is a connected directed graph, $s$ is a vertex in $G$, $A$ is a set of vertices in $G$ and there is a path ...
0
votes
1answer
31 views

Doubt on Graph on DFS

The maximum number of edges possible in an undirected graph with 5 nodes, when DFS call made on any random node in the graph result stack size 5 i.e. 5 function call present in stack simultaneously ...
0
votes
0answers
36 views

How can I prove the linear time search algorithm takes O(n) time? [duplicate]

The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
-2
votes
1answer
84 views

What will be a faster algorithm that finds the maximum number of party people?

You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be ...
3
votes
2answers
58 views

League and Divisions problem (np-hard)

There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team ...
1
vote
0answers
32 views

Cover a polygon with least amount of parallelograms

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
3
votes
0answers
46 views

Interesting applications of union-find

I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know: Kruskal's algorithm for MST Tarjan's off-line ...