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
2answers
34 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
12 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
0answers
15 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 ...
1
vote
0answers
29 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
641 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
25 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
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
48 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
30 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
34 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 [on hold]

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
59 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
551 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
28 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
30 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
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
vote
1answer
31 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 ...
2
votes
1answer
43 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 ...
2
votes
3answers
2k views

An algorithm to convert float number to binary representation

I want to know the algorithm of converting a given float (e.g, 3.14) to binary in the memory. I read this wikipedia page, but it only mentions about the conversion the other way. Let me quickly give ...
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$? [on hold]

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 ...
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; ...
-3
votes
0answers
28 views

Recurrence / recursion [closed]

How to solve: A function F(n) satisfies the recurrence F(n) ≤ 4F(bn/2c) + n for all n ∈ N. Give an upper bound for F(n).
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 ...
2
votes
2answers
41 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. ...
6
votes
2answers
8k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
1
vote
0answers
17 views

Finding objects from a list with some properties in $O(n)$

Lets say I have $2$ strings each having $4$ characters. $k$ is a number $\le 4$. If, $2$ strings have exactly $k$ common characters lets say they are a "happy pair" with $k$ points. If I have $n$ ...
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
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 ...
0
votes
2answers
29 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 ...
0
votes
1answer
22 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 ...
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
2answers
2k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
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 ...
0
votes
2answers
39 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
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
4answers
106 views

Books recommendation on Graph Theory (Beginner level)

What are some of the best books on graph theory, particularly for the beginners. Thank you.
1
vote
1answer
27 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
28 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 ...
0
votes
1answer
38 views

Sum-of-products for a function

I am not quite sure if I am understanding this correctly or not. Here is the problem: "Find the simplest sum-of-products form for the function $f$ using the don't-care condition $d$, where $f = ...