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

1
vote
1answer
16 views

Is there an hamiltonian path on a $4 \times 4$ chessboard

If you have a $4 \times 4$ chessboard: Is it possible to make a Hamiltonian graph such that each step is like a move of the knight?
2
votes
1answer
19 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
1
vote
1answer
28 views

Find minimum number of coins with Largest value coins?

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find ...
6
votes
1answer
463 views

Structural Induction vs Normal (Mathematical) Induction

In computer science and semantics I have come across structural induction many times. In that context, it is often presented as something different from but similar to mathematical induction, ...
8
votes
3answers
9k views
2
votes
1answer
63 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 Wouldn't it would make much more sense if $L^0 = ∅$. ...
0
votes
1answer
11 views

Structural Induction with Propositional Variables

I've been stuck on this question and I'm confused as to how to approach it: Let $G$ be a set defined as follows: if $x$ is a propositional variable, then $x \in G$; if $f_1,f_2 \in G$, ...
0
votes
0answers
38 views

Showing set is undecidable with Turing Machines

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket ...
0
votes
2answers
61 views

Is it possible to have logic without syntax (with only semantic proof methods)?

In one paper I have read a note "Thus, unlike approaches which make use of full first order logic, unprovability of a formulae with respect to a agent specification can be shown by each of two ...
0
votes
0answers
16 views

existence of $\lambda$-term [on hold]

I want to show two things about $\lambda$-terms but I do not really know how to. There is no $\lambda$-term F such that: * FM=I if M contains free variables * FM=K if M contains no free ...
0
votes
1answer
45 views

Using pumping lemma

I'm trying to prove that the language $\mathcal L = \{w \in \{0,1\}^* ∣ w \leq w′ \text{ where }w′ \text{ is any rotation of }w\}$ is not a regular language. Note: The inequality is with respect to ...
0
votes
0answers
13 views

SQL joins and analysis

Say we have a users table and an events table and what sort of analysis can be done? Also, what is some SQL statements to describe the analysis of these 2 tables?
0
votes
1answer
1k views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
1
vote
1answer
496 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
2
votes
2answers
17 views

Comparing the growth of two function by taking logarithms

