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
1answer
37 views

Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
3
votes
1answer
220 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
1
vote
1answer
13 views

an algorithm for detecting if noisy univariate data is constant or is sum of step functions

In an explicit algorithm I'm writing, there is a certain stage where I need to determine whether or not a certain noisy univariate data is constant or is sum of step functions. For example, defining ...
4
votes
1answer
105 views

Task scheduling algorithm that limits concurrency

My prof introduced us an algorithm with semaphores that was used to solve the "dining philosophers" problem. The algo is ok, apart from that it limits concurrency. What does mean that it "limits ...
4
votes
1answer
81 views

Algorithm to create dense style crossword puzzles

I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
0
votes
0answers
8 views

Finding the point with smallest x-ordinate between two given y-ordinates [duplicate]

Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the ...
0
votes
1answer
36 views

algorithm with $f(n) = log^2(n)$

I have to write an algorithm that exactly reflects this recurrence: $$ T(n)=\begin{cases} Θ(1)\;\;\;\;n \leq 1\\ 2T(n/2)+log^2(n)\;\;\;\;n >1 \end{cases} $$ I have tried this way: ...
2
votes
1answer
41 views

Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are ...
0
votes
0answers
12 views

Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L⋅(1+1/α))

This question is from CLRS. The following is what I understand: The procedure is as follows: 1. First we randomly choose one index in T[m] 2. Let nk denote the number of elements in the chosen slot T[...
46
votes
5answers
43k views

Floyd's Cycle detection algorithm | Determining the starting point of cycle

I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare) I can see how the ...
0
votes
1answer
40 views

Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$?

In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ and if it's negative, then $p_1$ is counter-...
2
votes
1answer
39 views

A variant of hitting set problem? Is this also a NP-hard problem?

Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$, it is ...
0
votes
0answers
30 views

The average weight of a cycle in graph

I have a weighed undirected graph. How is possible find the minimum average cycle weight. The average weight of a cycle is the weight of this cycle divided by the number of edges in it. And I must ...
2
votes
1answer
65 views

Minimum bottleneck path between two vertices in an undirected graph

