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
2
votes
1answer
24 views

Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
1
vote
1answer
38 views

What are the reasons for solution assumptions behind the longest subsequence problem?

All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...": ...
-2
votes
1answer
23 views

A problem about $2-SAT$

My algorithm $n$ times checking that $n$ clauses with $2$ variable, are satisfiable or not? (i.e. $n$ times my algorithm check $2-SAT$ Problem with different variable) that each time $2-SAT$ need's $...
1
vote
0answers
85 views

Fixed bin packing for maximizing the number of matches in every bin

Original question: Given a symmetric matrix with matches count between different transcriptions, the objective is to maximize the batches total matches count while minimize the standard deviation ...
2
votes
1answer
54 views

Given a string which was produced by mixing up a string of digits, find the original digits

I encountered the following problem: Given a string which was produced by mixing up a string of digits (0-9), for example: "otetwonhree" was produced by "onetwothree"~123, find ...
0
votes
0answers
51 views

Confused about a corollary in MIT.Introduction.to.Algorithms(CLRS), seek help

Desc' I was reading CLRS Book's chapter 11 Hash Tables, and encountering some problems. There is an corollary in CLRS book, in Page 275 (quoted on the bottom of post), which discussed the expected ...
0
votes
0answers
44 views

Given a set of integers and target, find all subsets of size k such that sum of elements of each subset equals target

I am trying to solve below problem Given a set of integers A, and target integer, find all subsets of size k such that sum of elements of subset equals target. One approach could be enumerating all ...
0
votes
1answer
37 views

Importance of study of mathematics in algorithm design and other computer science fields

I am looking for a discussion state that, why study of mathematics in designing algorithms, and find out efficient solution for algorithmic problems is so important?
2
votes
1answer
49 views

Find maximum length subarray whose bitwise AND is at least $k$ in $o(n^2)$

