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

learn more… | top users | synonyms (1)

2
votes
4answers
1k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
1
vote
1answer
802 views

RGB to HSV Color Conversion Algorithm

I'm a programmer looking to build an RGB to HSV color converter. I found an algorithm, but I have very little mathematical background and I'm not quite sure what's going on with it. A step-by-step ...
3
votes
4answers
229 views

stuck with master method

$$T (n) = 3T (n/5) + \log^2 n$$ i am trying to solve this recurrence i have been told that it is master methods case 1 but how do i compare $\log^2n$ with $n^ {\log_5 3}$
-1
votes
1answer
17 views

Determine fraction length of fixed-point binary

How to determine fraction length of fixed-point binary so that distinct entries of a group of decimal numbers (for example: 1, 0.456, 0.444) remain distinct after converting them from decimal to ...
0
votes
0answers
26 views

Can someone help me with the following math question/dilemma?

I have a pool of objects that are randomly selected from a global object database. The objects certain numeric attributes: The objects from the pool are fed to users in real time Users will either ...
0
votes
2answers
64 views

Finding all possible pairs of integers $(a,b)$ such that $a^b=n$. [duplicate]

Given an integer $n$, how can I find all possible pairs of integers $(a,b)$ such that $$a^b=n.$$ A fast algorithm is preferable.
2
votes
1answer
20 views

The probability of getting a certain image by random pixelation

Well, seeing that I'm terribly bad at math I don't know how to solve this, I'll try to explain, excuse me if I sound dumb. Just suppose that I've got a photo/image with 320x240 resolution and 24 bit ...
1
vote
0answers
23 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
3
votes
3answers
207 views

Solving inhomogenous ODE

I have an inhomogenous ODE. The main issue here is variables are matrices. It is bit of matrix calculus. A solution would be highly appreciated interms of x . I guess we can use same methods for ...
6
votes
3answers
2k views

how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$? Also, is it possible to solve this recurrence by the Master method?
2
votes
1answer
25 views

Show that the height of the heap is $\lfloor \lg n \rfloor$

I want to show that a heap with $n$ elements has the height $ \lfloor \lg n\rfloor$. That's what I have tried: The "best" case is a complete binary tree,and then it is of the form: So,the height ...
0
votes
0answers
17 views

Find a kernel in a directed graph.

It's a question from a sample exam I'm trying to solve but with no success yet. Let $G(V, E)$ be a directed graph. set $A \subseteq V$ is a kernel if: i. $\forall u,v\in A \implies (u, v), ...
1
vote
2answers
11 views

Asymptotic Notations in limits

Can the asymptotic notations, like Big O, be defined using limits? example:- Lim x->infi (f(n)/g(n))=c for defining f(n)=O(g(n)) If not, why??
-1
votes
1answer
40 views

Friends meeting at point

N friends live in different houses spread across the city.There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same ...
0
votes
0answers
20 views

Is complexity change when multiply with some number

The power operation with modulo operation $a^b \mod n$ has time complexity $O(\log n)$. what happen when it is multiplied with a number $p·a^b \mod n$, it can be read as $(p \mod n)(a^b \mod n)$. Is ...
1
vote
1answer
33 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
0
votes
0answers
29 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
4
votes
2answers
39 views

Using proof by induction to solve recurrence relation?

$$T(n) = \begin{cases} 1 & \text{ if } n = 1,\\\\ T(n/2)+d & \text{ if } n > 1 \\\\ \end{cases} $$ is $T(n) \leq c\log_2 n$ I'm still new to recurrence relations, so any ...
0
votes
0answers
18 views

Stopping angular momentum to obtain a particular angle

While the overall project relates to software development, it boils down to a simple (i think) physics problem. I have a joint (a motor, pretty much.) that needs to move to a specific angle. I can ...
-1
votes
0answers
43 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
1
vote
1answer
31 views

Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
1
vote
0answers
50 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
3
votes
2answers
146 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
1
vote
1answer
51 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
1
vote
3answers
24 views

Find an odd-length cycle in an undirected graph.

I have an exam next week and I found a question that I have difficults to solve: Given the following: Input: Simple undirected graph $G(V, E)$. Output: Find an odd-length cycle in $G$ or ...
2
votes
1answer
49 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
1
vote
0answers
92 views
+100

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards?
1
vote
3answers
30 views

Nth value of Function

Given x and y we define a function as follow : f(1)=x f(2)=y f(i)=f(i-1) + f(i+1) for i>2 Now given x and y, how to calculate f(n) Example : If x=2 and y=3 ...
-1
votes
1answer
32 views

