Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

0
votes
2answers
14 views

Bubble sort complexity calculation, unsure how it went from one step to another.

I'm looking at my textbooks steps for calculating the complexity of bubble sort...and it jumps a step where I don't know what exactly they did. I see everything up to that point using summation ...
1
vote
1answer
30 views

Sum of two elements is $x$

I read the following problem in the book Introduction to Algorithms by Cormen, Leiserson, Rives, Stein and I couldn't make any progress with it. There is a set of $n$ numbers. Give an algorithm that ...
2
votes
1answer
23 views

Complexity of generating a prime larger than $N$

Is it provably difficult to generate a prime larger than a prescribed $N$? For instance, if I want a prime of $1000$ digits, is there a way to do that deterministically, i.e., without resorting to AKS ...
2
votes
5answers
32 views

Prove a function is in Big-Oh and not in Big-Omega

We are told to use the definitions of Big-Oh and Big-Omega to prove that a given function is in $O(f(n))$ or $\Omega(f(n))$. It requires being able to use $c$ and $n_0$. Use the definitions to show ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
0
votes
0answers
34 views

Algorithm For Honest vs. Dishonest People

Consider a group of people. When two are taken and asked if the other is honest, they may each either reply that the other is honest, dishonest, or they may report that one is honest and the other is ...
0
votes
1answer
20 views

Solve logistic problem with graph - fitting boxes

Suppose you have $n$ boxes, each of which falls into one of the $k$ sizes, and you want to nest smaller ones into larger ones, such that no two boxes $A$ and $B$ are nested inside the same box, if ...
0
votes
0answers
12 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
0
votes
0answers
13 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
1answer
20 views

Proof of Mutually Inclusive Tree Properties

I don't know if that's the most accurate title. I'm trying to prove that one property of trees implies another without using any of the other properties. This is for homework. But I'm really just ...
0
votes
0answers
20 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
1
vote
1answer
21 views

How to show the running time of the following algorithm? [on hold]

The outer loop runs n times. The inner loop runs Math.floor(n/i) times. So it would be O(n*Math.floor(n/i)). I do not know how to transform that into a proper expression involving Big Oh and n. Maybe ...
0
votes
1answer
26 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
-7
votes
0answers
20 views

How to write an algo [on hold]

ecrire un algo qui calcule la moyenne de trois matiers d'un stagiaire(mat:a votre choix).et affecte une observation d'evaluation.
0
votes
0answers
12 views

Hamioltonian Circuit of Planar Graph of Order $2^n$

$G$ is a planar graph of order(= number of vertices) $2^n$. Questions: When $G$ has a Hamiltonian Circuit? Is there a polynomial or quasi polynomial time algorithm to decide whether $G$ has a ...
1
vote
1answer
43 views

Project allocation optimization with tricky constraint

I have an allocation problem that should be straightforward, except that it has very specific constraints. I want to assign approximately 300 students to 170 projects in pairs - so that each project ...
2
votes
2answers
29 views

Find $ k$ last digits of quotient

Suppose we have two integer numbers $a, b$ such that $b$ divides $a.$ Suppose that the number $a$ is very and very long and we cant to perform a division algorith. How to find last $k$ digits of ...
0
votes
1answer
42 views

Prove this greedy algorithm is optimal

So the question is: Consider the following different greedy algorithm for the Interval Scheduling algorithm: DifferentGreedySchedule - Initialize R to contain all intervals - While R is not empty - ...
1
vote
0answers
9 views

Determining next hash [on hold]

Given a series of hashes, were one hash is determined from the previous hash. i.e seed 0 => seed 1 => seed 2 => seed 3 Is it possible to determine the next seed or even the hash function itself?
1
vote
0answers
17 views

Number of global min cuts in undirected graph

I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$". It says $\forall i$ from $1$ to $n-1$ Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$. ...
0
votes
1answer
25 views

Geometric Meaning behind the algorithm (slope of the line + ray casting)

I'm trying to dissect the classic algorithm for finding if a point is inside a (simple) polygon. Please see: http://erich.realtimerendering.com/ptinpoly/ and ...
0
votes
1answer
39 views

algorithm to convert integer to 3 variables (rgb)

I try to store integer (real numbers) values into pixel data. The only way my api can store pixel data are RGB Colors. The idea behind it is, to store a large amount of vertices into the vram, rather ...
0
votes
1answer
14 views

How to divide a large rectangle into N smaller rectangles

I would like to divide a NxMpx rectangle(matrix) into X piece different size smaller rectangles. X is a variable so it dosn't have a fix value.The smaller rectangles must fill the 80-90% area of ...
0
votes
1answer
15 views

Algorithm to solve monetary obligation

i Need some help to find an algorithm for the following Problem. A Group of n persons lend each other some Money. A -> B, B -> C, C -> A, and so on. Now i want to find out how much Money each Person ...
0
votes
2answers
41 views

Evaluating Nested Summations

I'm trying to evaluate the following nested summation as a function of $n$: $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n \sum_{k=1}^j 1$$ So far I have: $$\sum_{i=1}^{n-1}\sum_{j=i+1}^n i+1$$ ...
1
vote
1answer
42 views

Stable Matching Problem Worst Preference?

Suppose we have one hundred pairs of women and men, and there is a man M that is ranked the second highest on every woman's preference rankings. Would it be possible that he ends up with the woman he ...
13
votes
0answers
88 views

Is there an efficient algorithm for this vertex cycle cover problem? [migrated]

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
0
votes
0answers
5 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

