Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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