I have an undirected graph, where the value of the path is the maximum weight among all weights edges included in it. And I want find the path of minimum value between two given vertices in time $O(n ...
3
votes
0answers
33 views

Determinant calculation - Bareiss vs. Gauss Algorithm

I've been working on a matrix-library in C++ for a while and amongst other functions, I've implemented two functions for calculating the determinant of a matrix: Gauss-Algorithm: This algorithm is ...
0
votes
1answer
27 views

How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm. I am ...
0
votes
0answers
14 views

Is the usage for asymptotic notation for these algorithms correct? [duplicate]

So after reading a lot of information around asymptotic analysis of algorithms and the use of Big O / Big Ω and Θ, I'm trying to grasp how to utilise this in the best way when representing algorithms ...
2
votes
1answer
2k views

Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
0
votes
1answer
90 views

Algorithm for real time Coordinate smoothing

So I get new Coordinates every 10ms even with RTK fixed precision, they jump between 1-3cm. The Coordinates are the current Position of my Vehicle I have a Vehicle using these Coordinates to follow a ...
1
vote
0answers
27 views

Recursive Algorithm to compute Square numbers

I figured out an algorithm to compute the square of a number (power of 2) in a recursive way backwards or forward. I don't think I have ever seen this anywhere else before, so I am curious if this ...
0
votes
0answers
26 views

creating a binomial heap with only pointer object references

I have a problem where I must make a binomial heap in Python. I have almost all of the methods working except for the bubbleUp method. The problem I am having is ...
1
vote
2answers
16 views

Number partitioning targeting ratio of subset sums and equal size

I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get ...
1
vote
0answers
15 views

Rabin Karp algorithm that uses bitwise AND

I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here. Here's the gist of it: ...
0
votes
2answers
32 views

How many Knight's can be placed on a chessboard n*m

I have a task, its essence is as follows: how many horses on the board $n * m$ can be set so that they do not beat each other. I am wondering if there is any mathematical solution to this problem, ...
2
votes
1answer
54 views

Algorithm: turining a fraction into a decimal expansion string

I already asked this question over on Mathematics and got the suggestion to ask it here. So I'm basically implementing a number type that can represent all fractions and was working on an algorithm ...
0
votes
1answer
22 views

Find the k-th member of the recursive sequence

I have a recursive sequence: $a_n = 5a_{n - 1} + 2a_{n-2} + 3$, for $n > 1$. And I could return $k-th$ member in $O(\log{k})$ of sequence i.e. $a_k$. I know how to get the formula of the $k-th$ ...
4
votes
1answer
365 views

Vehicle Routing Problem with multiple deliveries?

I have a problem that can be reduced to the following: There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points"...
0
votes
1answer
59 views

Finding invariant when detecting a cycle

Let consider a connected graph $G = (V, E)$ which is not oriented. One way to detect a cycle in such a graph is : Create an array : seen of size $\mid V \mid$ with seen[i] = false for all $i$ ...
1
vote
0answers
31 views

Longest processing time rule on unrelated machines

I am trying to solve the job secheduling problem using the Longest processing time rule, that is: We seek to minimize the makespan by first sorting the jobs in decreasing order of processing time, ...
1
vote
1answer
128 views

Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0

Suppose you have a system that consists of $m$ slow machines and $k$ fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you are given a set of n ...
1
vote
1answer
30 views

Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week. For N ...
3
votes
2answers
40 views

When should we construct trees, graphs to analyse an algorithm?

In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to ...
0
votes
1answer
143 views

Matching 2 sets of items by price

I'm trying to solve the following problem in the most efficient way I can find. I want to trade my items for someone elses items, every item have a price and a value. I want to maximize the value of ...
-1
votes
1answer
105 views

How to find the shortest even length cycle in a bipartite graph?

If you have n vertices and m edges, how would you find the shortest cycle of a bipartite graph in O(n^2) time? To do it in O(nm) time, it is simply a BFS on every single vertex. I do not understand ...
1
vote
0answers
12 views

Misunderstanding of an NP-hard problem, $1||\Sigma w_jU_j$, that has polytime algorithm

The problem $1||\Sigma w_jU_j$ of minimizing the weighted number of tardy jobs in a single machine is NP-hard. This is well known and can be shown by reducing the knapsack problem to it. Also, when ...
0
votes
0answers
20 views

Pattern Matching Algorithm in Java

I have to write an algorithm that solves below problem statement - There is a project requirement which has list of titles:- "JobTitles" : [ "Developer", "Programmer", "Java ...
0
votes
1answer
30 views

Why is a Knapsack problem not an LP problem?

We know that LP can solve optimization problems that have linear constraints and linear objective functions. A knapsack problem can be formulated into a linear objective function (because it is just ...
0
votes
1answer
16 views

An algorithm for identifying a fruit with words

Let's say a person picked up a fruit and wanted to identify it. The person knows certain features about the fruit, such as its color and where it was plucked from, but not its name. They also have ...
0
votes
0answers
16 views

Algorithm for this generalized assignment problem

I'm trying to find an algorithm for the following problem. There are $5$ computer files with capacity $18$, $23$, $12$, $125$, $45$ MB respectively and there are $4$ hard disks with capacity $25$, $...
0
votes
0answers
19 views

Need help optimizing an algorithm that's supposed to maximize the greatest common divisor of n elements by removing at most one element

Alright, first here's the text of the problem: You're given n bags of candies where the i-th bag contains a[i] candies and all numbers a[i] are in the segment [1,m]. You can choose a natural ...
0
votes
1answer
208 views

Finding longest prefix of a given string in set of strings that satisies some property

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...
1
vote
1answer
14 views

Big O notation space/time

I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read ...
1
vote
1answer
229 views

Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
4
votes
1answer
170 views

Optimizing method for counting length of elements between blocks

I'm currently trying to do a count of the number of elements between obstacles, for example: 000100001000 Would yield 3,4,3 and 01001110 would yield 1,2,1. More precisely i'm trying to find the sum ...
2
votes
1answer
94 views

N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its ...
0
votes
0answers
25 views

How do I compare these ranges of numbers efficiently?

I'm looking for an efficient way of testing eights. What happens is I need to check if a value is eights and discard it. The numbers I need to check for are: ...
2
votes
2answers
85 views

Given a connected graph with edges >= vertices, find an algorithm in O(n + m) that orients the edges such that every vertex has indegree of at least 1

I'm not exactly sure how to approach this problem. I was thinking we would need to detect a vertex in a cycle, then run DFS on it while also orienting the edges along each vertex u in the cycle, to be ...
0
votes
0answers
45 views

Is there some place I can find an implementation of the Cartesian Product Algorithm for Type Inference?

Where can I find an implementation of the cartesian product algorithm for type inference? (Preferably in Python/C++, but any language would really do) I've searched the internet many times but there ...
1
vote
1answer
49 views

Proof for an algorithm to minimize $\max(a, b, c) - \min(a, b, c), a \in A, b \in B, c\in C$, A, B, C are arrays in ascending order

Problem Statement I came across this problem here. For given arrays $A$, $B$ and $C$ arranged in ascending order, we need to minimize the objective function $f(a, b, c) = \max(a, b, c) - \min(a, b, c)...
2
votes
1answer
87 views

Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...

1
3 4
5
6 7
171