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
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 ...
0
votes
0answers
15 views

Parallel Merge Sort - No memory allocation

I am implementing a parallel merge sort in C++ that is based off P-Merge-Sort algorithm from Introduction to Algorithms, CLRS on page 803. Here's the algorithm: And the associated algorithms: And my ...
1
vote
1answer
27 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
25 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
23 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 ...
5
votes
1answer
549 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
2answers
187 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
41 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
17 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
17 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
37 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
46 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
34 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
40 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
45 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
21 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
22 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
31 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
136 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 ...
3
votes
1answer
50 views

How to answer multiple queries efficiently?

I am given a $N$-length integer array. For each integer, I am given 4 values: $$[\mathit{left},\mathit{right},t,\mathit{value}]$$ $$1\leq \mathit{left},\mathit{right},t\leq N$$ For each query, I ...
2
votes
0answers
24 views

Transit scheduling using flow networks

I am studying the maximum/minimum flow question, and was given the following problem: A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
3
votes
1answer
83 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 ...
0
votes
1answer
16 views

Time complexity of linear iteration bounded by logarithmic iteration?

I was wondering about the time complexity of something like the following loop (where work() is O(1)): ...
1
vote
1answer
23 views

Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the ...
0
votes
2answers
44 views

Range Query with conditions

Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the ...
3
votes
1answer
47 views

is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.
1
vote
1answer
16 views

Algorithm for coherent motion. Which bus is app user on?

I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on. To achieve this I am working on building a function ...
0
votes
0answers
23 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
-3
votes
1answer
41 views

I want to solve this question for algorithm, please [closed]

Write an algorithm that calculates the monthly payment of a bank loan with a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of years to pay the loan, you can ...
5
votes
0answers
77 views

Given $n=pq=a^2+b^2$, can we factor $n$?

Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$? It is a known ...
0
votes
2answers
34 views

An underestimated tradeoff between Memory and the Effectivity of Computation?

Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form ...
0
votes
1answer
42 views

Guess the number from its different base representations

Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or ...
2
votes
0answers
93 views

How to query the tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each ...
2
votes
1answer
35 views

reverse string to pattern matching

I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.: Patterns: ...
1
vote
1answer
35 views

How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book: I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
2
votes
1answer
44 views

Algorithm for dividing items into buckets while minimizing total weight

Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of ...
0
votes
1answer
42 views

Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

Here's the start and the vernacular I'm using. ...
0
votes
1answer
90 views

How to Optimise the following algorithm? maximum good value of an element in an array

I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an ...
0
votes
0answers
21 views

Java Dictionary Implementation [closed]

I am making a dictionary in java using separate chaining. It uses a configuration of X's and O's and empty spaces on the board ex. "XXOOOX X" for a tic tac toe game that asses the board through a ...
0
votes
2answers
82 views

number of permutation with k inversions

We are given two numbers N and K. N <= 10^9. K<=min{1000,(N*(N-1))/2} We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K. If N was <= 10^3. It would ...
0
votes
0answers
14 views

CRC(theoretical)-did not understand the highlighted part given below [closed]

Original:-http://www.cs.jhu.edu/~scheideler/courses/600.344_S02/CRC.html ........ Well, at the very least, it would be nice to make sure that the CRC did as well as adding a single parity bit. That ...
4
votes
2answers
121 views

Could anyone prove why O(n^(log n)) < O((log n)^n)?

Could someone provide a rigorous proof of why $O(n^{log n}) \leq O((\log n)^n)$ is true? I'm trying to do this by induction but it isn't working. Thanks.
0
votes
0answers
38 views

Making change optimally

Consider that a currency system has $k$ denominations $d_0, d_1, ... d_{k-1}$. $d_0, d_1, ... d_{k-1}$ are such that $d_0 < d_1 < ... < d_{k-1}$ and $d_i$ divides $d_j$ for all $0<=i<j&...
2
votes
3answers
162 views

Maximum number of multiples of an array element preceding it

Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$. For example, given the array 36 40 ...
1
vote
0answers
14 views

Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
1
vote
1answer
37 views

Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
0
votes
0answers
10 views

Is there any series of videos in which all the main algorithms are discussed without going into things like time complexity and steps [closed]

The course should be discussed in c language. I am presently learning basic computer programming through a book and while doing the questions from the book from a chapter say array, I found out most ...
0
votes
0answers
15 views

How to compute the predecessor-subgraph in all-pairs-shortest-paths algorithm?

The following slow algorithm (implemented from CLRS book) which runs in $\Theta(V^4)$ works fine for computing shortest paths distances: ...