Who will be last [on hold]

There are n children in school and teacher is going to give some candies to them. Let's number all the children from 1 to n. The i-th child wants to get at least a[i] candies. Teacher asks children ...
0
votes
0answers
32 views

Backward Substitution Method Questions

Question-1 is, G(n) = 2G(n-1) if n is odd and n≥1; G(n) = G(n-1)+G(n-2) if n is even and n>0; G(0) = 1 Solve for both odd and even values of n. Use backward substitution method ? I suppose; In the ...
2
votes
4answers
467 views

Numbers whose digits sum to 7

Let $S$ be the sequence of all positive integers whose decimal digits add to exactly 7, in increasing order: $$S = \langle7, 16, 25, \ldots, 70, 106, 115, 124, \ldots 160, 205, \ldots, 10230010, ...
3
votes
1answer
37 views

Partial sums of Pillai's function

Pillai’s arithmetical function (gcd-sum function) is defined by $$ P(n) = \sum_{k=1}^n\gcd(k,n) $$ Let $\sum_{n\leq x}P(n)$ be summation of all values of P for all $n$ up to given $x$. I dervied that ...
0
votes
1answer
17 views

Given a value and an arbitrary range, finding equivalent value in other arbitrary range

While strictly related to a programming project of mine, the problem in itself boils down to a math problem, as I am not sure which steps to take to produce the results i need. I have an input value ...
0
votes
3answers
2k views

Minimum moves to reach destination [closed]

Given that a person is standing at $(0,0)$ and initially look in direction of $X$-axis. Now he can walk only at right angle to previous move. Like if he has to go to $(3,3)$ then $6$ moves are ...
0
votes
0answers
53 views

QR decomposition algorithm

According to G. W. Stewart (Matrix Algorithms: Volume 1, Basic Decompositions) given an $n\times p$ matrix $A$, let $m=\min\{n,p\}$. The Stewart's Householder triangularization algorithm (Chapter 4, ...
6
votes
4answers
68 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
2
votes
2answers
352 views

Dijkstra's Shortest-Path Algorithm

I'm presented with the following algorithm: Dijkstra's Shortest-Path Algorithm This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted ...
2
votes
2answers
53 views

The value of loop variable at the end of a loop in the insertion sort

I am looking at the algorithm of the insertion sort: Input: $A[1 \dots n]$ ...
1
vote
0answers
27 views

Iterative Mean, Covariance Algorithm Convergence

The problem is to show that the following iterations converge to the vector $\mu$ and the matrix $\Sigma$. We have data in the form of nx1 vectors $\mathbf{Q}_k$, $1 \leq k \leq N$ where ...
2
votes
1answer
41 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
0
votes
1answer
35 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
0
votes
0answers
37 views

Global optimization

Assume that I want to find the global minimum of a non-linear, non-convex, multidimensional function subject to several restrictions. Could you recommend me any deterministic strategy which can ...
0
votes
1answer
43 views

Need to figure out how to do the math for deck of cards using different searches.

Below are the two questions I found from the websites ( I have added the link below ), that I am interested in learning the answers. My intention are not to post the answers for that guy but, I ...
1
vote
1answer
256 views

Algorithm for generating an ordered list of pair products

For problem 4 in the euler project part of the assignment is to generate a list of products of 3-digit numbers. The easy way is to just do a cartesian product (I think it's called), and after that ...
1
vote
1answer
28 views

Proving an asymptotic run time is faster than another using L’Hôpital’s

I'm working on a problem: Show using L’Hôpital’s Rule that a running time of $n\log(n)$ is asymptotically faster than (i.e., little-oh of) a running time of $\frac{n^2}{\log(n)}$.` I suppose a ...
2
votes
1answer
48 views

recurrence relation dependent inversly on n

Is there any efficient way to solve $F(n)=F(n-1)+1/n$ on $\mathcal{O}(\log n)$ time like we have matrix expo. for fibonacci series ?
6
votes
2answers
267 views

Algorithm fot planarity test in graphs

I am implementing a graph library and I want to include some basic graph algorithms in it. I have read about planar graphs and I decided to include in my library a function that checks if a graph is ...
0
votes
0answers
16 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
-1
votes
1answer
176 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
0
votes
4answers
53 views

Is it correct to write gcd(a,b) if a<b?

While creating an algorithm to compute the greatest common divisor of two numbers I saw that — on various websites/books — when you have "gcd(a,b)" a is superior to b ; is it an obligation or am I ...