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

1 2 3 4 5 163