Given an array $A$ of unsigned integers, a subarray is a contiguous interval $A[\ell],\ldots,A[r]$. The bitwise AND of the subarray is just the bitwise AND of $A[\ell],\ldots,A[r]$ (what is denoted by ...
3
votes
1answer
94 views

Winning move in graph based strategy game

I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if ...
1
vote
1answer
22 views

Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
0
votes
0answers
18 views

Iterative version of depth-first-search code to detect cycle in a directed graph [duplicate]

I have solved a problem that required me to find if the given directed graph had a cycle or not. The deal is, I used a recursive approach to solve it in the depth-first-search method. I was just ...
4
votes
2answers
77 views

Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing ...
2
votes
0answers
52 views

Approximation algorithm for minimal Covering of an orthogonal polyhedron

Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
4
votes
0answers
75 views

Sequence where every subset exists as some contiguous subsequence

Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
1
vote
2answers
43 views

Having a set of non unique Key-Value pairs, how can I optimally find a lowest sum subset if distinct keys?

I understand that the title might be confusing so I'll lead with an example. I have the following set (actually a map): ...
0
votes
1answer
79 views

Algorithm to return all possible ways to divide n unique elements into groups of size k

If I have as set N of n unique elements, is there a known algorithm that can return every possible way in which they can form groups of size k? Eg: If N = { A, B, C, D} and k = 2, then the algorithm ...
0
votes
0answers
162 views

Some Confusions in Ricart Agrawala second algorithm-token based algorithm for mutual exclusion

Resources that I followed to learn-: http://www.ejbtutorial.com/lectures/petru/lect6-7.frm.pdf https://cis.temple.edu/~wu/teaching/Spring2020_CIS5644_Distributed_Computing/distributed-computing-2020-...
0
votes
0answers
7 views

Looking for algorithm to pack rectangular squares while considering locality

I have a couple of rectangles (~10'000 - 1'000'000) with various integer dimensions where each side is something between 1-10 I got to arrange these (without rotating) into a block of fixed width ...
1
vote
0answers
24 views

How does Bowyer-Watson algorithm for Delaunay triangulation run in $O(n^2)$ but runs over all the simplexes?

The Bowyer-Watson algorithm for Delaunay triangulation is known to run in $O(n^2)$ according to the authors, where $n$ is the number of data points in $\mathbb R^d$. In addition, the algorithm (for ...
1
vote
1answer
30 views

What does "index up to $n^c$" mean in this question about CLRS "word size $c \lg n$"?

I don't know where else to ask this. And I don't know when or if I'll get reply at all if I comment on that answer. I was reading this answer on a text of CLRS and in the last line got confused. I ...
0
votes
0answers
28 views

Algorithm to efficiently plan a path to build a pixel structure

I have a problem that I have an unsatisfactory answer to and I would be interested in knowing if there is a better solution I am missing. The problem is as follows: Compute a series of ...
1
vote
0answers
35 views

Sequence of points on a line whose intervals represent a set of contiguous integers

If I have points on a line at positions (0), (1), (3), and (7) the set of intervals between any two points is the set of integers (1,2,3,4,6,7). In-general, a set of N unique integers can be ...
1
vote
0answers
25 views

Minimal description for tree selection

If you have a tree, where nodes can be either selected or not selected, and you wanted to describe which nodes were selected or not you could either List all the selected nodes and infer the others ...
2
votes
1answer
43 views

Find if two elements in an array sum up to a given number

I'm currently solving some problems over at kattis, in particular the Add 'Em Up task. A quick summarizing: You are given an array with $1 \leq n \leq 100000 $ elements and an integer $2 \leq s \leq ...
0
votes
1answer
24 views

Lower bound on number of zero columns in matrix

I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
0
votes
1answer
56 views

speed up straightforward solution using dynamic programming

i recently got onto the following problem: we consider the following array: A = [2, 3, 6, 1, 6, 4, 12, 24] we need to count the number of times these two ...
2
votes
0answers
24 views

Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
1
vote
2answers
43 views

Question about the proof of the undecidability of the Halting Problem

From what I can see, the proof of the undecidability of the Halting Problem relies on a fairly basic self-referential paradox, the simplified version being (from Wikipedia): ...
0
votes
0answers
15 views

Is ordering achieved by central server algorithm?

ME3 specifies that the first process be granted access before the second Ordering-: Requests are granted in the order they were requested. Colouris Distributed Systems book-: The reader should ...
0
votes
1answer
77 views

What is the most efficient algorithm for calculating factorials? [duplicate]

Calculating the factorial n! by the algorithm that defines it is of O(n) complexity because it requires n-1 multiplications to find the solution. Is there an algorithm that is any faster than that?
1
vote
1answer
44 views

How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
2
votes
1answer
29 views

Random splitting with fixed size range

I ran into this problem while trying to create a procedural texture algorithm. I ended up using a greedy approximation and shuffling it to hide the bias, but I was wondering if there was a way to find ...
1
vote
1answer
70 views

What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?

Shor's algorithm uses the Quantum Fourier Transform to find the period the function a^x mod N with "a" being a constant integer less than N and N being a ...
1
vote
0answers
26 views

Selecting sets that maximise the cardinality of the union minus the cardinality of the difference

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
0
votes
0answers
33 views

What's the best data structure to use for this problem?

There are n cartesian points. You need to come up with a data structure such that if you are given a point P=(x,y), you need to remove all the points s.t. if point G=(m,n) and m>x or n>y it is ...
0
votes
0answers
17 views

Selecting five binary vectors that when multiplied elementwise are most similar to another vector

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
0
votes
0answers
24 views

Polynomial time function vs polynomial time algorithm

In the book Proof Complexity By Jan Krajicek, the definition of a functional propositional proof system is given as: Definition 1: A functional propositional proof system is any polynomial time ...
0
votes
1answer
28 views

Recursive Prefix-Sums K times

I have been wondering about the following question for quite some time: You are given an array $x$. Define f(x) as the prefix sums of this array. For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
1
vote
2answers
493 views

Algorithm notation

I am reading Nancy Lynch's Distributed Algorithms. In page 103, there is the FloodSet algorithm. Can anyone please explain what Uj mean in W := W U Uj xj (line 3 of transition function)?
0
votes
0answers
12 views

How does Sign-and-Magnitude representation allow for easier tracing of memory dumps?

Hey I've read in Wikipedia the following: Refer here link. "Sign & magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 ...
0
votes
0answers
3 views

Rank aggregation algorithm across several criteria when only the top pick in each category is known

Example setup: Assume that in a survey, $n$ users pick their top cell phone (e.g. iPhone 11, Galaxy S9 etc.) in each of $m$ categories (e.g. camera quality, cost, speed etc.). The users don't rank all ...
0
votes
0answers
14 views

Algorithm speed-up assuming other cnditions unchanged

An algorithm uses $f(n)$ operations. Another algorithm for that purpose, uses $f(n)-g(n)$ operations. I want to calculate the speed-up percentage: Which is $\frac{second\ speed-first\ speed}{first\ ...
1
vote
0answers
22 views

Finding max values at a point given a list of ranges

In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so ...
0
votes
0answers
29 views

Is there such thing as average space complexity? If so, what is it for Timsort?

I was reading about Timsort's use in Python and wondered what the time and space complexities were which are dispalyed on the wikipedia page. The Wikipedia page lists average time complexity for ...
0
votes
1answer
31 views

Given a rectangle and a circle (having a lattice point as a center) find the number of lattice points of the rectangle inside the circle

The title explains the question easily. Also the radius of the circle is always an integer. The naive algorithm I thought was to check each and every lattice point of the rectangle but I wonder if we ...
0
votes
0answers
7 views

Algorithm to pair respondents based on differences in answers to survey

I am having the following problem: I have asked a number of people 7 different binary questions. I now want to pair my respondents based on how different their answers to the questions were. The goal ...
0
votes
0answers
30 views

A relaxation-free variant of Dijkstra's shortest path algorithm

I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
0
votes
2answers
56 views

How to define a formal language for describing procedural activities

I do not have a formal computer science background here so I am looking for pointers. How would you advice I go about describing a formal way to describe procedures like cooking recipes, manufacturing ...
0
votes
0answers
28 views

Worst case finding the goal node in a tree

Suppose given a tree with 10 nodes, we want to find vertex goal that is unknown for us. We act as follow: we pick a arbitrary vertex x, then if it goal we return it, else if it's not goal we have ...

1
3 4
5
6 7
201