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
2answers
64 views

Integrate $\int_{0}^{\pi} \frac{1}{a-b\cdot cos(x)}$ [closed]

Evaluate$$\int_{0}^{\pi} \frac{1}{a-b\cdot cos(x)}$$ Solution through either contour integral method or indefinite integral method please!
0
votes
1answer
17 views

Comparing algorithmic complexities

If an algorithm has a running time $ T(n) = O(n$ log $n)$, would it be possible to show that $T(n) = o(n^2)$?
1
vote
0answers
45 views

Finding a minimum stops along a route with a car that has unlimited tank

Suppose you want to go to a place that is D miles away, and you have a car that has unlimited fuel tank and has I unit of fuel initially. Along the route, there are N number of fuel stations, and the ...
1
vote
1answer
156 views

What are algorithm? Can we relate algorithm using set theory concepts?

What really algorithm are? Can we define algorithm as functions or in terms of set theory Can we reconvert proof using algorithm in set theory concept.For example, Theorem: A function defined on ...
1
vote
1answer
394 views

Put N mices in nearest holes

N mice are playing in the desert, when one of them notices some hawks flying in the sky. It alerts the other mice who now realize that the hawks are going to attack them very soon. They are scared and ...
0
votes
0answers
19 views

Summation for the “selection sort algorithm”

