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
1answer
12 views

Triple nested loop complexity

I'm trying to determine the complexity of the following structure: for (i = 1; i < n; i++) for (j = 1; j < o; j++) for (k = 1; k < p; k++) ...
0
votes
0answers
29 views

When a weaker computer wins

Consider the following algorithm: run algorithm A until a solution or out of memory run algorithm B Then if A does not solve the problem, a computer with less memory has an advantage. This could be ...
-1
votes
1answer
25 views

Finding the count of 0's bounded by all 1's

Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview). Sub-matrix ...
0
votes
0answers
11 views

How do i tell if a network is not sorting network? [duplicate]

For most sorting network diagrams how do you work out that it is not a sorting network? What is the method to work it out ?
3
votes
1answer
87 views

Linear algorithm to measure how sorted an array is

I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I'...
0
votes
0answers
10 views

Is there a way to test Simulated Bifurcation Machines by Toshiba?

There seems to be hype about Simulated Bifurcation Machines , an algorithm developed by Toshiba claiming to solve combinational problems in short amount of time. Is there a way to test it somewhere?
0
votes
1answer
24 views

Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer. I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
0
votes
0answers
19 views

How do I calculate the work for a parallel algorithm?

I have problem (for HW) which asks to find a sequential and parallel algorithm to check if a given set of cubes is stacked on top of each other or not. The conditions provided are that the stacks must ...
0
votes
0answers
16 views

algorithm that finds minimal vertex cover of a given vertex

i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to. not sure on how to do it correctly, ...
11
votes
2answers
2k views

Is there a name for the class of algorithms that are the most efficient for a particular task?

This would be analogous to the Kolmogorov Complexity of a string, except in this case, I'm interested in the algorithm that solves a given problem using the least number of steps. We would therefore ...
-1
votes
0answers
18 views

Finding an algorithm that after removing k edges we get an acyclic graph [duplicate]

Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k,...
2
votes
1answer
43 views

Algorithm to enumerate all complete schedulings of finals tests?

I'm creating an app that receives some map between finals and the respective periods during which they are held and a student's required finals. I was wondering if there was an algorithm to enumerate ...
0
votes
0answers
9 views

Optimal order placement of a good across different places when cost and quantity is unknown

I am looking for some help in devising/researching an algorithm. I have come up with some solutions on my own, but would like some guidance as to whether there exists a more formal/robust/mathematical ...
0
votes
1answer
19 views

Converting a function with single parameter to a function with multiple parameters

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows: Given a string or a list, do an aggregation operation on each of its elements. Here ...
0
votes
1answer
425 views

Given a set of points in the plane all laying on the axis, find the number of right angled triangles

My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa)...
1
vote
0answers
20 views

How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?

Question 1: Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j), I want to find subsets of $S_1$ ... $S_n$ (call them $T_1$ ... $T_n$ respectively) So that ...
2
votes
1answer
37 views

Combining merge sort with insertion sort - Time complexity

I am learning algorithms from the CLRS book on my own, without any help. It has an exercise which combines merge sort {O(n log n)} with insertion sort {O($ n^{2} $)}. It says that when the sub-arrays ...
0
votes
1answer
32 views

How can i solve a recursion equation with square root using recursion tree method?

$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$ I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn. I just don't want to ...
0
votes
1answer
35 views

Solving a peculiar recurence relation

