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.
8,108
questions
0
votes
0answers
4 views
finding if a boolean function is a combination of other boolean functions
What I call here "boolean function" is a function returning a boolean.
Here an example of what I would like to achieve: considering a set of boolean functions {f1, f2, f3, ...}, is there some ...
0
votes
0answers
5 views
Runtime of tree sort algorithm confusion
Can anyone explain to me why the average runtime complexity of the program here - https://www.geeksforgeeks.org/tree-sort/ - is nlogn and not n^2logn? Similarly, why is the worst case time complexity ...
0
votes
1answer
47 views
Detect line intersections excluding endpoints
Suppose I knew the endpoints of various different lines within a 2D plane.
For example, A = (1,1) B = (2,1) C = (3,4) D = (1,1)
Now, there are lines AB and CD, with a common point of (1,1).
However,...
0
votes
1answer
9 views
Quadratic Probing Infinite Loop?
I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element?
According to https://en....
0
votes
0answers
7 views
Pseudocode for a searching tree
I want to describe my search tree in an algorithm and describe how each level of the tree is created. But I cannot find good examples to help me express how to write it in an elegant way. Please if ...
1
vote
1answer
287 views
Correctness proof for greedy algorithm based on ratio
I've an issue stated as follows:
We have 10000 jobs to do, each with some length $l_i$ and weight
(importance) $w_i$. Our goal is to arrange the schedule of doing these
jobs (in other words, ...
4
votes
1answer
221 views
Single machine job scheduling to minimize weighted sum of completion time
Given $n$ jobs, schedule them such that the weighted sum is minimum.
weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :
$S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
1
vote
0answers
16 views
Algorithm to minimize the damage received from the monsters [duplicate]
I have been puzzled by the following question on an exam for quite a while: given a set of monsters with their health and attack damage (per second), design an algorithm that minimizes your overall ...
4
votes
1answer
79 views
Interview Question with Arrays and Consecutive Subintervals
I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it..
The question is:
"An array of $n$ integers is ...
0
votes
0answers
35 views
Travelling Salesman Problem Easy Algorithms
I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript).
Unluckily all of the ones i found are really hard to understand/ to implement.
The ones i ...
4
votes
2answers
138 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'...
2
votes
1answer
38 views
Calculate boolean matrix multiplication (BMM) using transitive closure
Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two ...
21
votes
3answers
13k views
What is the fastest algorithm for multiplication of two n-digit numbers?
I want to know which algorithm is fastest for multiplication of two n-digit numbers?
Space complexity can be relaxed here!
1
vote
1answer
23 views
How are “Problem Complexity” and “Solution Complexity” different?
I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the ...
2
votes
1answer
31 views
What's the decoding time complexity of LT codes?
LT codes are practical fountain codes that are near-optimal erasure correcting codes.
Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ ...
4
votes
0answers
53 views
+50
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
...
5
votes
1answer
90 views
Minimum edge weight k-exact cover with triangle inequality
Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in ...
1
vote
1answer
63 views
Find number of triples that sum up to zero in query-intervals
My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array.
For each query, we ...
-1
votes
1answer
29 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
1answer
18 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++)
...
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 ...
0
votes
0answers
37 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 ...
7
votes
3answers
2k views
Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop
The Floyd-Warshall algorithm is defined as follows:
...
0
votes
0answers
15 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
265 views
Find expectation with Chernoff bound
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every ...
3
votes
1answer
736 views
Finding the minimum number of calls in a tree
I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before.
Suppose you ...
2
votes
2answers
83 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
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
32 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 ...
4
votes
5answers
6k views
Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.
$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
0
votes
2answers
472 views
Will a Greedy algorithm give a correct result for minimum partition?
Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?
Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now ...
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 ...
3
votes
1answer
108 views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
0
votes
0answers
20 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 ...
2
votes
2answers
321 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
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, ...
0
votes
1answer
48 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 ...
-1
votes
0answers
19 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,...
0
votes
1answer
432 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)...
0
votes
1answer
64 views
Dynamic programming
Got a question and can't manage to find an answer, so help will be appreciated.
I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and 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
20 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 ...
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
180 views
Calculate makespan of job shop solution?
I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine.
A job shop problem can be written as such :
...
0
votes
1answer
36 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
39 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 ...
5
votes
1answer
607 views
Find equidistant triplets in a tree
Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
1
vote
0answers
22 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 ...
