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,658
questions
0
votes
0answers
6 views
Efficiently finding all pairs of disjoint sets
Say we have the letters $\Omega = \{1,2,\dots n\}$, and a two sets $S_1, S_2$ of subsets of $\Omega$.
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
26 views
Optimal solution for Weighted points problem
Problem: Given a set of 2d points N: {N1, N2, N3, ...., Nn}, find a set of points X: {X1, X2, X3, ...., Xk} such that the points in X are D distance apart and Sum( Weight(Xi) ) from i= 1 to k is ...
0
votes
3answers
535 views
Do algorithms always have a return value?
I learned that algorithms written in programming languages always return some value, not necessarily an input value.
But, if the return type of the main function is void, then does the algorithm ...
1
vote
1answer
25 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
vote
1answer
26 views
Multiple choice knapsack dynamic problem
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\}$...
0
votes
0answers
11 views
HITTING SET Problem
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 ...
0
votes
0answers
16 views
Pls help me to find an algorithm and the flowchart
Create a program that applies the ATM system in usa , minimum amount of cash withdraw is 50 $ and maximum is 5000 $. In addition, the amount should be a division of 50.
Hint: if the amount is not ...
-1
votes
0answers
19 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
2answers
34 views
How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?
I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
4
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 ...
2
votes
1answer
39 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 ...
2
votes
1answer
189 views
Prove that this solution to the Closest 3-Sum problem always works
I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why.
Here's the ...
2
votes
0answers
31 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 $$...
2
votes
1answer
10k views
An efficient algorithm to find a shortest cycle including a specific vertex
We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$.
We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle.
This ...
0
votes
0answers
18 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 ...
0
votes
0answers
11 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 ...
1
vote
2answers
70 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
14 views
Multiple parameters in optimization [on hold]
Consider a scenario where I have multiple unique balls of different sizes and weights. The problem is to identify the maximum number of balls which can fit into a bucket B given the following ...
0
votes
0answers
30 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
8 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 ...
6
votes
3answers
172 views
+50
Why does Min-Max algorithm delays a good move indefinitely?
Consider a simple chess example:
Q is white Queen.
K, R is black King and black Rook respectively.
A B
1 . Q
2 . .
3 K .
4 . .
5 . .
6 R .
7 . .
8 . R
1,2......
0
votes
1answer
30 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
1answer
35 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$...
0
votes
1answer
180 views
Merge sort and quicksort recursion tree depth
1)
I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
1
vote
0answers
15 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 ...
2
votes
3answers
219 views
Remove x last elements of an array and reinsert them before position y
I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array ...
2
votes
1answer
20 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
votes
0answers
18 views
how to do this? [on hold]
an array that holds the weights of n people in the class W = (w1, w2, ..., wn). Your goal is to divide the n people into two teams such that the total weight of the two teams is equal or as close as ...
0
votes
0answers
20 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 (...
6
votes
1answer
590 views
How to perform orthogonal check on two circular binary strings?
Say we have two circular binary strings $a = a_0a_1...a_{n-1}$ and $b = b_0b_1...b_{n-1}$ with arbitary starting point, and define a and b are orthogonal if $\sum_{i=0}^{n-1}a_ib_i = 0$.
Is there a $...
0
votes
0answers
42 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
19 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
28 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, ...
1
vote
1answer
55 views
packing with time-variant weights
This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions.
Scenario 1: Tough (for me!)
There is a one day conference with a set of (4 or ...
3
votes
2answers
119 views
Maximizing sum of numbers within a sequence
Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except ...
4
votes
2answers
129 views
How to evaluate all possible groups of adjacent tiles in 2D array?
I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain ...
8
votes
1answer
7k views
What does the 2 in a 2-approximation algorithm mean?
Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
0
votes
4answers
448 views
Questions on shortest path and minimum spanning tree
T/F Questions
Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
Solution - False
I think this should be True, as Dijkstra's Algorithm ...
0
votes
1answer
14 views
Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n
The Question of the CLRS $6.1-7$ exercise reads as:
Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \...
0
votes
1answer
34 views
Idea behind using binary search to solve rolling ball?
What is the idea behind using binary search to solve this problem:
There is a segment of length meters, and there are $L$ positions on it,
numbered $1,2,...L$ , equally spaced by 1 meter apart ...
2
votes
1answer
41 views
Understanding addition overflows when performing full, signed multiplication of two 64-bit numbers
I am close to solving question 3.59 from Computer Systems: A Programmer's Perspective 3rd Editionby Randal E. Bryant and David R. O'Hallaron, however I am having difficulties with understanding the ...
0
votes
2answers
103 views
Visit all vertices of a graph
I need to find the fastest route passing in all vertices
Each vertex is a class.
I can choose the number of classes for semester.
Some classes have prerequisites (A and B need to be done one semester ...
0
votes
1answer
45 views
binomial tree number of nodes
Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .
1
vote
2answers
39 views
Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find ...
3
votes
1answer
74 views
Split a list of elements into sub lists, each with different criteria
I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same ...
1
vote
1answer
28 views
Applying subproblem technique to permutations with grouping
I am trying to apply overlapping subproblems and dynamic programming to permutations.
Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$.
Given some ...
0
votes
0answers
11 views
Compiler Shows: Abort Called [migrated]
When does a C++ compiler give a this message : "terminate called after throwing an instance of 'std::out_of_range'"? I was trying this problem a website. I wrote an algorithm but the code won't ...
1
vote
1answer
53 views
Return the subset with smallest cardinality of an array whose elements sum to at least a given value
Suppose we are given an array $A[1\ldots n]$ and a value $C$.
Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots ...
2
votes
1answer
23 views
Combinations and Permutations of M sets of distinct items?
I'm wokring on this problem for a while. I want to know:
The correct name of this problem, so I can look it up in textbooks\online.
Here is the problem descirption:
The (un-ordered) combinations to ...
1
vote
1answer
31 views
nested boxes algorithm
I am given a set of 3D boxes {$B_1$, $B_2$...$B_n$} and each box have length, width and height. But these values are interchangeable since I can rotate the box. I need to find out the maximum sequence ...
