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

2
votes
0answers
33 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
21 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
1answer
21 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
264 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
34 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
9 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
39 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
100 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
129 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
31 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
37 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.
4
votes
0answers
35 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
32 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
52 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 ...
5
votes
0answers
44 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?
2
votes
1answer
24 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
4
votes
0answers
54 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
18 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 ...
4
votes
0answers
47 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 ...
2
votes
1answer
46 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
79 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
58 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
36 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 ...
4
votes
1answer
25 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 ...
5
votes
2answers
61 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
23 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 ...
6
votes
1answer
52 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 ...
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 ...
0
votes
0answers
33 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 ...
3
votes
1answer
30 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. ...
3
votes
1answer
50 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.
2
votes
0answers
34 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.
10
votes
1answer
95 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
31 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 ...
0
votes
0answers
31 views

Smallest grammar problem on a single character.

Let the alphabet be $\Sigma = \{a\}$. Say $s = a^6 = aaa aaa$. If the repeated variable $A = aa$ appears $k$ times in the expanded starting rule of a smallest grammar $G_s$ for $s$. Then that ...
-1
votes
2answers
26 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$ ...
4
votes
3answers
94 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 ...
1
vote
1answer
26 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
0answers
13 views

fuzzy computation

I am completely new to fuzzy set theory and fuzzy logic and maybe i am way off the subject, but I was wondering about the following. Suppose i have a statement: "X is about the same as Y and equal ...
2
votes
1answer
33 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$ ...
5
votes
1answer
55 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
57 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
44 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
85 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
42 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
96 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.
2
votes
1answer
50 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
48 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
44 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: ...