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

0
votes
1answer
22 views

How to describe this Context Free Grammar?

I've been having a really difficult time in describing the following Context Free Grammar S → SS | T T → aTb|ab I understand that it must start with an ...
1
vote
3answers
15 views

Help explain this Boolean equation XOR with NOR gates

I'm just starting Boolean algebra and am following an example given in the text that shows the configuration of NOR gates to create an XOR. I cannot follow the algebraic example and would like to have ...
1
vote
2answers
51 views

recurrence algorithms, algebra issues?

So we're given a problem to solve... no other instructions.. the answer is given as well. I am having trouble understanding how this problem is unrolled. I understand that $\sqrt{2^{2^k}}$ can ...
0
votes
2answers
35 views

Finite automata problem

I need to draw a finite automata over the alphabet $\{a,b,c\}$, such that the following properties hold: a word starts with at most two $a$ a $c$ is always followed by an even number of $b$ (0 ...
0
votes
1answer
32 views

Troubles proving $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$

Prove that $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$, knowing that $O[g(n)] = \left\{ f(n) \mid \exists\ c,n_0 > 0\ :\ 0 \leq f(n) \leq c \cdot g(n)\ \forall\ n \geq n_0 \right\}$ I don't ...
-2
votes
1answer
34 views

Importance of Bernoulli Numbers

I'm writing a research paper on the foundations of computing. Supposedly Ada Lovelace wrote an algorithm to find Bernoulli numbers. It sounds cool, but it won't mean anything to my history teacher. ...
0
votes
1answer
18 views

prove this $L$ is not regular?

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$. I want to prove that $L$ is not regular using the Pumping Lemma. So far i assumed by contradiction that $L\in REG$, so it has a pumping ...
1
vote
0answers
20 views

Ensure exact partitioning when performing masked equality comparison

This question arose from an informatics problem, but I do believe Math SE is the right stack to ask because I am not asking for a algorithm in a specific language but for properties to check using ...
0
votes
3answers
28 views

Complexity analysis of a polynomial and a logarithmic exponential function

I need to find the asymptotic relationship between the functions $f(n) = n^{100}$ and $g(n) = (log_2n)^{(1/2) \cdot log_2n}$. I did the following to show that $f(n) = O(g(n))$: $n^{100} \leq (...
0
votes
1answer
90 views

Encyclopedia of Integer Sequences - Formula

I am trying to reproduce the following sequence (https://oeis.org/A062734): ...
3
votes
0answers
89 views

Reverse Automorphic Numbers

I recently stumbled across Automorphic Numbers (definition and examples). In simple words, a number $n$ is said to be automorphic if last $d(n)$ digits of $n^2$ are $n$ itself (where $d(n)$ is ...
0
votes
1answer
31 views

Correctness of the sweep line algorithm for line segment intersection in the plane

Suppose we are given a finite set $S$ of line segments in the plane and the intersection between two segments is empty or a single point in the interior of both segments at most two segments ...
0
votes
0answers
57 views

Problem with 4-body Matlab code

I'm trying to model the 4 body problem to see how Jupiter, Earth and Mercury orbit the Sun. I found a two body script and adapted it as accordingly to modify my problem, but for some reason the ...
0
votes
1answer
35 views

Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
0
votes
1answer
16 views

Proof quadratic congruent equation has no solutions in $\mathbb{N}$

In computer science, quadratic probing is used in hash tables. We choose a $c_1$ and $c_2$ in the hash formula $h(k,i) = (h'(k) + c_1 i + c_2 i^2) \mod{m}$ where $h'(k) = k \mod{m}$ and $m$ is the ...
0
votes
1answer
32 views

Extract each digit of a binary \ decimal number

How can one extract the digits of a binary \ decimal number. For example i have 100110111 to need to extract them only using +,-,*,/ and MOD. I can only use this LOOP Language. Most of the algorithms ...
0
votes
1answer
28 views

What's the difference between “worst/best case big-O()” and omega()/theta()?

In formal discrete math and computer science we talk about "big-θ," "big-O," and "big-Ω" notation, being tight, upper, and lower bounds (respectively) on the growth of properties of an algorithm as ...
0
votes
3answers
38 views

is a^(m)b^(n) | m >= 99 and n>=999 a regular language?

I've been stuck on this problem for a while. Say we have the following language? a^(m)b^(n) | m >= 99 and n>=999 I'm trying to use the pumping lemma to ...
0
votes
1answer
18 views

Proof of Rows/Columns/Main Diagonals in a normal Magic Square

Someone else had asked this question but not to enough detail. I understand that you can sum all of the elements from $1$ to $n^2$ that are in the matrix to get $n^2(n^2+1)/2$. Then from there you ...
1
vote
1answer
46 views

Solving a recurrence with 2 recurrences

I am trying to solve the following recurrence: $$T(n) = T\Big(\frac{n}{3}\Big) + T\Big(\frac{2n}{3}\Big) + O(n)$$ I do not want to use the Akra-Bazzi method nor draw out a recurrence tree. I do know ...
2
votes
1answer
25 views

Space-Hierarchy Theorem in Theoretical CS

Sipser has a proof this theorem that goes like this: $$D = \text{"On input } w$$ $$1. \text{Let } n \text{ be the length of } w$$ $$2. \text{Compute } f(n) \\ \text{using space constructibility and ...
2
votes
0answers
46 views

How to choose set in Group Isomorphism Algorithm( Quasipolynomial time)

In the paper titled "On the $n^{log_2(n)}$ Isomorphism Technique" by Gary L. Miller, it is written A group is a binary operation * , satisfying 1) and 2) . 1) a)$ \exists! x(a*b = x)$ ...
0
votes
1answer
37 views

Proving Gale-Shapley algorithm completes in $O(n^2)$

In Algorithm Design by John Kleinberg and Eva Tardos, the proof for the Gale-Shapley algorithm running in $O(n^2)$ is given In the case of the present algorithm, each iteration consists of some ...
2
votes
0answers
23 views

Math of Repetition

Let R = A (A | B) (A | B | C) (A | B | C | D) ... be an R-Form(A sort of repetition matching grammar). Where A,B,C,D,... are symbols that allow equality comparison. Any sequence of A,B,C,D,... can ...
1
vote
1answer
41 views

Does two's complement arithmetic produce a field isomorphic to $GF(2^{n}$)?

From what I understand, we have these two isomorphisms: $(TC, +)$ is isomorphic to the cyclic group $\mathbb{Z}/2^n\mathbb{Z}$. $(TC, *)$ is isomorphic to the multiplicative group of polynomials. ...
0
votes
4answers
63 views

In formal verification, what is the formal specification, what formally means there?

I have been reading a lot about formal verification of software and apparantly you need to formalize the behaviour of the program to create an equivalent model of it (if I get it right). But nowhere ...
0
votes
2answers
32 views

Practical usefulness of $\mathbb N$ to$\mathbb N\times\mathbb N $or $\mathbb R$ to$\mathbb R\times \mathbb R$ bijection in data processing?

A while ago, I was reflecting on the practical usefulness of bijections from $\mathbb N$ to $\mathbb N\times\mathbb N$, or $\mathbb R$ to$\mathbb R\times\mathbb R$. (We all know they exist.) Wouldn't ...
0
votes
1answer
67 views

How to apply negation to a term?

EDIT: Maybe page 18 of this paper can help. This is a follow up from this question, where I am using ALCQ and I have this: $\lnot(3 \le \exists \text{hasPet}.\text{Animal})$ How to apply the ...
1
vote
0answers
44 views

Determine Huffman Tree Depth Using any combinactory ways?

I see this link for determining depth (height) of Huffman tree, but not useful for me. My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
2
votes
1answer
75 views

Normal Matrix - Is this a valid method of calculation?

Apologies in advance if I have posted unnecessarily. I posted this question on stack overflow but it seems it is more a maths question, hence the re-post here... I have almost finished coding a 3D ...
0
votes
0answers
17 views

Can someone explain the recursive solution to the Josephus Problem?

I saw a quora post that explained it like this: Take a simple case where n=5 and you remove every 3rd person. 1st turn: {1,2,3,4,5} Removed= 3 2nd turn={1,2,4,5} Removed = 1 3rd turn = {2,4,5} ...
0
votes
0answers
43 views

Crank Nicholson Method

I can not figure out what I'm doing wrong in otder to solve this problem using Crank-Nicholson Method. My code is below the picture. ...
0
votes
1answer
47 views

Make individuals distinct

I am trying to construct an ALCQ knowledge base (KB) for some sentences. Here is what I have: Abox (Yiannis is a person and he drinks only one kind of a coffee, frappe): Person(YIANNIS) $\forall$ ...
1
vote
2answers
38 views

Could tertiary computation negate the need for large memory?

In normal computers, pointers in code "point" to memory. On a lower level, linking and loading turns those "pointers" into numerical codes which really do point to specific bytes (or bits) of ...
0
votes
1answer
30 views

Constuct DFA from NFA with multiple epsilons

I need to create a Deterministic Finite Automata(DFA) from a Nondeterministic Finite Automata(NFA). I have created the NFA, however i'm having a hard time understanding the steps needed to turn the ...
0
votes
1answer
103 views

Stronger Pumping Lemma for Context Free Languages

Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ...
0
votes
1answer
30 views

Use unification and resolution to justify proof

Prove: If $\neg A(x)\lor B(y),\neg C(x)\lor G(w),\neg G(x)$, and $A(x)$, then $B(x)\land \neg C(w)$ Use resolution and unification to do your proof. Justify each step. I'm not sure how ...
0
votes
1answer
50 views

Random graph problem

I'm trying to analyze a network algorithm to get a latency probability distribution. One of the steps is to "calculate the probability distribution of the number of updated nodes in a single hop of a ...
1
vote
1answer
86 views

Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
0
votes
2answers
44 views

How to define numbers in a way that a number 'n' is equivalent to the function plus 'n'?

In lambda calculus, is it possible to define (or disprove the existence of) a number system alternative to church numerals such that each number is a function which on application, adds itself to it's ...
0
votes
2answers
44 views

How do I use integral calculus to estimate a discrete sum?

The Algorithms course I am taking on Coursera does not require discrete math to find discrete sums. Dr. Sedgewick recommends replacing sums with integrals in order to get basic estimates. For example:...
0
votes
1answer
17 views

Why is the expected length of a chain in hashing equal to $n/m$ (the load factor) due to independence of collisions?

Say we have inserted $n$ keys and that we have $m$ slots and that the Simple Uniform Hashing Assumption holds (each item to be hashed has an equal probability of being placed into a slot, regardless ...
3
votes
1answer
48 views

MST, Cut in Graph, Some Claims?

I ready for taking a P.hD Entrance Exam. one of old-solution problem of Data Structure is as follows: Which of the following Claims is True about MST of Simple, ...
1
vote
1answer
45 views

Randomized Quick Sort and Partition Probability?

We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes. Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
1
vote
1answer
82 views

Proof of the PAC generalization error bound using VC dimension

There is a theorem in PAC ("Probably Approximately Correct" model, in computational learning theory) that reads as follows: To guarantee that any hypothesis that perfectly fits the training data ...
0
votes
1answer
50 views

Question on my interpretation of logical notation relating to alphabets, theoretical comp sci.

EDIT: I cross-posted this, and couldn't delete this one as it had some answers. There is a good answer at: http://cs.stackexchange.com/a/53056/46284 $\exists x \in \Sigma^* (t=sx)$ Have I ...
2
votes
1answer
59 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? EDIT: But is an open knight tour? Thus possibly not an Hamiltonian ...
2
votes
1answer
58 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
71 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 ...
0
votes
1answer
20 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$, ...