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
3answers
31 views

Performing matrix chain multiplication by hand

I'm trying to gain intuition for writing a matrix chain multiplication algorithm by working through a few problems by hand. I see plenty of worked-through solutions on sets of three or four solutions, ...
0
votes
2answers
29 views

Does a System to Automatically (Mathematically) Generate Arbitrary Computer Programs Really Exist?

Has anyone actually developed a Program Synthesis system for creating computer programs automatically from a non-procedural specification that is taken from a fairly robust system of specifications? ...
2
votes
0answers
25 views

Chaitin's constant for lambda calculus and combinatory logic

I have found some approximations of Chaitin's Constant for turing machines but I have not found approximations for others. I'd like to have a rough estimate or upper bound on it for lambda calculus ...
0
votes
0answers
25 views

How can I understand 3d matrix coordinates in computer science

I know calculus but I have never ever touched on matrix...so I am always clueless. I get how you can multiply 2 matrices..but what you are getting even has mathematical significance is a mystery to ...
2
votes
2answers
65 views

Lower bounding the number of children in branching process

Suppose we have a recursive branching process where the number of children is given by $n p$ for parameters $n$ and (probability) $p$. Each child branches $n p$ children (once) and these children ...
10
votes
1answer
243 views

Fast inverse square root trick

I found what appears to be an intriguing method for calculating $$\frac{1}{\sqrt x}$$ extremely fast on this website, with more explanation here. However, the computer-science lingo and ...
1
vote
0answers
49 views

Implement A Function

Group $G = Z_p^*$ Where $p$ is the order of $G$. $e$ is a funtion $e : G \times G \to G $ such that: (Bilinear) For all $P,Q \in G$, for all $a,b \in Z$, $e(P^a,Q^b) = e(P,Q)^{ab}$. (Non-degenerate) ...
1
vote
0answers
25 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
1answer
35 views

What is the formula for this pattern?

I'm trying to find some sort of inverse relationship between two variables. I am working on some parallax scrolling in my iPhone app and I'd like to see if someone can help me find the formula for ...
0
votes
1answer
33 views

How to correctly calculate the fractal dimension of a finite set of points?

The box-counting dimension is defined by: $\lim\limits_{\epsilon \to 0} \dfrac{N(\epsilon)}{1/ \epsilon}$ What works well if you are solving algebraically or if you can recursively generate more ...
1
vote
2answers
86 views

Discrete Mathematics books for Computer Science Self-study

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
1
vote
2answers
23 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
1answer
25 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
2
votes
2answers
51 views

Asymptotic approximation of binomial theorem

Binomial theorem is a very popular theorem that: $$(x + y) ^ n = \sum_{i=0}^n {n \choose i}x^i y^{n-i}$$ I am looking for any papers (the newer the better) where I can find any informations about ...
1
vote
3answers
33 views

Generate numbers that add up to X

I have isolated the algorithm of a keygenme, but I am running into difficulty with creating the keygen. The key has a length of seven digits, and the sum of each of the digits in the key must be ...
0
votes
1answer
29 views

Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
0
votes
1answer
46 views

Practical differences between a PRNG and a Markov chains

In computer programming you can easily find people describing both a PRNG, like a Mersenne Twister, and a Markov / Stochastic process as "pseudo random generators". I honestly never liked this ...
1
vote
2answers
60 views

Need help on books on diff. equations/geometry and theoretical computer science

I am looking for recommendation of 3 different books on the following topics: 1.Differential Equations -Ordinary diff. equations -Vector field, transport equations -Equation of wave and heat -Use ...
0
votes
0answers
14 views

Translation of a Hamiltonian cycle to a boolean expression

I was wondering how you would go about doing this. For example: Translate the graph, which has a Hamiltonian cycle, into a boolean expression. The graph looks like a triangle where each corner is a ...
-1
votes
1answer
19 views

Universal way to convert from one base to another

Is there a universal way to convert from one base to another? I know how to convert numbers with any base to decimal form. i.e., with $\sum_{i=0}^{n-1} r^{i}d_i$. However I don't know any universal ...
2
votes
2answers
46 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
3
votes
0answers
76 views

A problem on 0-1 matrices.

Given a 0-1 matrix $A$, is there an efficient way to find all 0-1 vectors $x$ such that $Ax = v$ where the entries of $v$ belong to a set $\{a,b\} \subseteq \mathbb{Z}$ of size $2$? Note that $v$ is ...
2
votes
1answer
19 views

Checking if a graph is bipartite is $O(n)$

It seems to me that checking if a graph is bipartite (or biclique) has deterministic time complexity $O(n)$, where $n=|V|^2$, since we clearly have to iterate over all the elements of the incidence ...
1
vote
1answer
63 views

Proof that Newton Raphson method has quadratic convergence

I've googled this and I've seen different types of proofs but they all use notations that I don't understand. But first of all, I need to understand what quadratic convergence means, I read that it ...
0
votes
0answers
47 views

