All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag.

learn more… | top users | synonyms

-1
votes
0answers
11 views

Entropy of sum of two dependent random variables [on hold]

What is the entropy of sum of two dependent random variables, $$h(X+Y)$$
2
votes
1answer
25 views

Algorithm to determine if integer matrix is similar to symmetric integer matrix with nonnegative entries

Let $A\in M_n(\mathbb{C})$ be a matrix with integer entries (treated as a matrix over the complex numbers). Is there an efficient way to check if $A$ is similar to a symmetric matrix with nonnegative ...
0
votes
1answer
28 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
2
votes
1answer
43 views

Using Big-O to analyze an algorithm's effectiveness

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I ...
0
votes
0answers
5 views

Calculating peak achievable performance of a dot product of two vectors from the example

I am trying to get the concept of an example. The example shows me all data but I just wonder where certain numbers come from. Here's the example. Consider a memory system with level 1 cache of 64 ...
0
votes
1answer
22 views

Fibonacci proof with a language

The proof I am working toward achieving is as follows: I know this can be proven using induction, and in doing so, I will need to: show when n = 2, F₂ = G₀; when n = 3, F₃ = G₁; if $F_{n -1} = ...
2
votes
2answers
53 views

Sum of a Series to Infinity

Evaluate the following sums: $\sum\limits_{i=0}^\infty\frac1{4^i}$. $\sum\limits_{i=0}^\infty\frac i{4^i}$. $\sum\limits_{i=0}^\infty\frac {i^2}{4^i}$. $\sum\limits_{i=0}^\infty\frac ...
7
votes
3answers
2k views

Simplifying Catalan number recurrence relation

While solving a problem, I reduced it in the form of the following recurrence relation. $ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $ However ...
-1
votes
0answers
27 views

An Advice Concerning Master's Programme [on hold]

Which of these programmes is a better choice, if one wants to pursue a degree in pure mathematics? (In Geometry, Topology and Algebra, in particular, algebraic geometry) 1) ...
1
vote
1answer
23 views

Calculating $(\lambda x.(x+y))1$

$(\lambda x.(x+y))1$ returns(I think): $(1+y)$. Is $(1+y)$ another lambda function so I'd write: $\lambda y.(1+y)$ or is it just $(1+y)$ and if so what does that mean?
1
vote
2answers
21 views

Most negative number (in octal and hex) of a 16-bit one's complement system?

In a 16-bit one's complement system, how do you represent the most negative number in octal and hex? One's complement: http://en.wikipedia.org/wiki/Ones'_complement The most negative 16-bit number ...
0
votes
1answer
32 views

Understand a Maple output

My goal is to solve for $L$ in $\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} = \sum_{s=0}^k{L \choose s}{n-L \choose s}s!\frac{(2k-2s)!}{2^{k-s}(k-s)!)}{L-s \choose 2k-2s}.$ I tried to use the solve ...
1
vote
1answer
22 views

Why is the invariant of the following state machine (2 mod 5) OR (3 mod 5)?

Consider a state machine with tuple of numbers describing its state, i.e. $(i,j)$ such that $i \geq 0$ and $j \geq 0$. The initial state is $q_0 =(i,j) = (15, 12)$ There are only two transitions ...
1
vote
2answers
17 views

Prove that the binary representation of a number n will use floor(lg(n)) + 1 bits.

I'm taking Computer Algorithms class and one of my problems is from Skiena's Algorithm Design Manual, 2-41: Prove that the binary representation of $n \ge 1$ has $\lfloor \lg n \rfloor +1$ bits ...
1
vote
0answers
31 views

Computer program to simplify formulas

What is the computer program that attempts to simplify sums of binomial coefficients, factorials, etc.? Possibly Zeilberger wrote it, but I'm unsure. If so, possibly it was talked about in his A=B ...
0
votes
1answer
20 views

Find base of numbers in a sum?

is there an easier way to find the base A in the following without essentially brute-forcing it with different conversions until I get the result? Again, trying to find base A such that the following ...
0
votes
0answers
15 views

way-below in cartesian product

I have homework about domain theory. I did not have idea to solve it. Let $P$ be poset and $x$ and $y$ be two elements of $P$. $x$ is way-below $y$, in notation $x\ll y$ iff for every directed set ...
0
votes
1answer
19 views

Constructing a while loop in R for Newton's method

