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

learn more… | top users | synonyms (1)

15
votes
9answers
13k views

Efficient way to determine if a number is Perfect Square

Is there an efficient method to determine if a very large number (300 - 600 digits) is a perfect square without finding its square root. I tried finding the square root but I realized that even for ...
1
vote
1answer
18 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
3
votes
1answer
205 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
1answer
34 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
1
vote
1answer
217 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
1
vote
1answer
253 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
1
vote
1answer
123 views

Generating a random derangement

I'm having a problem about derangements that I'm trying to solve. Given a set $S = \{1,\ldots,n\}$, I want to generate a random derangement. I've considered generating a permutation and checking ...
0
votes
0answers
12 views

Strassens Matrix Multiplication Algorithm to compute product of 2 4X4 Matrices

Im trying to learn starssens matrix multiplication Algorithm.So far i know that it uses 7 multiplications and replaces a multiplication by several additions and subtractions,to achieve better ...
3
votes
0answers
599 views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
0
votes
1answer
29 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), ...
0
votes
2answers
17 views

Algorithm to find all possible base26 numbers of a 32-bit cropped value

I have following formula: base26value = 26(26(26(26(26(26a + b) + c) + d) + e) + f) + g The variables a..g have a range ...
0
votes
1answer
28 views

Kolmogorov complexity of an algorithm?

I've read that Kolmogorov comlexity is about calculating the least number of bits needed to describe a string or other mathematical objects. Does 'other mathematical objects' include algorithms too? ...
0
votes
2answers
104 views

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

Given a large integer $n$ (could be as large as $10^{18}$), how can I find all possible pairs of integers $(a,b)$ such that $$a^b=n.$$ A fast algorithm is preferable. The question How to quickly ...
1
vote
0answers
20 views

directed simple graph, all paths from node $ v_0 $ to an other node $ v $, MATLAB

consider a directed simple graph $ G=(V,E) $ with $ V=\lbrace v_0,v_1,\ldots,v_k \rbrace $ and adjacency matrix $ A=(a_{ij}) $, where $ a_{ij}=1 $ means, that there is an arc from node $ v_i $ to node ...
0
votes
1answer
72 views

How relevant is an inverted x-axis on a cartesian chart?

I'm a developer and some fellows here asked me if I could reverse x-axis on cartesian charts. Since this functionnality is not natively supported by the components I use, I wonder how relevant a chart ...
-2
votes
1answer
40 views

Best/Worst Test Cases

For the two functions, would their worst/best Big O cases change compared to each others? If so, how would they change. I believe that when dealing with Big O, order is the only thing that matters, so ...
0
votes
0answers
46 views
+50

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 ...
0
votes
1answer
32 views

How to simulate from a simple point process

Define a point process by the conditional intensity function $$\lambda^*(t) = \mu + \alpha \sum_{t_i < t} e^{-(t-t_i)}$$ where $\mu$ and $\alpha$ are positive parameters. I would like to ...
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
821 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
19 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
30 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 ...
2
votes
1answer
23 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
225 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
29 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 ...
1
vote
2answers
17 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
45 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
30 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
45 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 ...
4
votes
2answers
40 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
19 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
44 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
55 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
1answer
153 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
52 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
25 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
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 [closed]

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
477 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 ...