Note: I've also asked this question on StackOverflow here I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if ...
0
votes
0answers
24 views

Determining the minimal number of terms to use in a sum to approximate a number given a tolerance

In page 33-34 of Numerical Analysis by Burden & Faires an algorithm was given to compute the minimal value of $N$ for which $$|\ln{1.5}-P_N(1.5)|<10^{-5}\tag{1}$$,where ...
0
votes
1answer
23 views

ideal number gernerator

I was trying to solve a problem on Hackerearth. Here: https://www.hackerearth.com/problem/algorithm/ideal-random-number-generator/ I solved this partially:https://ideone.com/pXkHwQ (passed three ...
1
vote
1answer
45 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
1
vote
1answer
82 views

Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
0
votes
2answers
32 views

Newton's method for optimization

I have been reading about Newton's method and know that you can use it for optimization problems. However, does Newton's method only guarantee convergence to a local minimum or maximum, or can it be ...
0
votes
0answers
14 views

Weighted set cover variant- improvement over log(n)? [on hold]

Suppose we are asked to produce a set cover of minimal weight, where here w(S)=size(S) (and the weight of the cover is the sum of the weights of its sets). It is well known that in general weighted ...
-2
votes
0answers
15 views

Calculate full number of 7 card combinations beaten by my 7 card combo in texas poker. [closed]

Is there formula or algorithm for that? I can easily compare 2 seven card set but, is there formula for exact rank of my set? I am asking only about full 7 card sets.
4
votes
1answer
90 views
+50

How to partition $nk$ objects $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size $k$, so that no combination of $k$ is repeated.

What is an algorithm to partition $nk$ objects a total of $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size exactly $k$, so that no subset of size $k$ is ever repeated? For example, ...
0
votes
0answers
3 views

Convergence in constraint propagation

Introduction To the best of my knowledge, constraint propagation can be thought of (in a very heuristic sense) as a class of algorithms that solve a sort of generalized Sudoku problem. Some initial ...
0
votes
1answer
15 views

an array A[1..N] how many indexes (i,j) are there such that cumulative sum(i,j)%K = 0?

Lets say I have an array A[x1,x2,x3,...xN] of size N. for N = 4 , A = {x1,x2,x3,x4}. [1 based index] Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is ...
2
votes
1answer
21 views

Local Search algorithm: Why is the neighborhood structure $N : S \to 2^S$

I am writing a paper about meta heuristics and in particular local search. My tutor pointed this out: In every source (books, lectures, sites) I looked none explained why it is mapped like that. ...
1
vote
0answers
31 views

how to find out whether a point is surrounded by other points [duplicate]

I want to find out if a point $(x, y)$ is surrounded by a set of points. To understand my problem a short explanation: I am a programmer and I have a function for the user to select objects by ...
0
votes
0answers
14 views

worst-case time complexity of bijective function [closed]

$A=\{a_1,a_2,\dots ,a_n\}; B=\{b_1,b_2,\dots,b_n\}$. Let $f:A\to B$ be a function.Write an algorithm in pseudocode that returns $1$ if $f$ is bijective and $0$ otherwise. And calculate the worst case ...
1
vote
1answer
22 views

Average case of element comparisons when searching for an element x with a specific probability

I just had a midterm, and unfortunately our professor has stated that he will neither discuss nor post any solutions to the midterm, so I'm posting a question that was on it here in hopes that someone ...
1
vote
0answers
14 views

Applying the convolution theorem in the presence of a twiddle factor

The convolution theorem says that a 2-d cyclic convolution like $C = U \ast V$ can be evaluated more quickly than doing the raw sum $C_{i,j} = \sum_{a,b}^n U_{a,b} V_{i-a,j-b}$ for each point (assume ...
-2
votes
0answers
13 views

Parallel Luby Algorithm för finding Maximal independent set

This the Algorithm of Luby: MIS Luby Algorithm This Algorithm at the end spent O(log n). I want to understand why exactly O(log n), I need also a mathematical prove of this. Also How many ...
0
votes
0answers
14 views

Finding best local axis system of a set of points

I’m looking for a way to find the best axis system for a set of points and its tessellation – triangles, linking points to each others. The idea is that I’d like to orient a mesh using that axis ...
0
votes
0answers
15 views

How to find the best-case and average-case number of comparisons performed by a comparison tree?

So I'm reviewing some material before a midterm tomorrow and I came across this question: ...
0
votes
1answer
22 views

Polygon Equal Edge Offsetting?

If I have a random polygon of any complexity, be it a square or an irregular 20 sided polygon, how can I scale this up? I know the coordinates of each point on the polygon, but that is all. Another ...
0
votes
1answer
18 views

Implementing a function whose representation has a singularity.

$\newcommand{\R}{\mathbb R}$ Suppose I want to calculate the value of a continuous function $f\colon(a,b) \to \R$, with $a,b\in\R$, where there are functions $g,h\colon (a,b)\to\R$ such that for ...
0
votes
0answers
14 views

Algorithm to get the maximum size of n rectangles that fit into a rectangle with a given width and height

I have the same problem like this guy here, except that I need to change the algorithm posted there to calculate rectangles instead of squares, because I use this to calculate a grid of icons (square ...
0
votes
1answer
32 views

scientific computing problem, error analysis and writing algorithm

For $f(x)=(1-\cos(x))/x^2$, (a) Analytically evaluate $\lim_{x→0} f(x) = L$. (b) As $x→0$, at what rate does $f(x)→L$? (c) Suppose that we are able to represent floating point numbers with $N$ ...