Given recurrence: $T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$ The way I solved is like this (using change of variables method, as mentioned in CLRS): Let $n = 2^k$ $T(...
2
votes
1answer
34 views

Static Perfect Hashing - FKS

I am trying to understand perfect hashing aka FKS, but I have a few questions. From my understanding, perfect hashing is a two level hashing in which you take a hash function from a universal family ...
0
votes
0answers
16 views

Broken Parallel Prefix Sum Algorithm

The following is pseudocode for a cost-optimal prefix sum parallel algorithm, where n = problem size (16), p = number of processors (4), and log is base 2: ...
2
votes
2answers
82 views

Being stuck and frustrated with my masters project

I'm doing a masters in CS that requires me to implement from scratch most of the neural network models and because python libraries aren't applicable to what i want. The problem is that i don't feel ...
0
votes
0answers
14 views

How to get started to build a program that plays diablo-2-like games? [closed]

In brief, for those who don't know Diablo 2, it is an action role-playing hack-and-slash computer video game. The functions of the program should include, to detect paths, move the character around, ...
1
vote
1answer
25 views

What is the most effective way to learn, understand, and utilize an algorithm?

In order to keep my interviewing skills sharp, I solve one algorithm/data-structure problem every day, from sites like Leetcode or HackerRank. If I am not able to solve it after 45 minutes or so, I ...
0
votes
1answer
47 views

A linear time algorithm to find the array of indices of bigger numbers

Suppose you have an array nums of integers, unsorted, containing the values from 1 to n. You have a second array, call it ...
2
votes
2answers
314 views

Count number of pairs of elements whose product is a perfect square

Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ...
0
votes
1answer
23 views

Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

Given a set of positive integers : $ \\ D = \{ D_1, D_2, ..., D_n\}$ and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
3
votes
0answers
29 views

points to cover with circles and points to avoid

Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in ...
-1
votes
1answer
77 views

Help with designing the following algorithm to prepare chocolate

Mr X is a spy. He has recently found some very important information. Now he has to secretly send it to his boss. He plans to hide the information in a chocolate bar which can be later exported ...
0
votes
0answers
13 views

Proving existence of feedback edge set variant based on deciding if digraph acyclic [duplicate]

NOTE: this is a variation of Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC. here the definition of ACYCLIC is different to make it easier for me to understand a ...
1
vote
1answer
21 views

How many snakes there can be in the “snakes and ladders” game?

How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board? UPD: My thoughts are simple, ...
1
vote
1answer
42 views

Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could ...
0
votes
0answers
25 views

Sliding Puzzle w/ multiple solutions

I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles ...
1
vote
0answers
24 views

Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
1
vote
1answer
22 views

Is the sieve an improvement for prime finding over an optimized algorithm?

I don't think it is, as you have to loop through each set multiple times at least. implementation of sieve in JS - in the answer at the bottom. The link shows a 10X improvement using sieve. In this ...
3
votes
1answer
39 views

Matching two sets when you cannot do within-set comparisons

Suppose you have two lists, A and B, each with length n. The elements of A cannot be compared with other elements of ...
1
vote
0answers
11 views

Finding C-convex holes in a planar point set

I am looking for an efficient algorithm to find convex holes in a given point set. The problem is Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex ...
0
votes
1answer
38 views

Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
0
votes
0answers
36 views

Help with binary tree that allows duplicate values and returns number of nodes larger/smaller than entered value [closed]

I am trying to develop a Binary search tree that can store duplicate values. Please see the problem below. Problem Statement Sample Input Output Below is my Code: ...
0
votes
1answer
31 views

If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?

Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST? MST means ...
0
votes
1answer
22 views

Does input space size contribute at all to the runtime of an algorithm?

I just started learning about NP-Complete problems and one of the first examples they give is Set Cover: Given a set $U$ of $n$ elements, a collection $S_1, \ldots, S_m$ of subsets of $U$, and a ...
-1
votes
0answers
24 views

Is it possible to keep weights of left and right subtree at each node of BST that has duplicate values?

Is it possible to keep weights of left and right subtree at each node of BST that has duplicate values? I must be able to delete a node completely(irrespective of how many times it is present) ...
2
votes
1answer
116 views

Similar news detection

How do top news portals detect similar news? For example https://www.bbc.com/news/world-asia-china-51431087, if you go to this webpage, you can see the "More on this story" section at the bottom of ...
1
vote
0answers
36 views

Are weakly polynomial time algorithms truly polynomial?

I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if ...
0
votes
0answers
14 views

Is it possible to implement iterative pre/in/post-order traversal with only one stack?

All iterative algorithms I've seen for pre-order, in-order, and post-order traversals of trees have used two stacks. Is it possible to do it with one? I've been thinking about it for ever, I haven't ...
1
vote
1answer
71 views
+50

Selection over combinatorics that satisfies a distribution

I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not. Here is the problem : Consider a list of M ...
1
vote
3answers
60 views

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
3
votes
0answers
77 views

How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
1
vote
2answers
55 views

Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)

Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
1
vote
1answer
52 views

DQQD algorithm for Frobenius numbers

As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga ...

1 2 3 4 5 162