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

learn more… | top users | synonyms

0
votes
1answer
90 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} = ...
4
votes
2answers
76 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 ...
1
vote
1answer
68 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
vote
1answer
33 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
72 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
649 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
65 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 ...
2
votes
2answers
103 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
102 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 ...
2
votes
0answers
46 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
22 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 ...
1
vote
1answer
365 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
400 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 ...
2
votes
0answers
29 views

Proof of equality of least fixed point of two continuous function

The question is simple: given a set U, a continuous function (Scott continuity) $f \colon \mathcal{P}(U) \to \mathcal{P}(U)$ and function $g(X) := f(f(X))$, prove that $g$ is continuous and its least ...
0
votes
0answers
493 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) = ...
2
votes
1answer
60 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
125 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
140 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
225 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
47 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 ...
0
votes
1answer
78 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.
-2
votes
1answer
485 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 ...
3
votes
2answers
266 views

Algorithm for adding n 1-bit numbers

suppose adding two numbers, (that first number has a bits and second number has b bits) can be done in ...
0
votes
1answer
267 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
83 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 ...
0
votes
0answers
87 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
282 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 ...
2
votes
1answer
70 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 ...
0
votes
2answers
118 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
1answer
217 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
1answer
123 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 ...
0
votes
1answer
38 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
1answer
72 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
0
votes
0answers
44 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
4
votes
1answer
158 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
1
vote
0answers
70 views

Proof that Finite Turing Machine is reducible to Regular Turing Machine

I know that Finite Turing Machine and Regular Turing Machine are undecidable through Rice's theorem, but I may find a reduction among them? Finite TM = {< M > | L(M) is finite on {a}} Regular TM ...
-1
votes
2answers
29 views

One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
2
votes
3answers
124 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
0
votes
1answer
53 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
0
votes
1answer
50 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
1
vote
1answer
77 views

Queue and Stack in Computer Science and relation to MATH

For Creating a Queue Q we use two Stack S1,S2. for insert x in the end of Q we do Push(S1,x). for deleting element from front of Q, (if Q is not empty) we do Pop(S2). if on Q that at first is empty, ...
0
votes
4answers
176 views

recursive definition odd length strings

Given the alphabet {aaa bbb}, give a recursive definition for the language that only contains odd length strings. must be constructive definition we are suppose to treat aaa as one letter and bbb as ...
0
votes
1answer
52 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
1
vote
2answers
125 views

Do mathematics researchers regularly solve problems like this?

I'm not sure that this is the right exchange for this question. It asks about the possibilities of research in mathematics and computer science. Extended Background I am very interested in ...
0
votes
2answers
116 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
-1
votes
5answers
126 views

How would I show that R is an equivalence relation?

If I were to consider the relation R on ℤ defined by n R m if and only if P(n)=P(m). How would I show that R is an equivalence relation? Any help is appreciated.
1
vote
1answer
60 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
1
vote
1answer
66 views

In lambda calculus, can the parameter of abstraction be a non-variable lambda expression?

In short, my main confusion is between the two concept variable and lambda expression: I am reading this reference here: ...
1
vote
2answers
61 views

Questions about the functions of the operations of a queue

I am looking at the following two functions of two operations of a queue: ...
2
votes
2answers
66 views

Question about queues

A queue is implemented with a sequence $Q[1\ldots n]$ and two indices $\def\head{\operatorname{head}}\head[Q]$ and $\def\end{\operatorname{end}}\end[Q]$ such that the elements of the queue are the ...