Calculate the Probability for Binary Matrix

Consider a binary matrix of dimension $m\times n$. Suppose the probability of occurrence of 1 is $p$ in any row of the matrix. Each row of the matrix is independent to each other. The all possible ...
2
votes
1answer
62 views

Getting interested in mathematics again after I finished Computer Science program.

So, I finished Computer Science study about 3 years ago (I'm 28 now) and lately I've been craving math. As a daily job I work for a start up company building a web application. I mostly done web apps ...
1
vote
1answer
99 views

Is NP countable?

Is NP countable? I am confused with this problem. I think it is not countable but I am not sure. Can someone prove whether it is countable? Please show your proof. Thank you for your time!
1
vote
1answer
29 views

AND using XOR and OR?

Is there a way to make an AND using only XOR and OR. I know that a XOR b = ab'+ba' but I have no idea how to proceed. Could it be impossible?
-2
votes
1answer
84 views

If P = NP, how would this allow us to cure diseases? [closed]

I have read a number articles on what the real-world ramifications would be if P = NP. One of these ramifications that is often repeated is that we 'could cure all sorts of diseases'. How or why ...
1
vote
1answer
49 views

Confused on how an equation is reached from Concrete Mathematics

I'm reading Concrete Mathematics and trying to understand some of the equations. In particular how the author arrives to a particular solution. Given: $$L_n = \frac{n(n+1)}{2} + 1$$ the author ...
1
vote
1answer
65 views

Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
0
votes
0answers
84 views

Function acting on a graph

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows: Given a graph $G= \langle V_G, E_G ...
1
vote
2answers
53 views

How to make a Truth Table and turn Truth table into A Circuit.

Background I'm a novice student learning some mathematics (Programming background) and I'm currently learning how to construct Truth Tables from Logical Statements and then use that Truth Table to ...
1
vote
0answers
52 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
2
votes
0answers
41 views

How to represent an algebraic number in algorithm

I'm studying the problem of computing $n$th digit of given (irrational) algebraic number. Is there some canonical way to represent an algebraic number as a string I could use in computing? Basically ...
0
votes
1answer
25 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
1
vote
1answer
50 views

Semantic consequence

I'm studying refutation trees in computer science II, but I have a big doubt: Let $\Gamma, \Psi \subseteq F_m$ Is the following hypothesis true? $\Gamma \vDash \Psi \iff \not\vDash\{\Gamma,\lnot ...
1
vote
1answer
42 views

Given a set $S$, find any $N$ numbers than sum to $X$

Similar but different from the problem here. I have an unsorted set $S$ of real numbers, and need to sum elements from $S$ to find the real number $X$; However, It could be from $1$ to $N$ elements ...
1
vote
0answers
34 views

Tools (electronic notebook and ontology viewer) of mathematical formulas (definitions and facts)

I am reading math books and articles (for applications in other disciplines, mostly about logics for computer science and AI) and the hardest part is to memorize formulas, to look up some ...
0
votes
1answer
32 views

Number of $n$-bit strings that contain from none to $n/2$ zeroes

This is a problem that revolves around symmetry. I recognize that if there is a 4-bit string that it will have 1110 as an answer, but it will also have 0111 as an answer. The thing is, I'm not sure ...
2
votes
1answer
79 views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
0
votes
2answers
35 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
0
votes
1answer
38 views

turing machine accept and reject state

I am pretty new to Turing Machines and I am trying to understand the basic things first...so my question is , would this machine accept all words ending in 'a' ? if ...
0
votes
1answer
23 views

Strong one-way functions: a remark on the definition

Notation: $\Sigma^k$ is the set of $k$-strings on the alphabet $\Sigma$; $\Sigma^\ast$ is the set of all finite dimensional strings on the alphabet $\Sigma$. In the context of computer-science a ...
1
vote
1answer
44 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
0
votes
0answers
20 views

Show L1 is in P, given that L2 is in P and L1 <=p L2

Given L1 and L2 are languages over alphabet Z. Also given that L1 <=p (polynomial time computable) L2 and L2 in P. What is the best way to show that L1 is in P (through definitions of class P and ...
1
vote
1answer
26 views

having hard time reading symbols in this Turing Machine

I am reading few books and I am looking at different examples of a Turing Machine, and I am getting frustrated reading symbols especially in this example...What does ...
0
votes
0answers
50 views

how do I make this post machine accept aab or baa?

so far I made it accept, a, aaa,bab but now I want strings aab or baa. How would I do this ? this is what I have so far... edit: @Hagen von Eitzen here is the example of Post Machine that a lot of ...
0
votes
2answers
23 views

Why cant this be a Regular Language?

Given L - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$ How can I prove that L is not a regular language?
0
votes
2answers
12 views

Linear search average-case complexity?

I am trying to find the average case complexity of the linear search. I know the answer is O(n), but is this correct: The first element has probability $1/n$ and requires 1 comparison; the second ...