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

3
votes
0answers
51 views

Examples of calculus on “strange” spaces

I am interested in examples of calculus on "strange" spaces. For example, you can take the derivative of a regular expression[1][2]. Also the concept extends past regular languages, to more general ...
0
votes
1answer
6 views

Increasing order of fourier coefficients on the boolean cube

Given a function $f:\{0,1\}^n\rightarrow \{0,1\}$, is it true that for any $S,T\subseteq[n]$, such that $S\cap T =\phi$, then $\hat{f}(S\cup T)\leq \hat{f}(S)$? It seems so to me cause, if if you just ...
2
votes
1answer
51 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
0
votes
1answer
65 views

Construct grammar $\ a^i b^j c^{i+j} b^j a^i $

I've been going through old exams at my college and I found this problem that I haven't yet been able to solve. Construct grammar defined on the alphabet $\ \{{a, b, c}\} $ which generates strings of ...
0
votes
1answer
23 views

How to compute sine function within certain precision

I know that there exists CORDIC algorithm, but CORDIC algorithm contains component $\arctan 2^{-i}$, which needs to be looked up. I do not know how this leads to the precision that is advertised by ...
3
votes
0answers
19 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
0
votes
0answers
16 views

FFT differential equations

Given a generical differential equation what is the procedure to solve it using fft command. Can anyone explain me how to do it? For example: $$\frac{d^2y}{dt^2}+10\cdot \frac{d\:y}{dt}=-5\cdot ...
1
vote
1answer
66 views

Python Integer Game

Jacob and Vicky play the fun game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Jacob always starts with p = 1, does his multiplication, then Vicky multiplies the number, ...
1
vote
0answers
35 views

Maxima CAS and programmatically defining a function with a variable number of arguments. -?

This is a very simplified question of what I had asked. In Maxima, how can I include a for-loop counter in the left-hand side of an assignment, e.g. ...
1
vote
1answer
35 views

error bound in function approximation algorithm

Suppose we have the set of floating point number with "m" bit mantissa and "e" bits for exponent. Suppose more over we want to approximate a function "f". From the theory we know that usually a ...
2
votes
1answer
40 views

Understanding difference between reduction methods

In Sipser's book "Introduction to the theory of computation" there are 2 methods for proving that $\rm HALT_{TM}$ is undecidable by a reduction from $\rm A_{TM}$ I am trying to figure out the ...
2
votes
3answers
134 views

which branch of computer science is most math intensive? [closed]

I am planning for a Master degree study, my major in college is computer science, but I also like math. I want to know which branch of computer science uses most math, not only discrete math, but also ...
0
votes
1answer
19 views

About Newman and Girvan definition of Modularity of Network-Community

Can some body explain me the following statement about Community Structure in a Graph : Newman and Girvan write: „In a network in which edges fall between vertices without regard for the communities ...
1
vote
0answers
22 views

periodic boundary conditions and the FEM

I am trying to set up the mass matrix for a 1D system which I want to solve using finite elements. So the mass matrix is defined as $$ M = \int{NN^T}dL, $$ where $N$ is the finite element linear ...
1
vote
1answer
69 views

How many non decreasing sequence of length k is possible?

If we have a set like this { 1A ,2A ,2B, 3A, 3B, 3C}, how many non decreasing sequence is possible, such that number in left is less than number in right of length k? i.e, Length = 2 then the ...
0
votes
0answers
20 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
2
votes
0answers
27 views

Stuck in a Context-Free Proof

I am trying to work through the pumping lemma for CFLs. $L_1 = \{0^n 1^{mn} : n,m \in \Bbb N\}$ I am trying to find a contradiction. I have currently chosen $z= 0^p1^{2p}$ to be my string. Then ...
0
votes
0answers
19 views

Cost of an algorithm or an operation

In my notes there is the following: $G$: finite abelian group If $|G|=m$ elements we need $\lfloor \log_2 m \rfloor+1$ digits to represent all the elemets of the group. For example, ...
0
votes
0answers
17 views

How to compute the logarithm of a computable number

Let's say you have a computable number $x>0$. $\ln(x)$ is computable as well. Given the computability of $x$, what is a computation for $\ln(x)$. I am using the definition where $a$ is computable ...
0
votes
1answer
25 views

Calculating an Intensity Centroid

I am trying to understand the theory behind calculating an Intensity Centroid (image processing), in particular defining moments. As defined by Rosin 1: $m_{pq}=\underset{x,y}{\Sigma}x^py^qI(x,y)$ ...
0
votes
1answer
72 views

Computability problems — can't solve

I have a pair of exercises I can't solve (tomorrow I'll have a test). I need some kind of solution so I can apply it to other exercises...thanks to all! In the following $W_n$ means the domain of the ...
1
vote
0answers
10 views

is the suggested PDA correct?

so i have this language $$ L = \{x^{i} v^{j} z^{j+2} w^{k} v^{i+k} | i,j,k \ge 0 \}$$ i made this PDA for it . states $ = \{q_0 ... q_5 , final\} $ alphabet $= \{ x,v,z,w \}$ stack ...
0
votes
1answer
50 views

Fractional Knapsack- explanation

The following algorithm is given: ...
0
votes
1answer
223 views

Basic idea of proof

I am trying to understand the proof that the expected running time of quicksort is $O(n \log n)$. Could you maybe explain me the basic idea? I am confused right now. EDIT: Suppose that we use the ...
4
votes
2answers
111 views

Help with deriving an absolute strategy (very fun if anything)

My friend and I are trying to figure out a solution or even a best path to figuring out a certain win strategy to this game. This game that my friend made, calling it the number game for short, is ...
0
votes
0answers
11 views

