# 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.

7,775 questions
Filter by
Sorted by
Tagged with
65 views

### Algorithm to find best solution

I am writing a software as small project in TypeScript/JavaScript and got to a problem i cant solve: A Company makes a new contract with a customer and wants to order materials. There are serval ...
28 views

### Is there any general, theoretical limit to time - space tradeoff?

In many algorithms, one can spot that improvements in time often are occupied by more memory requirements. For example usage of cache allows to speed up calculations by saving results in memory. Is ...
25 views

### Dividing unequal parts as equaly as possible

I'm dividing up an animation project among 20 students. The whole film is 4955 frames long, so each student should have as close to 248 frames as possible. However, the scenes have an unequal number ...
31 views

### What is the name of this sorting algorithm and how does it compare to others?

Let's say we have an array of strings that we want to sort lexically or by length or some other criteria: ...
30 views

### Computing order statistics $1,2,4,8,\ldots,n$

On an array of $n = 2^k$ numbers, where $k$ is a non-negative integer, the $k = \log n$ order statistics $1, 2, 4, 8,\ldots, 2^k$ can all be determined in a total of $Θ(n)$ time in the worst case. I ...
12 views

### Does integer matrix multiplication with its transpose (A^T)*A have more efficient parallel algorithm than the use of symmetricity?

Integer matrix multiplication with its transpose (A^T)A gives symmetric matrix, so, only one half of it should be computed. Besides, the formula for the resulting element rik=Sum[aijajk, j] reduces to ...
34 views

### Algorithm for efficiently sorting large lists based on user preference

I’ll preface this question by saying I’m having a difficult time even formulating the problem, so my explanation might be fuzzy and/or I might be missing obvious solutions. I have a list of 479 books ...
38 views

### Polynomial multiplications and counting

I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...
24 views

### How to solve Assigment problem on SPOJ? [closed]

Problem Link - Assign .This problem is known as assignment problem. I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to ...
142 views

### What is the best solving algorithm for a game with stacks?

Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose ...
145 views

### Finding the hidden treasure

Let's assume I am trying to find a hidden treasure. The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is ...
16 views

### How does ordering paradigm differs from subset paradigm in greedy method?

What is the difference between subset paradigm and ordering paradigm of greedy method approaches? More precisely I didn't understood how does the ordering paradigm differs from subset paradigm? ...
29 views

### largest bitwise-or subset with a maximum number of on bits?

Suppose I have the following set of bit sets: ...
55 views

### How can I create 10-character, unique codes with no collisions, but without being predictable?

If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of the picture(?). The use-case is ...
150 views

### Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior

I asked this question on Stack Overflow, but I have not obtained an actual answer to the question. Tarjan's strongly connected components algorithm is stunningly beautiful, and inexpressible in a ...
102 views

### Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph. My solution is to do a modification of breadth first search from the ...
33 views

### What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]

What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ ...
64 views

### Find two numbers in sorted array whose product is close to N

Given a sorted array of numbers, is there a good algorithm for finding two numbers in that array whose product is as close as possible to a given number N? I know that there is a good O(n) (?) ...
20 views

### Solve SUBSET SUM for Reciprocals of Primes

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
17 views

### Arrange the array element with minimum number of swaps

Given an array with some elements in which elements can occurs multiple times, so now how to arrange them in such order that no two same elements are together using minimum number of swaps.( it may ...
1k views

I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years ...
40 views

### How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
103 views

### Generate random labeled tree with constrained edge lengths

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes ...
42 views

### motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
16 views

### Construct neighbourhood relation graph for n sequences

Given $n$ sequences with length $m$, $s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$, where $c^i_j\in D$ is a partial ordered set and the partial order relation $\sqsubseteq$ on $D$ answers ...
25 views

### Understanding the behaviour of different variations of Binary Search

Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of ...
16 views

### Using Marching Squares to connect curve ends in adjoining squares

I'm learning Marching squares for a graphic program I'm working on and, while I understand how to connect points along an edge of a single square depending on the vertex values, I am unclear about how ...
21 views

### Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))

I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds. I ...
47 views

### Efficiently finding all pairs of disjoint sets

Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$. I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. ...
23 views

### HITTING SET Problem [duplicate]

HITTING SET INSTANCE: collection C of subsets of a set S, positive integer K. QUESTION: Does C contain a hitting set for C of size K or less, that is, a subset S' of S with |S'| <= K and such ...
50 views

### Multiple choice knapsack dynamic programming

Giving a the following: A list of a store items $T=\{t_1, t_2,...,t_n\}$. A list of prices of each item $P=\{p_1, p_2,...,p_n\}$. A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
35 views

### Searching for the biggest area inside 2D matrix

so I've a algorytmical problem where i need to find the biggest area of a certain type of pixels inside a 2D matrix with following conditions: Each pixel needs to be connected either diagonally or ...
20 views

### How is 2d peak finding algorithm Big0(nlogn)?

What's unclear from this explanation is Step 5. "Evaluate one of the remaining columns (fifth column evaluation), and you're done." There are two remaining columns left, columns 31 and 32. So, how can ...
46 views

### Spotting the difference between two arrays using divide-and-conquer

Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index. For ...
29 views

### time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
36 views

17 views

### Traceless In-place Selection

I was asked a question in an exam You are given an array A[1..n] of length n with each cell containing a ⟨height,weight⟩ pair. All height values are distinct, and so are all weight values. The array ...
35 views

### What is google docs solution to handling multiple users editing and reading at the same time?

I have always been curious as to how google solved the solution of real time collaboration in their google docs product where they allow multiple users to edit and read the same document in real time. ...
32 views

### Minimum words in a string given a dictionary

The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
76 views

### Efficient algorithm for finding optimal sum from both arrays

I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See ...
21 views

### Highest safe rung problem?

Highest Safe rung problem : There are many rungs on a ladder in increasing order of height. A bottle is thrown from a rung, and depending on the height of the rung, the bottle may break or may not (...
295 views

### Help with an algorithm task

I've been given a task that I had issue solving. Problem statement: John likes jumping so he is about to build a new jumping terrain. The terrain consists of N blocks, and in each block he can ...