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

How can you tell if you a piece of code has running time of logn?

I'm new to Data Structures and Algorithms and I would like an example of code (preferably java or any pseudocode) that shows logn running time. I know what n and n^k running time looks like (simple ...
0
votes
1answer
27 views

Combinatorics counts outcomes, what mathematics lists outcomes?

Since I've been learning combinatorics the past few days I've constantly found myself wanting to implement the combinatorics I've learned in various ways(mostly by writing software that analizes each ...
1
vote
0answers
17 views

Number theory formula needed

Problem: $10$ numbers modulo $77$ are given. Denote them by $a_1, a_2, ... , a_{10}$. I want to find a surjective function $f(a_1, ... ,a_{10})$ with following condition: $f(a_1, ... ,a_{10}) \neq a_i ...
1
vote
0answers
22 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
0
votes
0answers
18 views

Count ways to paint the grid

Given a rectangular grid of dimension N x M. We need to paint the grid with black or white color such that there is no rectangle of size X x Y having same color in each cell. Find the number of ways ...
0
votes
0answers
14 views

A Turing machine algorithm which determines other algorithms

Let $X$ be a Turing machine algorithm, which run as following: For a Turing machine algorithm A, X(A)=0 if A(A)=0 X(A)$\neq$0 if A(A)$\neq$0 We can code X easily. However, what's the ...
0
votes
2answers
16 views

How fast can you split a set of numbers into 2 sets, where the difference of each sum is maximized

How fast can you perform this task? More specifically, if there is a set of 2n elements, how fast could you split those elements into two groups of n elements where the sum of each group is of ...
0
votes
2answers
34 views

Multiplication and addition, but in a weird way.

'calculate the product of x and y by accumulating the sum of x copies of y' I'm stumped, what is it this exercise actually wants me to do? Express $x$ * $y$ as something else? I'm allowed to use an ...
0
votes
1answer
23 views

Distribute n balls across m bags when bags are not empty to get the same sizes

Thinking about the best solution of the next problem. Suppose we have m bags where $n_1, n_2, ..., n_m$ balls are already laid. We need to distribute new n balls across these bags to get almost the ...
1
vote
1answer
16 views

Expanding a recurrence relation with a summation involved

Question: $(10)$ Solve the recurrence in asymptotically tight big Oh function; $$t(n)=n+\sum_{i=1}^kt(a_in),$$ for the two cases (a) where $\sum_{i=1}^k a_i < 1$, and (b) where ...
0
votes
0answers
12 views

Algorithm to answer questions on dominated input

Consider a setting where we see inputs one-by-one, with each input being an $n$-tuple $(a_1,a_2,...,a_n)$, where each $a_i\in\{0,1\}$. For each new input we see, we have to answer two questions: 1) ...
0
votes
0answers
12 views

How to find all maximal chains and antichains in a finite bounded lattice

Is there a (possibly efficient) algorithm to find all maximal chains and antichains in a finite bounded lattice?
0
votes
0answers
23 views

Divide-and-Conquer algorithm for sorting ascending lists

Divide-and-conquer involves dividing the problems into as small sub-problems as possible and then recursively solving the sub-problems before combining the solutions to get an overall solution. The ...
0
votes
1answer
41 views

How to deal with summation with log bounds like: $\sum \limits_{i=1}^{\lg (n)}$ [on hold]

I came across this summation in my algorithms textbook. I've googled everywhere and can't seem to find anything on how to deal with these types of bounds. (Apparently it equals 2n as n approaches ...
0
votes
0answers
29 views

Winning probability calculating in a two-players game

The problem comes from an contest that is already over. There are two players playing the game. Given n cards each containing a number. In one go, any one of them ...
1
vote
0answers
40 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
0
votes
3answers
66 views

Prove that $1^{k} + 2^{k} + \cdots + n^{k}$ is $O (n^{k+1})$

I have the following to prove: $1^{k} + 2^{k} + \cdots + n^{k} \text{ is }O (n^{k+1})$ I have done the following: $$\frac {1^{k} + 2^{k} + \cdots + n^{k}}{n^k} \leq n$$ Am I on the right track? I ...
2
votes
4answers
47 views

Prove that $3^n$ is not $O(2^n)$.

I am working on some Big oh questions and I can't seem to get how disprove them. In this case we have: Prove that $3^n$ is not $O(2^n)$ I can see that its obvious just by looking at the two ...
0
votes
1answer
11 views

Help on understanding tax bracket computation

Warning: some codes Tax Bracket: 1 up to 5,070 ---- 10% ...
1
vote
1answer
43 views

Onion-peeling in O(n^2) time

I am working on the Onion-peeling problem, which is: given a number of points, return the amount of onion peels. For example, the one below has 5 onion peels. At a high level pseudo-code, it is ...
0
votes
0answers
35 views

counting the good numbers

We need to calculate Good Numbers in range from $A$ to $B$ (Both inclusive). A number $N$ is said to be a good Number if it satisfy following conditions : If we extract every $2$-digit number of $N$ ...
0
votes
0answers
18 views

Separate a list of spheres into several lists, each contained in a sphere with a radius no larger than specified.

I have a list of arbitrary spheres, what I want to end up with is that list separated into a number of groups, where spheres in each group all fit into thier specific larger sphere. The limitation is, ...
1
vote
1answer
30 views

How many binary string are there such that there are no k consecutive characters are the same?

Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same. Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
1
vote
1answer
21 views

Multiply two polynomial in O(nlog n) time

In order to multiply two polynomial , we need O(n^2) complexity. Is it possible to perform the multiplication in O(nlog n) time??
3
votes
1answer
71 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
0
votes
2answers
63 views

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

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
16 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
39 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 ...
0
votes
0answers
39 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 (I think it is foolish what am I writing) But can we reconvert proof using algorithm in set theory concept.For ...
2
votes
1answer
349 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
14 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
22 views

Extracting 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
81 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
12 views

Algorithm for Leaderboard Performance

Here's the situation I'm working on a leaderboard algorithm where multiple parameters play role. ...
1
vote
1answer
49 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
29 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
20 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
vote
1answer
18 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
23 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
24 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
23 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
13 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
22 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
14 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
24 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
23 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 ...
8
votes
1answer
192 views
+500

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 ...
1
vote
4answers
908 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
34 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? ...