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
3
votes
1answer
213 views

Random algorithm termination

Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On ...
3
votes
1answer
231 views

Median of medians: bound on pivot position

If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at ...
2
votes
1answer
439 views

Runtime of the binary-GCD state machine

I am doing self study from MIT OCW exercises and I could not understand this question. The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state $(...
2
votes
2answers
2k views

CNF Generator for Factoring Problems

I've been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don't understand how the reduction from FACT to $3\text{-SAT}$ works. ...
2
votes
1answer
86 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
2
votes
1answer
2k views

How to find longest recurring pattern from lage string data set?

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example ...
2
votes
2answers
3k views

Algorithm for finding maximum mutually coprime subset of a multiset of integers

For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I'm having trouble ...
2
votes
0answers
157 views

What you want to “prove” in algorithms

So it seems that you can get pretty far with just type definitions as a formal model of a system. The typed properties verify that the properties will have that type, typed function arguments verify ...
0
votes
1answer
1k views

Finding all (weighted) cycles through a given vertex

For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$? In my case, I have weights for every ...
19
votes
2answers
1k views

How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the ...
9
votes
1answer
155 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
8
votes
3answers
578 views

How to count in linear time worst-case?

This question and this question got me thinking a little bit. For sorting an array of length $n$ with $k$ unique elements in $O(n + k \log k)$, we need to be able to store counts of values in the ...
7
votes
4answers
3k views

Loop invariant for an algorithm

I have developed the following pseudocode for the sum of pairs problem: Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A[i] + A[j] = b$, NO ...
6
votes
3answers
8k views

Quicksort vs. insertion sort on linked list: performance

I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a ...
6
votes
2answers
6k views

Algorithm to return largest subset of non-intersecting intervals

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals. i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...
5
votes
1answer
3k views

Effect of increasing the capacity of an edge in a flow network with known max flow

I need your help with an exercise on Ford-Fulkerson. Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance. Now suppose you are ...
5
votes
1answer
275 views

Data structure for selection of K elements and taking sum

The problem: We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times: We can select exactly $Z$ ...
5
votes
1answer
452 views

Merge sort worst case running time for lexicographical sorting?

A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge ...
5
votes
3answers
1k views

Finding the $k$th largest element in an evolving query data structure

Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element ...
5
votes
1answer
2k views

Tarjan's Strongly Connected Component algorithm

I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net): On line 33 why is ...
4
votes
1answer
458 views

Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
4
votes
2answers
66 views

Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
4
votes
1answer
780 views

how to understand time complexity from a plot?

This is my first question here. I'm not a CS at all, so it might be quite trivial. I have written a program in C where I allocate memory to store a matrix of dimensions n-by-n and then feed a linear ...
4
votes
3answers
224 views

Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$. Now let $T'$ be some other spanning tree of $G$ (...
4
votes
1answer
350 views

CLRS RAM model Description

I'm seeking some clarification on a description of the RAM model in CLRS on page 23, section 2.2 (Analyzing Algorithms). Firstly, it is mentioned that we assume integers are represented with $c\cdot\...
4
votes
2answers
677 views

Analysis of algorithms, 'big O' question

The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation? Also, what about ...
3
votes
1answer
176 views

Algorithm for estimating function maximizing parameters

I'm trying to find parameters $\omega, \alpha,$ and $\beta$ which maximize $$ \sum_{i=1}^m{\left\{ -\ln(v_i) - \frac{r_i^2}{v_i} \right\}} $$ where $$ v_i = \omega + \alpha r_{i-1}^2 + \beta v_{i-...
3
votes
2answers
93 views

Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape

Lets say I have a random number generator that spits out uniform numbers from 0 to 1 Next, I have a shape defined by a series of vertices, like { [0, 0.4], [0.5, 0.2], [1, 0.4] } In those vertices, ...
3
votes
1answer
61 views

Blind sorting an array with a singular sort function?

I am doing some interview prep, and I came across a question that really stumped me, and it didn't provide an answer. The premise of the question was as follows: You are given some unsorted array A ...
3
votes
2answers
902 views

Predicting energy consumption of households

I have the dataset which you can find here, containing many different characteristics of different houses, including their types of heating, or the number of adults and children living in the house. ...
3
votes
2answers
2k views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm? I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. ...
3
votes
1answer
1k views

How can I tell who is a truth teller and who is a liar?

This is a problem that I was given for my data structures and algorithms class. I am not sure how to tackle this problem. Can I get some assistance? At Hogwarts a new shipment of $n$ goblins has ...
2
votes
1answer
1k views

Why does using unary in subset sum problem result polynomial time complexity?

From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input). The number of bits in binary notation is obviously less ...
2
votes
2answers
885 views

How to write regular expression excluding certain pattern aba from albhabet set {a,b}? [duplicate]

Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite? Is there any generic way to write a regular ...
2
votes
1answer
214 views

Suppose G is simple graph with n vertices. Prove that G has twice as many edges as vertices only if $n\geq 5$

I just didn't understand the second part of the prove "G has twice as many edges as vertices only "... what do I actually have to prove ? I understand it like $n=2e$ , is it right ? then isn't it's ...
2
votes
1answer
381 views

Algorithm for computing partitions of a set of n elements into subsets of size m

I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m. For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be $\{\{\{...
2
votes
0answers
218 views

Difference between fully-reduced BDD and quasi-reduced BDD

I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for ...
2
votes
1answer
994 views

Direct edges of undirected graph so that all indegrees are even

Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even. For example, consider ...
2
votes
1answer
433 views

Algorithm to detect if word belongs to pushdown automaton

I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that. My thought at first would be to go ...
2
votes
2answers
682 views

Generalized data structure

Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and ...
2
votes
1answer
2k views

How to find max flow in a graph after decrementing an edge capacity?

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for ...
2
votes
1answer
2k views

How to get expected running time of hash table?

If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
2
votes
3answers
1k views

Feedback polynomial of 7-bit Linear Feedback Shift Register

My friend gave me a question to solve. The question he asked me was: the following sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I ...
2
votes
1answer
146 views

Disruption in the context of Genetic Algorithms

I'm trying to do a homework problem which references "disruption" in Genetic Algorithms. True or false? For 1-point and 2-point crossover, the schemata which have bits that are close ...
2
votes
1answer
276 views

Median of Medians Recurrence Relation for 3-grouping

So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like $$ T(n) = T(\...
2
votes
1answer
3k views

Reducing from Hamiltonian Cycle to Subgraph Isomorphism

I am reading Subgraph isomorphism problem I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article. ...
1
vote
1answer
281 views

Is this a legal Fibonacci heap?

Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? ...
1
vote
2answers
471 views

Broken stick problem

We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible. The amount of glue need to connect ...
1
vote
0answers
1k views

Problem with Cormen's treatment of the Rabin-Karp algorithm

I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. ...
1
vote
2answers
757 views

In what situations should a particular sorting algorithm, such as heap sort, be chosen over others?

In my algorithm class my teacher said that we should always use counting sort when we want to sort integers. After he said this I was curious to know in which situations I should choose one sort ...