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

8,510 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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[...
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 ...
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-...
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 ...
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 ...
65 views

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