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
2answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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: ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
4
votes
3answers
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 ...
0
votes
0answers
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? ...
2
votes
1answer
29 views

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

Suppose I have the following set of bit sets: ...
0
votes
3answers
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 ...
2
votes
2answers
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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$ ...
0
votes
2answers
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) (?) ...
3
votes
1answer
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 (...
3
votes
0answers
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 ...
13
votes
2answers
1k views

Quantum Supremacy Task

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 ...
0
votes
3answers
40 views

How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
8
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 \}$. ...
0
votes
0answers
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 ...
2
votes
1answer
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\}$...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
0answers
36 views

Why can't we use the Master Theorem on recurrences with floor or ceiling operations? [duplicate]

From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$...
0
votes
0answers
17 views

Survey of Graph Algorithms with applications to data/ML?

I'm a new Computer Science student in a masters program, switching from Applied Math. I'm really new and lacking some background, but I am interested on what literature is out there on graph ...
5
votes
3answers
1k views

How can I determine if two vertices on a polygon are consecutive?

Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices ...
0
votes
0answers
33 views

Binary to Decimal Algorithm Explanation

I came across some code today for converting binary to decimal, and I realised that I don't fully understand how it works. Here it is in Python: ...
0
votes
0answers
11 views

Maximum cardinality bipartite matching when nodes are ordered and only subsets can be matched?

Maximum bipartite matchine problem can be converted to the maximum flow problem and it can be solved by Edmonds-Karp algorithm in O(VE)<=O(V^3). But there can be bounded problem, when the nodes on ...
3
votes
1answer
71 views

Optimal solution for Weighted points problem

Problem: Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, ...
2
votes
1answer
36 views

Can we apply the Master Theorem to the following recurrence?

Our recurrence is $$ T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\ 1 & \text{if $n=1.$} \end{cases} $$ I have identified $a = 1 > 0$, and $b = 2 > 1$...
1
vote
0answers
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 ...
0
votes
1answer
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. ...
2
votes
2answers
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 (...
0
votes
0answers
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 ...
1
vote
1answer
24 views

Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
3
votes
1answer
29 views

A problem on sets

Given a collection C of sets, with union U, find a choice function which chooses a distinct element from each of the sets such that the union of the singleton distinct elements is U. As an example, ...