Questions related to design and analysis of algorithms
1
vote
0answers
32 views
Why is my bubble sort taking longer to sort a random array as opposed to a descending array?
I am in an entry-level algorithms class, and for our final project we are coding and thoroughly analyzing 6 different sorting methods. Part of the analyzation is timing the methods and comparing the ...
2
votes
2answers
32 views
To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$
I have done the proof until the point when $T(n) \leq cn^{\log7}$.
But when it comes to finding the value of constant $c$, I am getting stuck.
The given recurrence relation is $T(n) = 7T(n/2) + ...
0
votes
1answer
21 views
Recognizing interval graphs--“equivalent intervals”
I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper:
Each interval graph has a corresponding interval model in which two intervals overlap if
and only if ...
0
votes
0answers
10 views
Algorithm for queue with multiple repeated different interval events
I have N events, each repeats after some time ti. I want a queue where I can pop out next event.
For example, I have events A,B,C with intervals 2,3,5 At the beginning they all are in the queue with ...
3
votes
2answers
44 views
Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?
On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s. Each element of the matrix must be either ...
0
votes
0answers
13 views
(tensor decomposition) Is there a reference/source paper for the TUCKER_ALS() in Tensor Toolbox for MATLAB? [on hold]
TUCKER_ALS computes the best rank-(R1,R2,..,Rn) approximation of tensor X, according to the specified dimensions. I am using MATLAB Tensor Toolbox Version 2.5. I am wondering if I write a paper, how ...
2
votes
0answers
19 views
Measuring similarity of music, using lossy compression [migrated]
I have two sound clips $C_1,C_2$ which are pretty similar. I'd like to measure how perceptually similar they are, i.e., how similar a human would perceive the two to be. Is there a way to use a ...
-1
votes
0answers
40 views
1
vote
1answer
76 views
Big O running time for this algorithm?
Here's the code for the algorithm:
Foo(n)
lcm = 1
for i = 2 to n
lcm = lcm*i/Euclid(lcm,i)
return lcm
The running time of ...
2
votes
0answers
30 views
Sub-dividing a 2d array into regions
Suppose I have a array of real numbers with $n$ rows and $m$ columns. I want to consider possible ways of dividing that array into rectangular regions of three different possible types: a constant ...
0
votes
2answers
48 views
What is the Big O estimate of a nested for loop?
I am trying to figure out what the big o estimate of the following for loop is.
...
2
votes
2answers
71 views
Breaking up sum of power of 2s
I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays.
I encountered a sub-problem that requires me to break up sums of numbers which are power of ...
-2
votes
0answers
18 views
Randon 3SAT - when is a clause ture? [on hold]
Hi i have been give some random 3Sat data and ask to WalkSAT to solve for uni. Only thing is I don't really know where to start. I have some clauses say
-61 -63 26
-40 92 57
-74 -84 54
How do I ...
2
votes
2answers
93 views
What is the difference between maximal flow and maximum flow?
What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
1
vote
1answer
40 views
Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed
How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)?
Examples:
Partition Problem with negative numbers ...
1
vote
2answers
30 views
$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]
According to Introduction to algorithms by Cormen et al,
$$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why?
And which case of master theorem is it?
1
vote
1answer
86 views
What is the asymptotic runtime of the best known TSP solving algorithm?
I always thought that TSP currently requires time exponential in the number of cities to solve.
How, then, has Concorde optimally solved a TSP instance with
85,900 cities?!?
Is this a typo? Is ...
0
votes
1answer
61 views
Minesweeper master from Google Code Jam(2014) Qualification round [on hold]
Update: Several answers have been posted on the Stack Overflow version of the question.
This is a problem from Google Code Jam qualification round (which is over now).
QUESTION: How to solve this ...
0
votes
1answer
30 views
The most frequent integer value from set of intervals [on hold]
What is the fastest way to get one of the value from set of intervals which occurs most frequently?
For example if I have interval (0, 3) and (2, 4) the most frequent value can be 2 or 3.
0
votes
0answers
24 views
How to get time complexity of n queen puzzle algorithm(Using Backtracking)? [duplicate]
I have the following algorithm
...
1
vote
0answers
25 views
Gradient descent vs. Newton's method: which is more efficient?
Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both ...
0
votes
0answers
11 views
How to find number of similar elements in two rows of two matrices? [closed]
I am surrounded in a problem! I have two matrices and index of rows are input and i have to find number of similar elements in those two rows!..
Here is my code!...
...
1
vote
1answer
25 views
Time Complexity of Halley's Method
What is the time complexity of Halley's Method?
I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity ...
2
votes
2answers
84 views
EM algorithm for two Gaussian models
This is about basic machine learning which I do not understand clearly.
I have 2 Gaussian models $G_1$ and $G_2$ and given a list of data as below.
(1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)
I ...
2
votes
1answer
30 views
How to check if two sequences of setoid members are mutual rotations? [closed]
Task and terminology
Assume we have a set $X$ and two sequences $S_1 = (a_1, a_2, \ldots,a_n)$ and $S_2 = (b_1, b_2, \ldots,b_n)$, where $a_i \in X, b_i \in X, \forall i \in [1..n]$.
We define, that ...
5
votes
1answer
41 views
Maximum Stacking Height Problem
Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it?
Problem ("Maximum Stacking Height Problem")
Given $n$ polygons, find their ...
1
vote
1answer
32 views
Why are the two farthest points vertices of the Convex Hull?
I read that in a 2D space, the two points farthest away must be in the convex hull (CH).
Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point ...
2
votes
3answers
79 views
How is A* search superior to Dijkstra's algorithm
Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm.
How is it ...
8
votes
6answers
1k views
How is Dynamic programming different from Brute force
I was reading up on Dynamic Programming when I came across the following quote
A dynamic programming algorithm will examine all possible ways to
solve the problem and will pick the best ...
32
votes
2answers
2k views
Is there a system behind the magic of algorithm analysis?
There are lots of algorithm-analysis questions around. Many are similar, for instance those asking for an analysis of nested loops or divide & conquer algorithms, but most answers seem to be ...
0
votes
1answer
49 views
How do people measure performance overhead?
How do people measure performance overhead? Whenever someone is bragging about how their program or application performs better than another, they talk about particular measurements, eg time, ...
2
votes
1answer
52 views
How to optimally seperate a student body?
Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with ...
4
votes
1answer
34 views
Construct a digraph given its in-degree and out-degree distribution
Could anyone help me with this algorithmic problem:
Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph ...
0
votes
1answer
23 views
Boosting algorithms: Confusion between “weak classifiers” versus “number of boosting rounds”
I've been reading up on boosting algorithms.
I understand that the main crux of the algorithm is to build weak classifiers that are slightly better than random guessing, and then to add them up so ...
2
votes
2answers
107 views
Minimum path between two vertices passing through a given set exactly once
Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes ...
4
votes
3answers
78 views
How to enumerate a product set?
I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 ...
6
votes
2answers
136 views
If $\log xy=\log x+\log y$ then why multiplication is harder than addition?
Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this ...
6
votes
2answers
73 views
Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial
I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
1
vote
2answers
53 views
Perceptron learning rule doesn't work [on hold]
i'm a little bit lost ... can you help me ?
So I have this table of date (each row give a point with its group)
So i took a random weight let's say : [1, -2]
H = 1 if n =< 0
0 otherwise
...
1
vote
0answers
25 views
Difference between probabilistic and randomized algorithm [duplicate]
What I understated is this:
Probabilistic algorithm: an algorithm that produces result in determined time with a confidence value about the probability of the ...
1
vote
1answer
82 views
Dynamic programming VS Greedy Algroithms [on hold]
I have two True or False questions in my practice test that are related but I am unsure about:
...
3
votes
1answer
71 views
Unique keys in a binary search tree
I'm studying for my finals and I can across this statement.
"For a fixed set of (unique) keys, any binary search tree containing those keys can
be converted to any other BST on the same set of keys ...
0
votes
2answers
25 views
Best Resource Allocation Algorithm [on hold]
I am facing an algorithm design problem.
For a given building, I need to buy a generator capable of providing a maximum amount of energy X at one time.
Depending on the time of the day, the various ...
3
votes
1answer
471 views
Best solutions to 6 degrees of separation
From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check ...
1
vote
1answer
55 views
Automatic seat assignment algorithm [closed]
I am looking for articles relating to algorithms that deal with automatic selection of seating assignment.
I need an algorithm (preferably more than one) that can automatically select a seating place ...
2
votes
1answer
44 views
Solving System of Equations
(Re-posted from StackOverflow as suggested)
I have the following problem.
The functions $f(x),g(x)$ are defined as
$$
f(x) = \begin{cases} f_1(x) & 0 \leq x \leq 10, \\ f_2(x) & 10 < x ...
5
votes
1answer
76 views
How to compute a curious inverse
Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$. If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular. ...
2
votes
1answer
23 views
Partition overlapping polygons
On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are ...
2
votes
2answers
39 views
Reconstruct directed graph from list of ancestors for each node
I have a problem that I encountered that boils down to the following:
Considered this directed graph I found on Google:
I have the following information available to me
...
1
vote
1answer
62 views
Permute the subintervals of an interval partition to most closely align with a model partition
You are given two things: A fixed initial 'model' partition of an interval, e.g.
I------I---I-----I-------I----...
where each ...
