The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
7 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
8 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 ...
0
votes
0answers
13 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\}$...
1
vote
0answers
14 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 ...
0
votes
0answers
15 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
35 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 ...
0
votes
0answers
17 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 ...
2
votes
0answers
28 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 $$...
0
votes
0answers
10 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 ...
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 ...
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
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
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 ...
0
votes
0answers
18 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 ...
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$...
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 ...
0
votes
1answer
29 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
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 ...
1
vote
2answers
69 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
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 (...
0
votes
0answers
41 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, ...
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
33 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
2answers
31 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 ...
6
votes
3answers
168 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
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 .
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
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
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 ...
0
votes
0answers
31 views

Improving on Monte-Carlo

Can I improve on a Monte-Carlo search for the problem, described? So I have a graph/network consisting of segments a1, a2, ..., b1, b2, ..., and c1, c2, ... For all the underlying segments there is ...
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 ...
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 $...
2
votes
3answers
218 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 ...
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
0answers
19 views

Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks

In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
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
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
1answer
38 views

Check subset sum for special array

I was trying to solve the following problem. We are given N and A[0] ...
1
vote
0answers
55 views

Paxos algorithm, accept phase

From the wiki https://en.wikipedia.org/wiki/Paxos_(computer_science) If a Proposer receives enough Promises from a Quorum of Acceptors, it needs to set a value v to its proposal. If any Acceptors ...
0
votes
0answers
22 views

proving long asymptotic bounds

I'm trying to find ways this simplify this formula and assuming numbers but that doesn't seem to help, the question is asking to prove or disprove: $$ 3n(\log_{}n)^2 + 4n = \Omega (2n^2 \log_{}n +1) $...
1
vote
0answers
39 views

Data structure for storing strings

I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) ...
0
votes
0answers
42 views

Algorithm for travelling to top right corner in a room with random walls inside

A robot, let's say, Steve, is in the bottom left corner of a rectangular room, the size of which is unknown. His goal is to travel to the top left corner of the room and stop there. There are random ...
1
vote
1answer
49 views

How to encode reachability in a graph with walls as a SAT problem

Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...
2
votes
0answers
22 views

Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification

I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq ...
2
votes
1answer
23 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
2
votes
1answer
32 views

complexity of a variant of the subset sum problem

We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$. What is the ...
1
vote
2answers
141 views

How can I make my algorithm more efficient or Is there a better way to solve the problem

Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you ...