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

792 questions
Filter by
Sorted by
Tagged with
299 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
795 views

### Finding the smallest string that contains a given set of substrings

The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible....
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 ...
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 ...
3k views

### What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
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 ...
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 ...
398 views

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 ...
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 ...
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. ...
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 ...
132 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 ...
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 ...
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 ...
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 ...
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 ...
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.) ...
621 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 ...
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 ...
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\}$ ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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$ (...
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. ...
888 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 ...
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 ...
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 ...
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 ...
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, ...
246 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 ...
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-...
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. ...
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 ...
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. ...
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 ...
1k views

### Finding the $k$-smallest elements in a min-heap

Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ ...
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 ...