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

2
votes
2answers
14 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 $ ...
0
votes
0answers
17 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 ...
0
votes
1answer
27 views

Using pumping lemma

I'm trying to prove that the language $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 ...
1
vote
0answers
17 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 ...
3
votes
1answer
24 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 ...
1
vote
2answers
66 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
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 [on hold]

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
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
48 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 ...
0
votes
1answer
47 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
1answer
23 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 ...
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
2answers
30 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
49 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
33 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
60 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 ...
0
votes
1answer
31 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
0answers
16 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
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?
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 ...
3
votes
1answer
55 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 ...
1
vote
2answers
23 views

Time Complexity Calculation

I'm currently working a few exam question, and got stuck at this point. I am given that a Quicksort algorithm has a time complexity of $O(nlog(n))$. For a particular input size, the time to sort the ...
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, ...
0
votes
1answer
59 views

Evaluate truth value of formula

I am not sure about this question? Domain = {1, 2} Assignment of constants: a = 1 and b = 2 Assignment of functions: f(1) = 2 and f(2) = 1 Assignment for predicate P: P(1, 1) = T; P(1, 2) = T; ...
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
78 views

Function such that $f(a, b) = c$, but even if I knew $c$ and $b$ I cannot (practically) find $a$? [closed]

I need a function where $f(a, b) = c$. a,b,c are all positive integers. But even if you knew $b$ and $c$ you cannot practically discover $a$ or narrow $a$ down to fewer than ~1 billion ...
2
votes
2answers
42 views

Solving for the positions of vertices of 3 line segments

I have 3 line segments of lengths p,q,r joined at their ends. Let's call the vertices A, B, C, and D. Suppose D is fixed at the origin. Suppose that A is constrained to move only in the Y direction. ...
0
votes
1answer
16 views

an array A[1..N] how many indexes (i,j) are there such that cumulative sum(i,j)%K = 0?

Lets say I have an array A[x1,x2,x3,...xN] of size N. for N = 4 , A = {x1,x2,x3,x4}. [1 based index] Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is ...
0
votes
1answer
22 views

Help solve a computational complexity problem

Find the tight computational time ($\Theta$ notation) complexity of the following function Of course an exact solution is $\sum\limits_{i = 1}^{3{n^3}} {\frac{{2{n^3}}}{i}} $, but I am not able to ...
0
votes
2answers
31 views

RSA Encryption Original Primes $p$ and $q$

I am well aware of the math behind the RSA encryption system, and why it works. The bank, for example, publishes a pair of numbers $(e,n)$ which are used for encryption by the customers. The bank then ...
1
vote
0answers
31 views

How to resolve this computability paradox?

Let's define two Turing machines, $T_1$ and $T_2$, as follows: Given a number $n$ as input, let $T_1$ be a Turing machine that enumerates over all pairs $(p,s)$ where $p$ is the code of some Turing ...
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
40 views

How do I use L'Hopital's rule to determine if $\log^kN$ is $o(N)$ for any constant $k$?

How do I apply L'Hopital's rule to see if $\log^kN$ is $o(N)$ (small $o$) for any constant $k$? I understand I should keep finding the derivatives of both functions and stop if I can clearly identify ...
1
vote
1answer
56 views

How to encode a list of integers, how to find an arithmetical formula for a sequence?

I have the following list of integers : $$t={0, 15, 73, 27, 73, 105, 25, 65, 26, 8, 84, 72, 15, 73, 27, 73, 105, 25, 65}$$ And I want to find a function or (an expression) such that $f(k)$ is always ...
1
vote
0answers
21 views

If $T$ is a set, $P(x)$ denotes x is a hard worker and $D(x)$ denotes that $x$ is a worker, how to translate the following to English sentence?

So $T$ is a set of workers and materials in a tower, $P(x)$ denotes that $x$ is a hard worker and $D(x)$ denotes that $x$ is a worker $\forall x \in T: [D(x) \rightarrow [\exists y \in T: P(y)]]$ ...
0
votes
1answer
16 views

String recursive definition corner case

I need your assistance with a corner case of this problem: Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}. I've ...
1
vote
1answer
28 views

Converting an NFA to a DFA

I am trying to convert this NFA to DFA: So I built the power automata, and this is what I got: This should be the answer: I don't understand where am I wrong since ...
0
votes
0answers
29 views

recursively enumerable sets closed under concatenation

I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I ...
2
votes
0answers
66 views

How to generalize “Seven trees in one” to labelled/colored trees?

In the famous paper Seven trees in one, Andreas Blass showed that there is "a particularly elementary bijection between the set $T$ of finite binary trees and the set $T^7$ of seven-tuples of such ...
0
votes
1answer
23 views

Big-O complexity of $2t(\frac{n}{2}) + n^3$

I'm trying to determine the Big-O complexity of the listed equation and want to know if my approach is valid. I tried using the Master method. It appears to be a case $3$ type problem to me, where ...
0
votes
0answers
25 views

Statistical Analysis of an AI Solving Raven's Progressive Matrices

I need to build an artificial intelligence capable of solving some simple Raven's Progressive Matrices. The gist of it is that you are given an analogy "A is to B as C is to blank" and numerous ...
0
votes
1answer
12 views

K-Map multiple representations

I have a K-Map for a given function and need to figure out the minimal form. This map involves don't-cares. My question is: Do I need to use the don't-cares in my minimal form. I will show you why I ...
0
votes
1answer
20 views

Induction on String? (automata related)

Honestly, all I know about mathematical induction is as follow: prove $P(0)$ - base step for all $n \ge 1$, prove $(P(n − 1) \rightarrow P(n))$ - inductive step Prove the following claim by ...