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.

9
votes
1answer
151 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.) ...
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 ...
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
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
407 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
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\}$ ...
4
votes
3answers
185 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
315 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
454 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
674 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
1answer
725 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
2answers
62 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
174 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
891 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
84 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
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 ...
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. ...
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
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
1answer
197 views

Basic requirements for Integrality gap examples

I have the following question about giving a series of examples of range spaces for my Hitting Set problem that establish a lower bound for the integrality gap (IG). IG is the supremum of ratio of ...
2
votes
1answer
895 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
3answers
485 views

Which fingerprinting/hashing algorithms support compounding?

The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as: Some fingerprinting algorithms allow the fingerprint of a composite file to ...
2
votes
2answers
662 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 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
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
0answers
210 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
245 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
145 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
2answers
837 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 ...
1
vote
2answers
832 views

Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford ...
1
vote
2answers
464 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
1answer
274 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
0answers
985 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
712 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 ...
1
vote
1answer
312 views

Euclid's Algorithm Time Complexity

I have a question about the Euclid's Algorithm for finding greatest common divisors. gcd(p,q) where p > q and q is a n-bit integer. I'm trying to follow a time complexity analysis on the algorithm (...
1
vote
0answers
62 views

Exponential maths operator

I have written a math library which handles really big numbers with good precision. Each digit is stored in a nibble and a 'nibble array' makes up the number. There is no epsilon portion, as for ...
0
votes
2answers
1k views

Sorting an array of length $n$ with $k$ distinct elements

There is an integer array that contain $n$ numbers, in the array there are $k$ distinct elements up to $k = 50$. Is it possible to sort this array in linear time, by using only comparisons? I know ...
0
votes
1answer
1k views

Divide and Conquer majority element algorithm

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array) I came up with this linear divide and conquer algorithm, but I'm ...
0
votes
0answers
263 views

Hamiltonian path in dynamic graph

Given an undirected Graph. I want to find a hamiltonian path with no restriction to starting or ending vertices. I know there are some smart algorithms for solving that. Now let's make things ...
0
votes
3answers
677 views

Modification of Dijkstra's algorithm

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality? There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
-1
votes
1answer
1k views

Minimal Spanning tree and Prim's Algorithm

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
-1
votes
2answers
835 views

Deleting edges from complete graph

I have a complete undirected graph with $V$ vertices and $\frac{V(V - 1)}{2}$ edges. Then, I remove $K$ edges $(a_i, b_i)$. I want to know if the graph is still connected after performing all the ...
-1
votes
1answer
61 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
78
votes
8answers
53k views

Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
49
votes
4answers
48k views

What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
35
votes
3answers
36k views

Factorial algorithm more efficient than naive multiplication

I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further ...
42
votes
2answers
64k views

Find median of unsorted array in $O(n)$ time

To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take ...
41
votes
7answers
62k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
25
votes
3answers
27k 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 ...