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.

1,709 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
1answer
1k views

Data structures and algorithms for bridge game play?

In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There ...
0
votes
1answer
407 views

Algorithm to minimize an expression

If I have a constraint like $y_1 + y_2 +\dots + y_n = k$ for positive integers $y_i$, how would I minimize $$\quad\frac{x_1 }{ y_1} + \frac{x_2 }{ y_2} + \frac{x_3 }{ y_3} + \dots + \frac{x_n }{ y_n}$...
0
votes
1answer
315 views

Looking for an algorithm to solve a specific Vehicle Routing Problem

I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while minimizing distance traveled. There is only ever 1 company warehouse in the area. The ...
-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 ...
-1
votes
0answers
48 views

intervals in geometrical points in 2D space

Can anyone help me and provide me a link for learning geometrical points in 2d space which is related to algorithmic course ? this is the question but as I searched youtube there should be an equation ...
-1
votes
0answers
37 views

Finding the right algorithm

I am reading the book by Petkovsek et all "A = B". I am wondering which of the algorithms would better work in order to compute (or at least estimate) the following sum: $$ \sum_{m=0}^q\binom{q-m+\...
-1
votes
1answer
26 views
-1
votes
1answer
54 views

What is the Time complexity of this sorting algo?

So i was trying to write an efficient sorting algorithm and i came up with this method, Sorting an array in ascending order by flipping (exchanging) 2 adjacent integers not in the correct order ...
-1
votes
1answer
25 views

Recurrence Relation of Ternary search and the number of comparisons with binary search

i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
-1
votes
1answer
46 views

Find an algorithm to write a given word with this broken keyboard

I am submitting this interview question I have recently found Imagine you have a computer keyboard that has all the letters mismatched example: - typing q gives you a - typing w gives you b ...
-1
votes
1answer
100 views

Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?

We are given a tree of N nodes from 1 to N where node 1 is the root of the tree. For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
-1
votes
1answer
51 views

Genetic algorithm problem

This is a problem I found in an old exam in my school. I have to solve this Genetic Algorithm problem: N students $x_{1},..,x_{N}$ have answered a quiz of 10 questions (True or False questions) and ...
-1
votes
2answers
37 views

calculation of Transitive Closure

This question is not from homework, but rather as preparation for the test: The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond ...
-1
votes
1answer
577 views

Maxflow problem

I need help with the following practice problem on network flow: A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the ...
-1
votes
1answer
91 views

A question about a variant of a knapsack problem

I have the following problem: Let $q_1,\cdots,q_k$ be natural numbers $> 0$, $q := \sum_{1\le i \le k}{q_i}$ and $s_1,\cdots,s_k$ be positive $>0$ real numbers, and $S$ be a positive real number....
-1
votes
1answer
35 views

A general question in type of computer science

Where can I find a source for questions/problems with data structures (like questions about avl trees , rank-trees, 2-3 trees, heap) and algorithms? I will be happy for a references in these topics ...
-1
votes
1answer
66 views

What will be the computational complexity of a system with two pipelined algorithms?

A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ...
-1
votes
1answer
228 views

Find number of swap required to club all greater than $k$?

Given an array of $N$ numbers and a number $K$, Find the minimum number of swaps required to bring all the numbers greater than or equal to $K$ together. Swap here means, swapping value of $...
-1
votes
1answer
404 views

Number of paths of length N inside a graph

Number of different paths (length N) between vertices x and y inside of a clique Kn or a bipartite graph Kn,n? I am looking for simple paths. Therefore, in case I have n vertices N can be maximum n-1....
-1
votes
1answer
46 views

Possible orderings with constraints

Given variables {A, B, ,,,,,Z} We want to sort these varibles according to given constraints. The constrains are in below format: X Y Z meaning the third variable (Z) is not in the range ...
-1
votes
1answer
413 views

Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
-1
votes
1answer
98 views

How to find a pair of array elements whose difference is smaller than the average difference?

How to find a pair of indices $1\le i \le n$,$1\le j \le n$, $i\neq j$ in array $A[1..n]$ such that $0\le A[i]-A[j]\le\frac{max(A)-min(A)}{n-1}$ in $\Theta(n)$ time? ...
-1
votes
1answer
804 views

How to convert a graph into a Boolean formula that represents all paths from a source node to a sink node?

I have a DAG. I want to construct a boolean formula $\varphi$ that represents all paths from a source node to a sink node. In particular, I have a variable for each vertex. A path $v_1 \to v_2 \to \...
-1
votes
1answer
2k views

Divide and Conquer Algorithm for Hidden Line Removal

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$. We will make the assumption that no three of the lines ...
-1
votes
2answers
671 views

How to find the median of 5 elements by rote and its time complexity is O(n)

In the first step, I agree that divide n elements into groups take one pass so the time complexity is $$O(n)$$. But if we need to find the median of each 5 elements, we may have to sort them. I ...
-1
votes
1answer
239 views

Definition of valid partner in Stable Matching Problem

From Tardos and Kleinberg's Algorithm Design, the definition for "worse valid partner" is basically — $m$ is $w$'s worse valid partner if $m$ is a valid partner of $w$, and no man whom $w$ ranks ...
-1
votes
1answer
106 views

I would like to know if there is a closed form expression from taking the reciprocal of a polynomial

I would like to know if there is a closed form expression from taking the reciprocal of a polynomial so that I can apply polynomial division to deconvolution using parallel fork-join multithreading. ...
-1
votes
1answer
74 views

Algorithm : Select maximum number of Boxes to lift from N boxes

There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to ...
-1
votes
1answer
124 views

Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
-1
votes
1answer
542 views

Convert between IEEE 754-2008 decimal64 and IEEE double precision floating point number

I need to know the algorithm for converting between IEEE 754-2008 decimal64 and IEEE 754-1985 double precision floating point number. I have been working on this for the past 2 days and I match the ...
-1
votes
1answer
106 views

Maximum frequency in any row and column

I have been given 2D matrix with some elements. I want to find out what is maximum frequency in any row and column. Example: 1 2 1 2 3 4 1 2 1 1 1 1 2 2 2 2 Maximum frequency is 6 which occurs in last ...
-1
votes
1answer
214 views

Longest path with at most $k$ edges in a tree

How to find the longest (in terms of sum of weights) simple path with at most $k$ edges in a tree? Weights of edges are integers, so they can be negative. I thought about using Bellman-Ford, but it ...
-1
votes
1answer
24 views

What algorithm to apply when a graph have cycles (“circuits”) and some negatives values in order to find the shortest path from $x1$ to all vertices?

What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph? I know I can'...
-1
votes
2answers
3k views

developing a Turing Machine that checks for powers of 2

I want to write a Turing machine which checks for unary powers of 2 but without the use 0s, only accepting as input a series of 1s and dashes. I do not know of a sequence of states which would allow ...
-1
votes
1answer
280 views

Check if a string can be split into two subsequences

Given a string S of length N, a string A of length M, a string B of length O such that N >= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y. Example: ...
-1
votes
1answer
1k views

How to balance parentheses/brackets in a string with minimum cost?

Given a word composed of opening and closing parentheses and brackets, we can do two operations: Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, [ for ] and ] for [. This ...
-1
votes
1answer
74 views

Horn clause for the following formula

Let be $$F=A\land (\neg A\lor B)\land(A\lor \neg C)\land(\neg A\lor\neg B\lor D)\land(\neg A\lor\neg B\lor\neg C)$$ a formula. Is $F$ satisfiable? Well, firstly, I've put $F$ into another form: $$...
-1
votes
1answer
291 views

Fit stack of stone of varying length into a well of varying length

I have a stack of m stones of different Diameter. stack = [5,4,9,20,1] And a Well that is of depth n with varying diameter at different depths . ...
-1
votes
1answer
119 views

Collecting and combining data from iterative DFS on read-only trees

I am iterating over a tree through an API. This API provides a list of nodes sorted in post order DFS. I need to gather data for each node in the tree, combine that data with the parent's data (...
-1
votes
1answer
52 views

Determine whether there is a valid rounding in a table of numbers

I was told this question would be better suited here: Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 &|&...
-1
votes
1answer
323 views

Recursion problem to see if string fits in given pattern

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk ...
-1
votes
1answer
2k views

Runtime of nested loops

What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case. ...
-1
votes
1answer
574 views

Obtaining an Algorithm for a heavier coin

You have n coins — they all look identical, and all have the same weight except one, which is heavier than all the rest. You also have a balance scale, on which you can place one set of coins on one ...
-1
votes
1answer
185 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
-1
votes
1answer
271 views

Custom binary counter supports only increment in $2^i$ values amortized analysis

I'm a having trouble analyzing this algorithm. This is a binary counter that supports only increments in $2^i$ values it's implemented in this way: starting from the $i$-th location change all the ...
-1
votes
1answer
50 views

Fixed Parameter Algorithms

Suppose a parameter $\hat{k}$ is larger than another parameter $k$, assume that $k$ is bounded by a function $f$ of $\hat{k}$. How can we prove that if a problem is FPT with respect to $k$ implies ...
-1
votes
1answer
2k views

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ? for example : for n=10 1 2 3 4 10 20 30 40 100 200 the sub-sequence of length ...
-1
votes
1answer
88 views

Tour de France problem : Dynamic programming

Here is the question: You are doing the Tour de France and you are given a map with all the n places where you can refill your water bottles. Your bottles fit 2 liters of water with which are enough ...
-2
votes
1answer
301 views

How to use Bitmasking to solve this problem?

http://codeforces.com/problemset/problem/535/B The problem is: You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 ...
-2
votes
1answer
353 views

Boruvka/Sollin's algorithm for MST

Please help me regarding following problem- Let us consider Boruvka/Sollin's algorithm . Note that Boruvka/Sollin algorithm selects several edges for inclusion in T at each stage. It terminates when ...