Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

2
votes
0answers
8 views

Card-buying algorithm

I'm trying to make an algorithm to calculate what combination of cards from what buyers I should get to get the cheapest deal. Taking the shipping costs into consideration. It's for a website called ...
0
votes
1answer
20 views

Complexity of general polynomial map evaluation is polynomial?

A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x ...
0
votes
0answers
15 views

k insertion and e insertion

I am studying words and transducers for the first time, and I have some questions. I looked up but it doesn't make sense to me. SO my task is to make a k insertion, but before that I have a ...
2
votes
1answer
47 views

Expected maximum bin load, for balls in bins with equal number of balls and bins

Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we ...
-1
votes
0answers
21 views

How to prove that any minimum vertex cover of a clique of size $n$ must have exactly $n-1$ vertices? [on hold]

I would appreciate any help with this question... I don't know how to prove Np-completeness when it's given with a new problem!!! How to prove that any minimum vertex cover of a clique of size $n$ ...
-1
votes
0answers
15 views

Prove that the set cover (U,F) is NP-hard? [on hold]

Prove that the set cover problem (U,F) is NP-hard, even if for each element from U, we have at most two subsets from the family F that cover this element
4
votes
2answers
310 views

Convex Hull algorithm - why it can't be computed using only comparisons

Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that: ...
0
votes
0answers
45 views

Studying Skiena. War Story: What’s Past is Prolog [on hold]

I am reading The Algorithm Design Manual, 2nd Edition. The book gives an example task and then explains how to solve it step by step. (The task and solution is detailed here) But I don't follow one ...
1
vote
0answers
45 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
44 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
30 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
12 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
67 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
14 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
41 views
1
vote
1answer
79 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
34 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
72 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? [closed]

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
94 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
41 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
88 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
75 views

Minesweeper master from Google Code Jam(2014) Qualification round [closed]

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 [closed]

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
1
vote
0answers
26 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
91 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
44 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
37 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
35 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
137 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
54 views

Perceptron learning rule doesn't work [closed]

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
83 views

Dynamic programming VS Greedy Algroithms [closed]

I have two True or False questions in my practice test that are related but I am unsure about: ...
3
votes
1answer
72 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 ...