Sorry if the title was not clear enough. I noticed this summation in a textbook (analysis of the Selection Sort algorithm) $C(n) = \sum_{i=0}^{n-2}\sum_{j = i + 1}^{n-1} 1 = \sum_{i=0}^{n-2}{(n-1 - ...
0
votes
0answers
41 views

How to Extract the dual feasible search directions for the primal-dual potential reduction algorithm?

I am trying to implement the 4.4 Primal-dual potential reduction algorithm introduced in M.S Lobo et al.. Here is a screenshot depicts the algorithm flow: As ...
1
vote
1answer
86 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
0
votes
1answer
13 views

Algorithm for Leaderboard Performance

Here's the situation I'm working on a leaderboard algorithm where multiple parameters play role. ...
-1
votes
1answer
117 views

Count ways to form isosceles triangles

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
0
votes
1answer
33 views

Applying Master's Theorem to a recurrence of type $T(n) = \sqrt{2} \cdot T (n/2) + \log (n)$

I have a recurrence of type and I am trying to solve it with the Master's Theorem: $T(n) = \sqrt{2} \cdot T (n/2) + \log (n)$ I just tried to solve it by substituting $m = \log (n)$ such that ...
0
votes
2answers
21 views

How can i fit a specific count of rectangles in a bigger rectangle with a given size?

I have an area (rectangle) with a given size and i want to fit any number of smaller rectangles with variable height and width in it. I.e.: My rectangle is 1024x600 and i want to fit 150 smaller ...
-1
votes
1answer
44 views

Find next good string [closed]

A string S is called special if it satisfies the following two properties: ...
1
vote
0answers
9 views

Rotating Seating Algorithm

I am planning a speed dating networking session with round tables. My challenge is to rotate all participants to each of the tables while minimizing the times in which they sit with the same person. ...
0
votes
0answers
24 views

help writing an algorithm needed

I have the following problem and I need to write an algorithm to solve it: I have a set $A= \{A_1, A_2, A_3... A_n\}$, and a set $B=\{B_1, B_2, B_3,....B_n\}$ And a set $R= \{R_1, R_2, R_3… R_m\}$, ...
0
votes
0answers
38 views

Algorithm to optimize rectangles filling by rectangles

I have a set of rectangles, all of the same size (W,H) (in fact paper sheets). I have another set of n rectangles of different sizes (Wi,Hi), i = 1..n such that Wi <= W and Hi <= H (in fact ...
1
vote
0answers
24 views

Sampling from Cartesian product without replacement, but with balanced totals

I am struggling with a combinatorial task that I cannot reduce to any procedure I know: Given two sets $F, G$, I want to sample from $F \times G$ without replacement, but subject to the condition that ...
0
votes
0answers
14 views

How to implement the Integer Wavelet Transform for images?

I have a description of a wavelet transform, but I am unsure on how to implement the algorithm based on the information given: $A_i,_j = ((I_{2i,2j} + I_{2i+1,2j}) / 2 )_{floor}$ $V_i,_j = ...
1
vote
1answer
29 views

Finding Big-O with logarithmic functions

Give a big-O estimate for, $$ (nlog(n) +1)^{2} + (log(n) +1)(n^2 +1)$$ my attempt was: separate the function find the dominant values and take the big-O evaluation This is what I got: first ...
1
vote
0answers
15 views

Find two clusters in an ordinated array

As the titles goes, I have an array of sorted real positive numbers, and some information on the structure of the data. I know that there are two constants $a>>b>0$ and two other numbers ...
0
votes
1answer
27 views

Collatz sequences meet at a point

I was solving the problem,in which we are given two starting values of collatz sequence and our task is to say after how many steps their sequences “meet” for the first time. For ex - a= 7 , b= 8 a ...
0
votes
1answer
25 views

Given a set of integers find two disjoint subsets $I$ and $J$ so $|I|+|J|=k$ and $\sum\limits_{i \in I}x_i = \sum\limits_{j \in J}x_j = n^2$

Given a set of integers $1 \le x_1,x_2\dots,x_n \le n^2$ and a number $k \le n$. describe an algorithm that will determine if there exists two disjoned subsets $I$ and $J$ such that $|I|+|J|=k$ and ...
10
votes
2answers
271 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
2
votes
4answers
947 views

Find a 4-digit number which, divided by a 3-digit number (all unique digits) equals 9

This question is related to this Stack Overlow post. I tried following R code to find a 4 digit number divided by a 3 digit number (all unique digits) so that result equals 9: ...
1
vote
0answers
39 views

Indexing ranked permutations into other ranked permutations

Consider all permutations of 0, ..., n-1 under some ranking R. Given two ranks, i and j, what is the rank of the permutation that results from applying the i'th permutation to the j'th permutation? ...
2
votes
1answer
37 views

Proving that the height of a 2-3 tree is between $\log_3 N$ and $\lg N$

I am stuck on the problem of trying to prove the upper and lower bounds of a 2-3 tree. I think the most natural recourse is to use induction. However, my instructor told me that this was unnecessary ...
1
vote
1answer
46 views

Given the coordinates of four points on a plane, how can one determine the shape they form?

Actually it is an algorithm problem, however I cannot solve the problem. So, We have 4 points, how can we know what kind of shape(figure) can be drawn ? I want to learn mathematically. If possible i ...
0
votes
1answer
25 views

Can we transform given strings to get the same string?

There are 2 binaries string $A, B$ (string just contains $0$ or $1$) Input: $A_1, A_2,\dots,A_{50}$ and $B_1, B_2,\dots,B_{50}$ Note that: $A_{51} = B_{51} = A_{52} = B_{52} = \dots = A_{\inf} = ...
0
votes
2answers
38 views

Algorithm to calculate rating based on multiple reviews (using both review score and quantity)

First of all I must state that I am not a mathematician, so please correct me if I use wrong terminology. I am building a web application which needs to calculate the rating for each entity based on ...
0
votes
1answer
31 views

How do you typically prove recurrence relations?

The median-of-medians algorithm gives a recurrence relation $T(n) = T(n/5)+T(7n/10)+n = O(n)$. If the subgroup was changed to a size 3 or 7, how would this effect the recurrence relation? I came to ...
1
vote
1answer
17 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
0
votes
0answers
26 views

# of ways to sort. Quick Sort Problem.

This is a question about the quick sort algorithm and the # of ways I can place the books on shelves. I have to place a book on n number of shelves with m number of books; m >= n >= 1. But I have to ...
0
votes
0answers
23 views

Help Representing Python Algorithm Mathematically

For a project I am doing (using rhythm comparisons as an alternative to password authentication), I created an algorithm called "MalKonform", which compares keystroke times between two instances. ...
0
votes
0answers
22 views

Upper and Lower Bound Function for Recurrence Function

Suppose the first number in a sequence is 2, the second number is 3, and every following number is two times the (i-1)th number plus three times the (i-2)th number plus 2. (e.g. the first five numbers ...
1
vote
1answer
43 views

Algorithm to find subset of integers with highest sum under specific conditions

I have a set of N>1 integers all greater than 1, not necessarily all different. I need the most effective algorithm to find a subset of these numbers whose sum is the greatest. Unfortunately, there ...
2
votes
3answers
46 views

How to check a polygon in $\mathbb{R}^2$ for convexity.

Given $n$ points in $\mathbb{R}^2$, $\{p_1,p_2,\ldots,p_n\}$, how do we test if the (interior of the) polygon formed by drawing the line segments $[{p_{i-1},p_i}]$ for $1\le i \le n$ and also ...
1
vote
2answers
23 views

Alternative hash table analysis

Let us say that we have to hash $n$ elements to $m$ hash slots. Now what could be the average length of a chain. We can assume that prob. that 2 elements will map to a particular location will be ...
1
vote
3answers
57 views

What algorithm solves this problem? Non-linear measuring tape

A measuring tape is marked at 0, 5, 15 and 40. The distances between each mark are marked on top. At what distances should I mark 1 through 4, as well as 6-14 and 16-39? My math knowledge does not ...
-1
votes
1answer
36 views

Need help with an algorithmic function [closed]

Consider the following claim: for any positive constant c, f(cn) ∈ Θ(f(n))? Either show the claim is true or give a counterexample.
0
votes
2answers
45 views

Need help ordering a list of functions

List the functions below from lowest order to highest order. If any two or more are of the same order, indicate which. $n$, $n^3$, $2^n$, $\ln n$, $n^2$, $\ln^2 n$, $\sqrt n$, $2^{n−1}$, $\ln n$, ...
0
votes
1answer
24 views

Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$, where $0 < a < b$.

Let $a$ and $b$ be real numbers such that $0 < a < b$. Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$.
0
votes
1answer
132 views

Algorithms - Induction (packing cups into boxes)

I need some assistance on this question. I honestly just have no idea where to go with this one. Question: We have $n\cdot k$ cups. Each of these cups has one of the $k$ different colors. Assume $k$ ...
-1
votes
0answers
67 views

Door game between alice and bob

Alice and Bob are taking a walk in the Land Of Doors which is a magical place having a series of N adjacent doors that are either open or close. After a while they get bored and decide to do ...
1
vote
1answer
71 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
0
votes
1answer
31 views

Sequence of polynomials with rational coefficients

Clearly, the set of all univariate polynomials with rational coefficients is countable. That is, we can enumerate the members, say, as $x_1,x_2, \dots ,x_n, \dots $ How can we find $x_n$ for a given ...
0
votes
0answers
13 views

Is my proof correct : $\sum\limits_{i=0}^b a_in^i = \Theta(n^b)$

I want to prove : $$\sum\limits_{i=0}^b a_in^i= \Theta(n^b), a_o,a_1,...,a_b\in R, a_b \ne 0$$ So first, I prove that $\sum\limits_{i=0}^b a_in^i= O(n^b)$. First, Let's find $c$ $$ 0\le a_o + a_1n + ...
2
votes
1answer
80 views

{0,1}-solutions for integer equations via lattice base reduction?

I would like to find $\{0,1\}$-solutions of a system of equations of the form $$\left\{\begin{array}{c}\sum_{i\in I_1}x_i=1\\\sum_{i\in I_2}x_i=1\\\vdots\\\sum_{i\in I_k}x_i=1\end{array}\right.$$ ...
1
vote
0answers
35 views

Count balls to put in triangle

Given balls of radius $R$ we need to find how many balls can be put into a triangular container with sides $a,b$ and $c$. Example : Let $R=1$ and $a=3,b=4$ and $c=5$ then answer is $1$, as only one ...
0
votes
0answers
28 views

Division Algorithm With Negative and Absolute Value

(a) Prove that $d \, |\, a$ implies that $d \,| (−a)$. (b) Prove that $d\, |\, a$ if and only if $d \,| (−a)$. (c) Prove that $d \,|\, a$ if and only if $d\, \Big|\, |a|$. I can see why these ...
0
votes
0answers
17 views

Pina's algorithm

I have difficulty to understand the Pina's algorithm for enumerating all cycle bases of the undirected graphs. -Could you please explain to me using a detailed example ?