I was trying to understand how to compare the big-O growth of two functions by taking the logarithm (or some increasing function like $\sqrt{f(n)}$. For example, take $2^{({log_2n})^2}$ vs $ ...
3
votes
1answer
31 views

Inclusion exclusion principle questions i tried(doing it correct?)

$x_1+x_2+x_3\le10$ how many natural numbers solve this problem if $1\le x_1 \\ 2\le x_2 \\3\le x_3$ What i did: i created $y_1,y_2 , y_3$ so $\\ y_1=x_1-1 \\y_2=x_2-2\\ y_3=x_3 -3$ and then added ...
3
votes
1answer
59 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
0
votes
0answers
28 views

Looking for mathematical/combinatorial and computational explanation regarding adding values in a $5 \times 4$ (matrix?) with a constraint.

Given the following matrix (not sure if I should call it that): Matrix $5 \times 4$ I want to add all possible combinations of values such that each Horse gets but one value from each Bookie. What I ...
1
vote
2answers
69 views

Should non mathematicians learn mathematics “just in time” or ahead of time? [on hold]

I am wondering how someone that is not exclusively interested in mathematics (but nevertheless aims to become a decent applied mathematician), but for example, a theoretical computer scientist, should ...
1
vote
0answers
22 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
1
vote
1answer
513 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
-1
votes
2answers
33 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: $$ ( a + b )^* a ( a + b )^* b( a + b )^* = (a + b)^* ab(a + b)^* $$ I can "see" why they are equal to ...
-1
votes
1answer
16 views

Signed binary number [closed]

What is the range of number that can be represented by a 16 bit signed binary numbers ? How many are negative and positive numbers ? Thanks.
0
votes
1answer
24 views

Convert hexadecimal to binary scientific notation using IEEE 754 single-precision floating point

I am trying to convert these numbers to binary scientific notation, but I cannot figure out the process. Could someone please the process of going about solving this? For IEEE 754 single precision ...
0
votes
1answer
13 views

Simplify Conjunctive Normal Form?

is there any kind of general rules to follow or algorithm for trying to simplify something in conjunctive normal form? Specifically, I'm trying: (P or Q) and P and (Q or R) and (P or notP or R) and ...
1
vote
2answers
49 views

Is there a way to prove that a Turing machine computes the function we designed it to?

Say we design a simple Turing machine that adds two numbers together. Is there any way to formally prove that the machine actually computes the function we 'know' it does? Is there a general method ...
1
vote
0answers
31 views

In a floating number system, are there always as many numbers between 0 and 1 as between 1 and $\infty$.

The question is as the following, where $\beta$ is the base, $t$ is precision (length of decimals), $e_{\min}$ is the minimum exponent, and $e_{\max}$ is the maximum exponent. I am not sure, ...
0
votes
1answer
643 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
13
votes
0answers
88 views

Is there an efficient algorithm for this vertex cycle cover problem? [migrated]

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
0
votes
1answer
27 views

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free I am trying to prove it without to build a pushdown automaton First I tried to look which words are in $\mathcal L$, ...
0
votes
2answers
31 views

Whats bigger? lim n->infinity n^x or lim n->infinity x^n

What is bigger? lim n->infinity n^x or lim n->infinity x^n I have a relationship where I am trying to find the lim n->infinity (2^n + n^20) / 3^n and am having a hard time deciphering it.
2
votes
1answer
50 views

Converting programming logic to mathematical notation

How do I go about converting programming logic to mathematic notation? For example, I read a question that asks: ...
1
vote
0answers
36 views

Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
0
votes
0answers
37 views

Algorithm For Honest vs. Dishonest People

Consider a group of people. When two are taken and asked if the other is honest, they may each either reply that the other is honest, dishonest, or they may report that one is honest and the other is ...
0
votes
0answers
14 views

Cannot open Singular in a running emacs [closed]

I am a newbies in Singular. I just downloaded Singular4-0-2_64.dmg, mounted the image, right-ckick, show the package contents, then moved the contents folder to the Applications directory. ...
1
vote
0answers
61 views

How to find $1^k+2^k+…+n^k$?

I know how to come up with $F(n, k) = \sum \limits_{p=1}^n p^k$ recursively knowing $F(n, k-1)$. But what if I want to find it in a very short time? I know how to find fast $f_n = ...
2
votes
1answer
12 views

Savitch theorem and its assumption

famous Savitch theorem states: For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$ Why we need an assumption that $f\in\Omega(\log(n))$? Thank ...
2
votes
0answers
31 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
1
vote
1answer
1k views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
0
votes
1answer
24 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
0
votes
1answer
554 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
0
votes
1answer
34 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
1answer
32 views

Find the equation of a non-linear relation given 2 points

So I ask my question, let me just begin by stating that I'm in grade 9, and have decided to start learning calculus to aid me in the development of an undisclosed project that I am working on. Now, ...
-1
votes
2answers
44 views

$f(x) \geq g(x) \Leftarrow \lim_{x \rightarrow \infty}\frac{g(x)}{f(x)}=0 $?

I want to know if function $f(x)$ is greater or equal than $g(x)$. If I prove that $\lim_{x \rightarrow \infty}\frac{g(x)}{f(x)}=0$ then is it so?
0
votes
0answers
17 views

Hypercontractivity Lemma

In the proof of the Hypercontractivity Lemma here http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture13.pdf (3.4) what does it mean to split $p$ into $r + x_n*s$, why can we do this?
1
vote
1answer
40 views

Proving L is regular or not using pumping lemma

So I'm trying to prove that the language L = {$1^n$ | n is composite} is either regular or non-regular using the pumping lemma. I wanted to ask if I'm on the right track. So I assume that L is ...
0
votes
1answer
28 views

Geometric Meaning behind the algorithm (slope of the line + ray casting)

I'm trying to dissect the classic algorithm for finding if a point is inside a (simple) polygon. Please see: http://erich.realtimerendering.com/ptinpoly/ and ...
0
votes
0answers
9 views

What is the complexity of the arithmetic operations in base $b$?

Fix a number $n$. We want an algorithm which takes a positive integer $x$, represented as a base $b$ string, and outputs the base $b$ representation of $nx$. Note that if $n$ is a power of $b$, there ...
2
votes
3answers
10k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...
31
votes
8answers
4k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...