I'm very, very new to R, and my instructor's example seemed like a special case (or I just don't know how to extrapolate his syntax to my problem). Here's the example we used: Approximate the square ...
5
votes
3answers
255 views

How to encode matrices uniquely

Given a square matrix $A=[a_{ij}]_{n \times n}$, an operation $swap(A, i, j)$ is defined to swap row $i$ and $j$ of $A$ and do the same thing with the corresponding columns. For example, in the ...
3
votes
3answers
125 views

$2x_1 + 2x_2 + \cdots + 2x_6 + x_7 = N$

How do I find the number of integral solutions to the equation - $$2x_1 + 2x_2 + \cdots + 2x_6 + x_7 = N$$ $$x_1,x_2,\ldots,x_7 \ge 1$$ I just thought that I should reduce this a bit more, so I ...
0
votes
0answers
23 views

Tilde approximation for $\frac{N^{100}}{2^N}$?

I am having some trouble getting the tilde approximation for a computer algorithms class. Here is what I have so far: $\frac{N^{100}}{2^N} \rightarrow \lg\left(\frac{N^{100}}{2^N}\right) = ...
0
votes
0answers
8 views

Computationaly Simulating Brownian motion and entry times in sets

What would be some good books to help me program Brownian motion? I want to simulate Brownian paths in a bounded domain and ,ideally, get estimates on the hitting probability of sets in that domain. ...
1
vote
1answer
38 views

Limit of a recursive function

I have a recursive functoin: $$\log^{'}(n) = \begin{cases} & 1 \text{ if } n \leqslant 1 \\ & 1 + log^{'}(\log(n))\text{ otherwise} \end{cases}$$ This function grows VERY slowly. Is this ...
1
vote
0answers
76 views

Bounds on Linear Unique Game value

Suppose we have a system of $N$ linear equations in $\mathbb{Z}_n$ of the form $x_i - x_j = c_{ij}$ where the $x_i$ are variables and the $c_{ij}$ are constants. Suppose that at most $M$ of these ...
2
votes
1answer
26 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
2
votes
3answers
95 views

Show that the language is not regular using the pumping lemma.

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma. I have done the following: Let $i \geq 1$ $$x = a^i b^i \in L$$ $$|x| = 2i \geq i $$ ...
1
vote
0answers
22 views

operator vs operation vs function vs procedure vs algorithm

I have a vague understanding of what operator, operation, function, procedure, algorithm mean in general. I am heavily biased towards computer science. Do you agree with them? What are the generally ...
1
vote
1answer
32 views

What's wrong with this “proof” of time complexity? Traversing a $n \times n$ matrix in $O(n)$

Claim: I can traverse an $n \times n$ matrix in $O(n)$. "Proof": Clearly, this is true for $n=1$. Now suppose this is true for $n-1$. Then given an $n \times n$ matrix, traverse the upper left ...
2
votes
1answer
29 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
3
votes
0answers
32 views

The Basic Example and Output of Algorithms [closed]

if exg(x,y) swap the x,y, and array A contains integer numbers, the following algorithm how modify the $A[1]$ and what is the operation of the following algorithm? i confused to trace this code. any ...
2
votes
1answer
28 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
3
votes
0answers
51 views

Increasing Growth Rate Challenge [closed]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
2
votes
1answer
274 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
-2
votes
1answer
35 views

FA that accepts only those words that have an even number of substrings cdc?

I take this question as it could accept cdccdc,cdccdccdccdc,dddcdccdc,etc. I feel that I coveed all the even loops of cdccdc but I am stuck trying to figure out how to add in c* and d* in the mix of ...
2
votes
0answers
35 views

Add two a,b bits number Algorithm

Suppose we want add two numbers that has a and b bits. we do such operation in O(max{a,b}). we want to add n, 1 bit numbers (0 or 1). what is the best and worst case of this algorithm? i ran into ...
4
votes
0answers
40 views

One Simple Code and Problem on Running [closed]

My Stackexchange friends, would you please show the following code how manipulate the n-elements array A?
1
vote
1answer
21 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
0
votes
0answers
13 views

Scheduling Algorithm for a multi-server queue problem

I have 4 servers, n customers and m reports. At any time, a customer may request one of m reports. There are only 4 servers which are capable of generating reports. Each server can only process one ...
2
votes
1answer
37 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
1
vote
0answers
40 views

Describe in English the pattern in the following regular expressions [migrated]

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
4
votes
0answers
51 views

local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
16
votes
1answer
316 views

Mathematics of Torrenting

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
0
votes
1answer
26 views

Tarjan's algorithm to determine wheter a directed graph has a cycle

I want to know if a directed graph has a cycle; something like 1->2->3->2 ... 1->2->3->4->3... 1->1->1->1... So, I'm considering ...
3
votes
1answer
17 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
1
vote
1answer
32 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
1
vote
2answers
420 views

shadow simulation from buildings

is it possible to calculate shadow areas of buildings or simulate shadows of buildings in a city, using the heights of these buildings and the sun angle and azimuth? the basic light tracing concept ...
0
votes
0answers
21 views

Seam Carving - Energy functions. How do they work?

I have been taking an interesting in dynamic programming and more specifically Seam Carving. For those who are not aware what this is, please look here and for some more detailed information here. If ...
4
votes
1answer
46 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
0
votes
0answers
23 views

Help needed for K-nearest neighbor distance metric and distance weight formulas.

I am currently working on K-nearest neighbor algorithm with Distance Weighting. I have read the Distance Metric and the Distance Weighting parts. I want to fully understand how the Distance metric and ...
2
votes
1answer
112 views

Water Box with n Liter

I ran into a basic challenging problem. I see an high school local math Olympiad question. we have a box that keep n Liter water. each time we extract 1/k Water from box. how many times (minimum) we ...