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

0
votes
1answer
22 views

What mathematical structure best entails self-modifying programs?

If a program description can be represented as a sequence, then what is the best structure to entail program descriptions which self-modify? There must exist a relationship between the structure in ...
1
vote
1answer
23 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
0
votes
0answers
37 views

Proving that there always exists two opposite points on a circle where the temperature difference is less than 1

You are given $n$ ($n$ is even) integers $a_0,a_1,\ldots,a_{n-1}$ representing temperature measurements, equally spaced around a circle. Since the points are "close", the temperature difference ...
1
vote
0answers
13 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
2
votes
1answer
33 views

Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
0
votes
1answer
15 views

In the loop average computation

I want to compute the average of a set of number, which is constantly increasing. I guess it's simple, but I'm struggling here: Let's say: 1st iteration: m(i)=a+b/2 2nd iteration: m(i+1)=a+b+c/3 ...
0
votes
1answer
37 views

Trouble reading mathematical statements. Need to know I'm on the right track.

Σ = {a, b}. We write #a(x) for the number of occurrences of the letter a in the word x and similarly for #b. note: $\Sigma^*$ refers to the set of all finite strings (words) over Σ. ...
0
votes
1answer
54 views

What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
-1
votes
0answers
21 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)$$ when X y Y have the same distribution. In particular, is it larger or smaller than the entropy of the sum of two ...
0
votes
1answer
37 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 ...
0
votes
0answers
6 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
55 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 ...
2
votes
1answer
47 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 ...
-1
votes
0answers
28 views

An Advice Concerning Master's Programme [closed]

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
25 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?
2
votes
1answer
29 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 ...
1
vote
2answers
23 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
33 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
16 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
257 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 ...
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 ...
2
votes
3answers
96 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 $$ ...
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 ...
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
30 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.
-2
votes
1answer
36 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 ...
4
votes
0answers
41 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 ?
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?
0
votes
0answers
14 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
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 ...
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 ...
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
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 ...
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$ ...
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
19 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 ...
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 ...