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
0answers
3 views

SPSA loss function

I need a simple implementation (in Matlab) of the most basic SPSA algorithm for a friend of mine. I have found this code from J.C. Spall but I don't know where to find an implementation of an ...
1
vote
1answer
61 views

Find the pair of values $a[i]$, $a[j]$ such that $a[i]\,\&\,a[j]$ is maximum

Given a list of positive integers, find the largest possible value of $a[i]$ $\&$ $a[j]$, where $i$, $j$ are indices of the list. $ i\ne j $, $a[i]\,\&\,a[j]$ is bitwise AND of $a[i]$ and ...
-1
votes
0answers
53 views

Maximise and operation [duplicate]

Given an array of $n$ non-negative integers $A_1, A_2, \dots, A_N$, find a pair of integers $A_u$, $A_v$, where $1 \leq u < v \leq N$, such that the bitwise-and ($A_u$ and $A_v$) is as large as ...
2
votes
1answer
48 views

Why is the sentence true?

I am looking at the algorithm of the insertion sort: ...
0
votes
1answer
37 views

Best approach or algorithm to solve equation with multiple variables?

I have an equation : $A^6x_1 + A^5x_2 + A^4x_3 + A^3x_4 + A^2x_5 + A^1x_6 + x_7 = B$ What can be the best algorithm/approach I can use to crack this? $A$ and $B$ are constants. $x_1,x_2...x_7$ are ...
0
votes
0answers
19 views

How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting algorithim

If we assume reblalancing an AVL tree of height n after an insertion or deletion takes O(n) operations. How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting ...
1
vote
0answers
22 views

Lowest sum of 2 sets of number pairs

I am given a set of unique integers $n$. I need to compute the smallest sum $s$ such that there are two different pairs of integers $(x1, x2)$ and $(y1, y2)$ where $x1 < x2$ and $y1 < y2$ and ...
1
vote
0answers
34 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers {a1....an} and another number k. I need to find whether sum of any combination of numbers in the set ...
2
votes
2answers
30 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 ...
0
votes
1answer
56 views

Algorithm for a counter [on hold]

I am looking for an accurate algorithm for calculation required in any kind of counter, Like for example I have two values a: max 48 bits b: max 30 bits x: (a << 30) | (b); Now, if value of b ...
1
vote
1answer
39 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 ...
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 ...
0
votes
2answers
22 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
31 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? ...
1
vote
0answers
21 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 ...
-3
votes
1answer
41 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 ...
-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 ...
0
votes
2answers
107 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 ...
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 & ...
0
votes
1answer
30 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), ...
2
votes
1answer
30 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??
0
votes
0answers
32 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 ...
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 ...
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
49 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 ...
-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
votes
1answer
47 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 ...
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
56 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 ...
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
1answer
57 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
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
36 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 ...
1
vote
3answers
27 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 ...
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 ...
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 ...
2
votes
4answers
480 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, ...
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 ...
1
vote
0answers
28 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 ...
3
votes
0answers
225 views

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?
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 ...
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, ...
2
votes
1answer
42 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
45 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 ...
0
votes
0answers
39 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 ...
-1
votes
1answer
177 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 ...