Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
1answer
17 views

Finding end point of straight line given starting point and angle

I have a program which computes the angle of skew of a scanned photograph. It returns the angle of skew in degrees. I now need to draw lines across the image which follow the angle of skew. These ...
0
votes
0answers
24 views

Using math functions to time finales of a fireworks show

This year, I have the honor of programming two finales for a fireworks show. I want to use math. I suspect that I should use a function such as square root or log to specify the decreasing pause ...
0
votes
0answers
14 views

Unrolling and rerolling with a different thickness

I have two rolls, the main one with two layers of material and the secondary one with just one of them. As the main one unrolls it loses one layer of thickness, and simultaneously the second one has ...
3
votes
2answers
53 views

Minimize Sum a_i / Sum b_i over subsets

I have two positive finite sequences $a_i$ and $b_i$, with $0 \leqslant i \leqslant n$. The problem is to find the subset $I$ of $\{0, ..., n\}$ that minimizes: $$\frac{\sum_{i \in I} a_i}{\sum_{i ...
-1
votes
2answers
34 views

How to generate all possible combinations for X numbers in PHP? [duplicate]

I would like to make function in PHP which would print all possible combinations for X numbers. For example, for input 2 result would be: 12 21 For input 3 ...
0
votes
1answer
39 views

Prove that $\sum_{i=0}^\infty i p_i = \sum_{i=1}^\infty q_i$

Given a table with m slots, indexed $0,1,\dots, m-1$ and n keys that are included in this table, $n \lt m$, with $m-n$ slots being empty, I'm given an algorithm that given a certain permutation of the ...
2
votes
1answer
40 views

Efficient Extended GCD Algorithm for Polynomials

For computing the GCD of two multivariate polynomials we have the Euclidian algorithm. However, it's well known that the Euclidian algorithm is not very efficient (because of intermediate expression ...
0
votes
0answers
11 views

Selecting a number of items according to multiple criteria

There's a very real-world application for this, but I've converted it into a simplified example to demonstrate my problem: Suppose you have a number of shapes of different shapes and colors. For ...
0
votes
1answer
222 views

Solution of Introduction to Algorithms 3rd edition (Cormen)

I'm studying algorithms by Cormen book. I have already find a pdf with the answers of the questions. www2.compute.dtu.dk/~phbi/files/teaching/solution.pdf But it isn't have the all solutions. I'm ...
1
vote
2answers
44 views

linear programing : maximize $\sum \limits_{i=1}^{n} C_i$ where $C_i$ is circumference of circle with center at $\{x_i,y_i\}$

given n points on $\mathbb{R^2}$ $\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$ formulate a linear program to maximize the sum of the circumference of all circles so any two circles won't intersect (two ...
0
votes
0answers
32 views

Smart Travelling Agent Problem

Smart travel agent, Mr. X's is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus ...
0
votes
0answers
12 views

How to normalise logarithm depending on the size of the range of possible values

I'm attempting to write a function which can be used to generate weighted random numbers between a set range, the size of which can arbitrarily grow and shrink, depending on some modifying value to ...
1
vote
1answer
41 views

Question about the algorithm.

A chocolate company decides to promote its chocolate bars by including a coupon with each bar. A bar costs a dollar and with c coupons you get a new bar. How much chocolate is a dollar worth? As from ...
0
votes
0answers
36 views

What is exactly a DFS tree?

Here's a question: Claim: Every time we run the DFS algorithm on the following graph, The DFS tree will be lanyard (?) True \ False, Explanation: I Googled but I'm not pretty ...
0
votes
1answer
25 views

Risch differential equation algorithm by Bronstein

I was implementing the algorithm by Manuel Bronstein for solving the Risch differential equation. My question is: What does Bronstein mean by "Order" in the algorithm poly_DE (exponential case, ...
0
votes
0answers
19 views

The problem category of sudoku Puzzle solved by search algorithms

Good day everybody, Sudoku puzzle solvers have been categorized in the literature to: Deductive algorithms that perceive sudoku as a hard constraint satisfaction problem (CSP) or Boolean ...
0
votes
1answer
24 views

Find Maximum-Matching in a tree $T(V, E)$ in $O(V)$

It's a question from a previous exam that I'm trying to solve with no success. Suggest a Dynamic-Programming algorithm for the following problem: Input: indirected tree $T(V, E)$. ...
2
votes
0answers
76 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
0
votes
0answers
32 views

Finding the point satisfying the condition

Given N interesting points on the plane. Each interesting point has integer coordinates. Also, all the interesting points form a strictly convex polygon. If we select two coordinates from these ...
0
votes
1answer
28 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
1
vote
0answers
31 views

Searching a common substring presence

Some time ago during an interview for software developer position I was asked the following task: Supposing we have two immense texts (like till million of characters each) and we are asked whether ...
0
votes
0answers
12 views

on-line Batched bin Packing

I have a project concerning "on-line Batched bin Packing" where the item sizes should be between 0 and 1 and have to be packed into bins of size 1. In my project I have to design a 3-batched online ...
1
vote
1answer
36 views

how do i find the shortest path/route/tour that visits every vertex at lest once

I have a non-directed non-weighted graph and i want to find the shortest path/route/tour (i don't know which is the correct definition) that visits every vertex at least once. Is there an algorithm ...
0
votes
0answers
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
0
votes
1answer
39 views

Minimum AND operation on subset

Given an array of size N . Let's create all the subsets of this array which contain at least 2 elements. Now, operate AND over the elements of each subset, and store the results in a new array. I ...
2
votes
0answers
16 views

map if-then-else to probability [closed]

I need an algorithm to transform game rules (p&p role playing) to probabilities, specifically conditional constructs built from if-then-else with conditions made of the boolean and relational ...
2
votes
2answers
31 views

Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
0
votes
1answer
25 views

Find all “critical nodes” in a graph

Say there is a graph in which every node is connected to every other by some path. How would i find the particular nodes, which if removed would lead to some of the nodes NOT being connected to all ...
0
votes
0answers
9 views

Algorithm to randomly distribute a fixed no. of points on a line such that density graph tends to a certain function?

Lets say I have 10 points. And I have 40 empty places. I want to randomly place those ten points in those places such that when I plot the avg. density of points vs. position, I should get a graph ...
0
votes
1answer
30 views

Reading set notation for the flow number

Could someone please help me to understand the following notation: Flow Number: In case of need, S refers to a set of flows, C(s) is called congestion and D(S) is dilation. How would you put in ...
4
votes
2answers
99 views

Count Number of Sequences

The question is: Given a sequence of positive integers A={1,2,3,...,N}. Count the number of sequences you can get after making K swaps between adjacent element on it for a given N ? My approach: My ...
2
votes
0answers
205 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
1
vote
0answers
34 views

Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
1
vote
1answer
49 views

Rating system for 2 vs 2, 2 vs 1 and 1 vs 1 game

We play in table football in such configurations: 2 vs 2 players 2 vs 1 1 vs 1 Team (consisting of 1 or 2 players) wins the single game when they score 10th goal. I would like to introduce a ...
2
votes
1answer
109 views

Counting triplets with red edges in each pair

Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path ...
0
votes
1answer
46 views

Bipartite graph set cover

I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is an undirected bipartite graph G with the two vertex sets V1, V2. ...
0
votes
1answer
34 views

Algorithms for finding the multiplicative order of an element in a group of integers mod m

What are some algorithms for finding the multiplicative order of an element in a group of integers mod m, besides the naive one?
2
votes
0answers
178 views

How to distribute 5-digit numbers in 5x5 matrices

I have 98000 5-digit numbers, from 00001 to 98000. I need to distribute these 98000 numbers in 14000 5x5 matrices. A matrix cell must contain only a digit from 0 to 9. Each matrix must receive 7 ...
1
vote
3answers
54 views

General expanded form of $(x+y+z)^k$ [duplicate]

(hope it doesn't seem so weird), I'm looking for a general expanded form of $(x+y+z)^k, k\in\mathbb{N}$. $k=1: x+y+z$ $k=2: x^2+y^2+z^2+2xy+2xz+2yz$ $k=3: ...
1
vote
0answers
22 views

number set with non-adjacent digits

I'm not sure such thing exists, or even if I'm asking for a valid thing, but I'll do my best describing it. At least the thing I want is similar to Gray code, so should be valid. So, I want to know ...
0
votes
1answer
61 views

Even Odd counting

Given an integer $Q$ and an array $A$ of size $N$, can we figure out the answer to each of the $Q$ queries? Each query contains two integers $x$ and $y$, and we need to find whether the value ...
1
vote
2answers
47 views

Does anyone know of any open source software for drawing/calculating the area of intersection of different shapes?

I would like to be able to draw any number of different shapes and determine the area of their intersections. I'm looking for free, open source software. I thought about trying to code something up ...
0
votes
1answer
37 views

Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
0
votes
0answers
10 views

Polynomial-time reduction and complexcity sets P and NP.

hello I am having difficulties to understand the topic of P,NP and Polynomial-time reduction. I have tried to search it on web and ask some of my friends , but i havent got any good answer . I wish ...
1
vote
0answers
34 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and ...
2
votes
1answer
57 views

how to compute a^x %p

Hi I want to calculate $a^x mod p$ where p is prime and $x$ is large. What I know is that since $p$ is prime, it forms a cyclic group with order $p$ ie $ a^p$ $mod$ $p = a$. Thus, my problem will be ...
0
votes
0answers
23 views

2-approximation for TSP-metric

I got stuck with the following question: Consider the following heuristic: Start with a tour containing only one vertex. At each step, find the vertex outside the tour with the lesser distance to ...
0
votes
0answers
10 views

Need help with rating algorithm

I'm currently working on a rating system for my multiplayer iPhone game. This is the official algorithm used in chess for what the computer "thinks" your win chance is based on an rating. ...
1
vote
1answer
44 views

Prove that the “even” subset sum problem is NP-complete

I need to prove that the even subset sum problem is NP-complete. "Given a finite set of natural numbers and an even number $n$, decide whether a subset of the given set exists such that the ...
0
votes
1answer
27 views

Algorithm to find Frobenius number

I realize that such a question may have already been asked, and having looked at a few, I didn't really understand how to calculate a frobenius number. So, is there a general equation that can be ...