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

26 views

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

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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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'...
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 ...
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: ...
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 ...
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: ...
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 . ...
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 (...
52 views

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