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

1
vote
1answer
67 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
49 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
67 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
100 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
87 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
71 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
43 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
44 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
35 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
85 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
39 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
45 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
28 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
24 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
13 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 ...
1
vote
1answer
42 views

Are all polynomial-bounded functions computable? [closed]

Let $f = O(g)$, where $g$ is a polynomial. Then is $f$ computable? Let $K(s)$ be Kolmogorov complexity of a string $s$. It's an incomputable function. No. Let $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = ...
1
vote
2answers
58 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
1
vote
3answers
27 views

How do you reckon Big-O analysis with infinite problem sets?

Let $f : X \to Y$ be a problem, for instance, $f: \Bbb{Z} \to $ a factor. Given input measure $n = |x|$, then our problem is $O(g)$ if there exists an algorithm running on a standard machine, and an ...
0
votes
1answer
17 views

not understanding the part of the answer for drawn turing machine

Could someone please tell me what does capital B mean here ? of course I know R and L stands for right and left... and also I know for example if we have a,b,R (which tells you if you have an a , ...
0
votes
0answers
45 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
0
votes
0answers
37 views

Is the language $L = \{0^m1^n: m \neq n \}$ not context free?

I have been trying to prove that this is not a context free language using the pumping lemma for CFLs. I have tried for hours but am not able to prove it. Is it a context free language or not? How to ...
0
votes
1answer
68 views

Floating Point Number System

I really have no idea of how to do these questions - in fact I have no idea of how to do any question in the paper - but I have tried to figure out what's going on in the course called Computational ...
0
votes
1answer
62 views

how to a draw a turing machine that has the same number of a's ,b's and c's

how to a draw a turing machine that has the same number of a's ,b's and c's SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}
0
votes
1answer
22 views

circuits complexity

I ran into this claim and I dont really understand why it is true ( and I need to use it for proving other things) Every function from $(0, 1)^n$ to $(0, 1)$ is computable by a $2^n10n$-sized ...
1
vote
1answer
35 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la ...
1
vote
3answers
83 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
0
votes
0answers
17 views

Computing Object Classification with bayesian statistics

Say I want to know if there is a zebra $\theta$, in an image $x$. According to Bayes statistics applies to image recognition, I should be computing: ...
1
vote
1answer
38 views

Why we take transpose of Vector (Displacement Vector)?

I'm trying to understand some equations that involves transpose of vectors (displacement vectors to be precise) Two set of vectors F and G (with i,j) that corresponds to X,Y value in plane and ...
-1
votes
1answer
34 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
1
vote
0answers
18 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
1
vote
1answer
28 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
0
votes
1answer
29 views

uniqueness of Maximal Independent Set(MIS)

Is maximal independent set of a graph unique? I think between indepent sets, only one of them is maximal. So does it prove that MIS is unique?
0
votes
1answer
57 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
2
votes
0answers
30 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
1answer
59 views

Convert nested for loop to mathematical expression

Does anyone know how I can convert this nested for loop into a mathematical expression? ...
0
votes
2answers
47 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
45 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
1answer
26 views

create a new formula

I should write a new computer program which includes this computation which I am having trouble with. I may have several cases, ...