1
vote
2answers
50 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
1
vote
0answers
15 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
0
votes
1answer
46 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
0
votes
0answers
42 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
0
votes
1answer
82 views

Find all subsets whose sum modulo a value is 0.

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A. One method which I know of is to store all subset sums modulo A and ...
0
votes
2answers
27 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
0
votes
1answer
61 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
0
votes
0answers
14 views

algorithm for traversing a fractal in a “maximally ordered” way

consider a multidimensional fractal that can be "traversed" in an arbitrary order. is there an algorithm for traversing a fractal in a "maximally ordered" way? in other words the algorithm has ...
1
vote
3answers
49 views

Why do the children of a node $n$ in a complete binary tree have indices $2n $ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...
0
votes
1answer
27 views

find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
0
votes
0answers
17 views

Binary counter with increment by powers of 2 worst case and amortized

Question: We define a binary counter with the function $Increment (i) $ that whenever called , it increments the counter by $2^i$. It does that by: starting from the i'th place in the counter: going ...
2
votes
3answers
38 views

Help making the distinction between polynomial and exponential time

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed ...
0
votes
0answers
10 views

parallelizing $k$-means

I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just ...
1
vote
0answers
14 views

Encoder based on large similar data

Let us say you (Alice) and another agent (Bob) share a large piece of data (say, the Gutenberg project collection of books, or the Linux kernel. You want to send a smaller but still large piece of ...
1
vote
1answer
36 views

Engineering notation algorithm, i.e. 1000 -> 1k, 0.001 -> 1m

I had to come up with a simple algorithm on a low powered embedded system, because dividing numbers by 1000s to get the wanted digits (first three basically) caused a loss in precision in the floating ...
2
votes
0answers
33 views

A* vs D* vs Dijkstra [closed]

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
1
vote
1answer
31 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
0
votes
1answer
26 views

Proving Upper Bound for Two Variable Function?

The question is: Prove (logn)^k = O(n) for every k>=1. I have never encounter a problem for proving an upper bound for two variables, so I am perplexed as to ...
0
votes
2answers
72 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
1
vote
1answer
64 views

Knuth-Bendix completion algorithm: word problem

Can someone explain me how to set up an algorithm to find the 12 normal forms of the group $A_4$ by making use of the Knuth-Bendix completion algorithm? So we have that $RRR=1, SSS=1$ and $RSRS=1$. ...
3
votes
1answer
95 views

No of pairs of elements whose XOR satisfies a condition

We are given a set of $n$ non-negative integers. We need to find the number of pairs of integers from this set whose $XOR$ is $ = K$. My approach is to sort the integers which takes $O(NlogN)$. Then ...
3
votes
1answer
56 views

Recursively deleting every second element in a list

This question got me thinking. If you have a list of length n and recursively delete every other element from the list until only one element remains, is there any ...
0
votes
0answers
23 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
0
votes
0answers
19 views

Universal hashing proof

So I tried doing this proof but I do not know how to start it properly. I know I have to show that the hash function family has the consistent and random property. The first is rather obvious to ...
0
votes
1answer
32 views

Derive Time from Sorting Method/Time Complexity

A sorting method with “Big-Oh” complexity O(n log n) spends exactly 1 millisecond to sort 1,000 data items. Assuming that time T(n) of sorting n items is directly proportional to n log n, that ...
0
votes
0answers
17 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
2
votes
1answer
69 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
2
votes
2answers
65 views

Avoid dividing by zero with just variables and basic operators

I am working on stats for a sports team, and one of the stats I have the ratio of Shots and Shots on Target (Which I call ...
0
votes
3answers
123 views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
1
vote
1answer
72 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
0
votes
1answer
30 views

Constrained disjoint subsets

How to partition $n$ weighted elements into $m$ disjoint subsets such that the sum of weight of all elements in a subset is less than equals to the capacity of $j$th subset ($c_j$) . It is given that ...
4
votes
0answers
61 views

Computational hard math problem

Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& ...
3
votes
1answer
102 views

An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
1
vote
2answers
41 views

Best way to generalize a distribution of data into smaller subsets?

Suppose I had a data set as follows: 168.95, 176.83, 178.13, 179.61, 179.44, 172.83, 173.37, 174.06, 174.94, 175.43, 175.73, 175.5, 173.78, 174.06, 172.71, 174.3, 178.38, 178.43, 177.18, 175.34, ...
0
votes
1answer
41 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
4
votes
0answers
51 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
0
votes
0answers
33 views

mathematical structure or algorithm for mapping a sinuous pattern ( a river)

I have a java application where I need to show a wooden log floating down a sinuous river. the problem is the river is in the shape of an S and for every frame i need to draw the wooden log. So I was ...
2
votes
0answers
36 views

LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
6
votes
0answers
104 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
2
votes
1answer
62 views

Combinatorics/Task Dependency

Here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
1
vote
0answers
59 views

Is there a proof that Encrypting and then Decrypting any data using AES 256 will result in the same data?

I use AES quite often at work (I'm a software programmer) and I trust that it "works" without understanding the maths behind it. It's a black box to me. Does a mathematical proof exist that AES 256 ...
1
vote
1answer
47 views

How can I encode this?

Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7. Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3). Note1: The order of the integers in the choice doesn't matter. This means ...
0
votes
0answers
52 views

Lower bound of maximum seating plans

10 people will sit in a row of 10 chairs. How do I calculate how many seating plans can be made, where two seating plan are considered the same if two plans share adjacent quadruples? or How can I ...
2
votes
2answers
90 views

How to efficiently encode this?

I have 5 ring oscillators whose frequencies are f1, f2, ..., f5. Each ring oscillator (RO) has 5 inverters. For each RO, I just randomly pick 3 inverters out of 5 inverters. For example, in RO1, I ...
1
vote
1answer
157 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 ...
0
votes
2answers
416 views

Proving a connected graph is a tree if the DFS and BFS traversals from the same node are equivalent

Let $G$ be a connected graph and $v$ be a vertex in $G$. Suppose a DFS traversal from $u$ is performed resulting in a tree $T$, and a BFS from $u$ also results in the same tree $T$. I would like to ...
2
votes
0answers
176 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
1
vote
3answers
100 views

how can we write abstract algorithms?

Writing pseudo-code for algorithms is common practice in the applied mathematics literature. It is also often the case that the ideal input of an algorithm is an infinite set, for example it could be ...
1
vote
2answers
40 views

Solving system of linear eqaution in special cases

I have to solve for $Ax=B$. Here the diagonal elements of $A$ are $-1$ and all other elements are $1$. $A$ is $n \times n$ matrix . In this special case can we solve for $x$ quickly? EDIT: quick is ...
1
vote
0answers
30 views

Generate Max Value Expression

How to insert * AND + OPERATORS between a given set of integers so that the expression evaluates to the max possible value if Set is [3,4,5,6,-2] it should give 3*4*5*6+-2 and also note that * gets ...