Prove that $ALL_{CFG}$ is undecidable by reducing from PCP

I'm studying for a Computability exam that I have in a few weeks, and have come across this question which I'm having a hard time solving: Prove that $ALL_{CFG}=\left\{ \left\langle ...
0
votes
1answer
19 views

Time complexity function

I'm not sure I should post this on the Mathematics website or the Computer science website of Stack Exchange. If I'm wrong I will replace my question. So I'm trying to calculate the time complexity ...
0
votes
0answers
31 views

Bitwise Operations and the Naming Convention of their Operators

So I just recently came across a bitwise operation on StackOverflow which shifts the bits in a binary number to the right while zero-filling from the left. The left side zero-filling overwrites the ...
1
vote
2answers
41 views

Alternate plain English algorithm for Towers of Hanoi

There are four plain English algorithms for the Towers of Hanoi Puzzle available on Wikipedia, but when I was first solving the puzzle, I came up with an algorithm that is different from any of the ...
2
votes
0answers
40 views

Neighbor-full partition of $\{0,1\}^n$

What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$) We say $A$ and $B$ are neighbors if their ...
0
votes
0answers
30 views

Clique Percolation Method calculation

According to Clique Percolation Method as shown in Wikipedia I could not understand why the result of Graph1 is Graph2 if we assign k to be=2, According to the definition of CPM, then the cluster ...
4
votes
3answers
63 views

WolframAlpha has a different answer for a definite integral, why?

So I ran into this contradiction and I'd appreciate if someone could help explain what is happening: So when i perform the following integral on paper: $$\int_{-1}^1(\sqrt[3]{x} -2)\;dx \; = [\frac ...
2
votes
1answer
48 views

How to understand or derive the formula $Mantissa$ $bits$ $/$ ${log_2}$ $10$ = $Decimal$ $digits$ $of$ $precision$?

I asked a question a couple days ago about floating point precision on stackoverflow called, "Is floating point precision mutable or invariant?" and I received the following response. The formula ...
2
votes
1answer
29 views

pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
0
votes
1answer
37 views

Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
1
vote
0answers
33 views

Formal (Mathematical) Definition of N-Clan?

I tried many times to find a formal definition for the following important concepts in Graph Theory and Network Analysis: 1) N-Clique. 2) N-Clan. 3) K-Plex. 4) K-Core. Reference , but ...
1
vote
0answers
9 views

What is the maximal possible 'non-empty' K-Core of a Graph G

Since any graph can be extracted to find K-Core easily, since finding K-Core is Pronominal problem, what is the maximal possible 'non-empty' K-Core of a Graph G. Is it k+1 ? or what exactly ?
0
votes
1answer
17 views

Does this component have 2 2-clan and also 2 2-clique

I have done many examples with n-Clan and also with n-Clique, but I found an example online as shown in the figure bellow, it says there is only 1 2-Clan and also 1 2-Clique, nevertheless I think it ...
3
votes
1answer
26 views

Pumping Lemma for CGF question

I'm going through a pumping lemma for a proof that: the language $B = \{a^nb^nc^n \mid n\ge 0\}$ is not context free The first case considers when both v and y contain only one type of alphabet ...
3
votes
2answers
99 views

Computing the $n^{\textrm{th}}$ permutation of bits.

I've seen this post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are algorithms to quickly permute the NEXT ...
0
votes
1answer
20 views

Software for computing n-Clique, n-Clan, n-Plex?

I am studying graph theory and complex network into details, I would like to ask if some one could help providing a useful (academic) tools or some good tools for computing n-clique, n-clan, n-core, ...
1
vote
1answer
26 views

K-Clan detection based on a given connected Graph

I have the following definition of the K-Clan: A k-clan is a k-clique where the diameter of the corresponding sub-graph is at most k. and here according to the graph bellow I do not know why 135 is ...
1
vote
0answers
33 views

Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $

Problem Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $ My first idea was this: There can be an "a","b" or a "c" at the beginning of a word Then we ...
1
vote
1answer
49 views

Find regular expression that defines a given language

I want to find a regular expression that defines a language L over the alphabet {0,1} with a following condition: every word contains exactly two 000 substrings. For example, a valid word would be ...
0
votes
1answer
26 views

show how 42.25 would be stored as a floating point number with an 8-bit mantissa and a 4-bit exponent.

So I know that in binary: 42: 00101000 0.25: 01 I then put combine the numbers so it would be: 00101000.01 Once I get this point I'm not sure how to show the mantissa as an 8-bit and the exponent ...
1
vote
1answer
36 views

In formal languages, why is $L^0 = \{ \epsilon \}$? Why isn't it the empty set ∅?

It just doesn't make logical sense to me that a language to the power of $1$, is itself, but to the power of $0$ is only a tiny part of itself (since every language contains $\epsilon$) Wouldn't it ...
2
votes
0answers
36 views

What exactly is wrong with this argument (Lucas-Penrose fallacy)

Argument "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
0
votes
0answers
23 views

Size of remaining search space for Vehicle Routing Problem given a partial solution

The vehicle routing problem is a NP-hard problem that, in its most basic form, involves scheduling routes for v vehicles that have to make n deliveries in total. So a solution (schedule) has the form ...
0
votes
0answers
19 views

Rent's Rule and Modularity?

Rent's Rule http://en.wikipedia.org/wiki/Rent%27s_rule plays a very important role in the engineering of computer circuits, as well as in models of processing (be it of information, be it of brain ...
0
votes
1answer
14 views

Brauer Algorithm [duplicate]

I'm working on a problem and I'm looking at an equation: $lg(n) + (1 + o(1))(lg(n))/(lg(lg(n))$ All I want to know is, what does o(1) mean? Thanks!