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
4
votes
1answer
284 views

Bijective algorithm(s) that can shuffle a range of numbers back and forth

I've spent the last hours trying to come up with an algorithm that shuffles an ordered set of numbers (i.e a simple range of numbers) in a way that I can retrieve from a shuffled value the original ...
4
votes
2answers
2k views

without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?

In the text book, Introduction to Algorithm, 3rd Edition. In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says: I am wondering how triangle ...
4
votes
1answer
398 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
1answer
3k views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
4
votes
2answers
392 views

Mathematically determine if two strings are permutations of each other

I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each ...
3
votes
1answer
272 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 ...
3
votes
1answer
4k views

How does “Greedy Stays Ahead” Prove an Optimal Greedy Algorithm?

I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem. On the second page of Cornell's Greedy Stays ...
3
votes
1answer
223 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
2answers
176 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 ...
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
479 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
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
1answer
93 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
0answers
166 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 ...
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
1answer
131 views

Algorithm undirected graph to directed strongly connected graph

For an undirected connected graph $G=(V,E)$ given as adjacency list I want to find a directed strongly connected graph $G=(V,E')$ where each $e' \in E'$ is either $(u,v)$ or $(v,u)$ if we look at its ...
1
vote
1answer
536 views

Derandomization of vertex cover algorithm

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$. Add to ...
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 ...
20
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
165 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
615 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
7k 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
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 ...
5
votes
1answer
483 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
1answer
343 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$ ...
4
votes
3answers
446 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
2answers
695 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 ...
4
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. ...
4
votes
1answer
4k views

Matrix Chain Multiplication Greedy Approach

In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic ...
4
votes
1answer
887 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
1answer
487 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
70 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 ...
3
votes
1answer
2k 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 ...
3
votes
1answer
245 views

Find expectation with Chernoff bound

We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every ...
3
votes
2answers
924 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
1answer
178 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
1answer
65 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
104 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, ...
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
532 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
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
1answer
242 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
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. ...
2
votes
0answers
219 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
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
1k 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
473 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 ...