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
0answers
564 views

Gram matrix of Gaussian kernel is not positive definite

I am developing a machine learning software, where I am trying to apply kernel methods. I have N uniformly sampled scalar values, $\{x_1,\dots,x_N\}$ from a given interval $[a,b]$. My aim is to ...
3
votes
3answers
197 views

Can a Turing Machine process an infinite string?

I read in a text book once that a finite state acceptor machine cannot be an acceptor for an infinite language. My question is does this apply to Turing Machines? The implication, it seems to me, ...
1
vote
2answers
39 views

c(n,k) equals subdivisions

To compare n files, the total comparison count is: $$ {{n}\choose{k}} = C^k_n = \dfrac{n!}{k! ( n - k )!} $$ with k = 2. Input space is composed by all pairs of files to compare. I want to split ...
1
vote
1answer
173 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
1
vote
2answers
53 views

The expected time to sort $n$ elements is bounded below

Prove that the expected time to sort $n$ elements is bounded below by $cn \log n$ for some constant $c$. Could you give me some hints how I could do that?
1
vote
1answer
108 views

Is my Turing Machine (Transition Function) correct for finding if a string is of even or odd length?

I've been asked to create a formal Turing Machine (by means of a transition function) to which takes a string $a^n \in$ {a}* and decides whether it is an even or odd length. What I have made is the ...
4
votes
1answer
85 views

Calculating of genus of a curve

Let $C$ be a curve over $\mathbb{F}_q$ in projective plane. So $C$ can be done as zeroes of some gomogeneous polynomial $\in \mathbb{F}_q[x,y,z]$ with degree $n$. Whether is there algorithm which is ...
0
votes
2answers
97 views

Find both the largest and second largest elements from a set

Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons. Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient. ...
1
vote
1answer
117 views

Can 2 items be added/taken away from a stack in push down automata at once?

Here is a language and 2 ways (I hope) of representing it with a PDA. Can I use the notation (b,a $\to$ ee) or anything of the like, to take away 2 items from the top of a list at once? Such as I ...
3
votes
1answer
37 views

Modular arithmetic with huge modulus?

When the dividend is some huge power but the modulus is not so big, I can use modular exponentiation. But how can I compute the residue when the modulus is, for example, $2^{107} - 1$, a Mersenne ...
0
votes
2answers
661 views

Construct a PDA to accept the language

construct a PDA that accepts the language: a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$ my answer is : $$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$ b) ...
0
votes
1answer
24 views

complexity question regarding whether it is decision problem

When self teaching complexity theory and seeing arguments that were made online. I get some confusion. In the class, we classify problems into P: can be computed polynomially NP: given a claimed ...
0
votes
1answer
262 views

What is the possible maximum/minimum height for a 29 nodes AVL tree?

What is the possible maximum/minimum height for a $29$ nodes AVL tree? Maximum: We've learned in class that $h\le \phi \log_2n$. Where $\phi\approx 1.4404$. So if we calculate for $n=29$ we get ...
0
votes
2answers
170 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
1
vote
2answers
138 views

Discrete Math: Array-Pointer Representation

I am confused as to how the table is filled in for a pointer-array representation of a graph, and I can't find anything online that talks much about array-pointer representation. My book does not ...
1
vote
3answers
79 views

How many comparisons are required?

Let $S$ be a set of $n$ integers. Assume you can perform only addition of elements of $S$ and comparisons between sums. Under these conditions how many comparisons are required to find the maximum ...
2
votes
1answer
104 views

A decision tree has an expected depth of at least $\log n!$

I am looking at the proof of the following theorem and I have some questions. The theorem is the following: On the assumption that all permutations of a sequence of $n$ elements are equally ...
0
votes
2answers
408 views

The decision tree has height at least $\log n!$

The proof of the theorem Any decision tree that sorts $n$ distinct elements has height at least $\log n!$ is the following: Since the result of sorting $n$ elements can be any one of the $n!$ ...
0
votes
0answers
84 views

Is there a name for this constant? (0.0100011011…)

It's the simplest number I could think of that contains any finite binary code in its digits: $$\begin{align} c &= 0.0100011011000001010011100101110111...\\ &= ...
0
votes
1answer
419 views

checking boolean logical equivalence

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?
1
vote
0answers
102 views

smallest circuit

Let $SMALLESTCIRCUIT$ be the language consisting of all Boolean Circuits $C$ with the property that there is no smaller circuit $C^{'}$ that has the same truth table as $C$. (smaller means having ...
1
vote
0answers
41 views

Size of increments in commutative ring to reach given number

I have the ring $\Bbb Z_q = \{0,1,\ldots,q-1\}$, where $q$ is a prime. Starting from $0$, I want to make exactly $n$ equally sized increments and reach $a\in \Bbb Z_q$, with $n<q-1$. For example if ...
0
votes
1answer
26 views

Hexidecimal subtraction when more than one borrow is needed

I wanted to know how I would subtract two hexadecimal values from each other when more than one borrow is needed. Given 0x00000200 - 0x00000004 Here is what I ...
3
votes
1answer
89 views

Subsets of a monoid closed under left-multiplication by elements of a submonoid

Let $M, T$ be monoids (or, semigroups) with $M \subset T$. Then we can consider subsets $S$ of $T$ that are closed under left-multiplication by something in $M$, i.e. $$ a \in S, m \in M \implies ma ...
2
votes
2answers
592 views

Prove correctness of algorithm using induction

Bubblesort(A) int i, j; for i from 1 to n { for j from n-1 downto i { if (A[j] > A[j+1]) swap(A[j], A[j+1]) } } Could ...
3
votes
5answers
403 views

Proving formula for sum of squares with binomial coefficient

$$\sum_{k=0}^{n-1}(k^2)= \binom{n}{3} + \binom{n+1}{3}$$ How should I prove that it is the correct formula for sum of squares? Should I use induction to prove the basis? Any help is appreciated.
5
votes
1answer
80 views

Is a thorough study of algorithms useful for a mathematician?

In my university, there is a core course called "basics computer science for mathematicians". The topics covered range from algorithms, to the bases of programming, to theory of computability. The ...
2
votes
0answers
30 views

Deriving a recurrence equation and apply Master's Thrm to it

So for a function such as: function Hi(n) if n > 1 then for j ← 1 to n do print(”Hi”) Hi(n/2) Hi(n/2) Hi(n/2) It's very easy to eyeball this and get a ...
3
votes
2answers
173 views

Application of Mergesort

We have $8$ players and we want to sort them in $24$ hours. There is one stadium. Each game lasts one hour. In how many hours can we sort them?? I thought that we could it as followed: ...
1
vote
0answers
60 views

Proof of Correctness: Recursion inside loop

I am trying to prove the correctness of the algorithm in the research paper. It is at page 17 in the pdf. ...
0
votes
0answers
18 views

Show that this is the number of moves that have to be done to solve the problem [duplicate]

Prove that $2^n − 1$ moves are necessary and sufficient to solve the Towers of Hanoi problem. Could you give me some hints how I could do that??
2
votes
0answers
128 views

Recursive definition of a language

Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria: All words in L contain the substring aa an odd number of times. All words in L are such ...
1
vote
1answer
148 views

Finding recurrence relation for digits

codes have been generated odd number of odd digits. Let $ a_n $ be the number of valid n-digit activation codes. Find the recurrence relation. I can't figure out and understand the question. Can you ...
0
votes
1answer
43 views

How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$. I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ . $f(n)=O(g(n))$ That means that $\exists c_1>0, n_2 \in ...
-1
votes
2answers
55 views

How may occupied positions are there?

Consider an array, that can have a huge ( or infinite ) number of positions, but only the first $n$ positions are occupied(only $n$ of them contain valid elements), and the remaining are empty. ...
0
votes
1answer
121 views

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
2
votes
0answers
99 views

Differential Geometry for Computer Science

I am looking for a good book or other resources on Differential Geometry for Computer Sciences or more specifically Differential Geometry used in Computer Graphics, Geometric Modelling and Mesh ...
1
vote
1answer
63 views

Given $x,y\in\mathbb R$ is there a “formulaic” way to obtain a $q\in\mathbb Q$ with $a<q<b?$

Is there an assignment of reals $x,y$ to a rational number $q(x,y)$ for which $$\forall_{\mathbb R} x.\forall_{\mathbb R}(x<y).\left(x<q(x,y)<y\right)\hspace{.2cm}?$$ For computable reals, ...
0
votes
1answer
54 views

Did I do this big-Omega proof correctly?

Prove or disprove: 6n^3 – 4n^2 + 3n +2 is in Ω (5n^3 – n^2 + n +1). So I'm not sure if I did this right or not, any pointers or the correct steps would be helpful Ǝc ∈ ℝ+, ƎB ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ ...
1
vote
1answer
72 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
0answers
58 views

an instance of NP-complete

The cafeteria serves $m$ different kinds of food, $F = \{ f_i \}_{i = 1}^{m}$. The fruit are grouped into $n$ different types of bags $B_1, \cdots, B_n \subseteq F$. (The same kind of fruit might be ...
1
vote
1answer
68 views

What is this function?

In python I made this function: def f(x): eqStr = '' for y in range(int(x)): eqStr += 'x**%s + ' % (y) eqStr += '0' return eval(eqStr) ...
1
vote
1answer
889 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?
0
votes
1answer
294 views

is $\{a^n b^m | n \neq m\} $regular or non regular?

$\left\{a^nb^m\mid n \neq m \right\}\subset \{a, b\}$. I have been asked to prove this is irregular but I think it is regular as I can write a regular expression a*b* for it. Am I wrong? If so how ...
0
votes
1answer
180 views

Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$ So far I have $E \to EcE$ $E \to a$ $E \to b$ $E \to c$ But I'm new at this and feel I'm miles away from a finished answer
0
votes
2answers
187 views

If language L is not regular, and L ⊂ M. Do we know if M is regular or not?

I have been given some questions to do regarding regular/irregular languages. And have the following questions True/False (i) If L is not regular and L ⊂ M, then M is not regular. (ii) If L ⊂ M and ...
0
votes
1answer
48 views

decidability and countability

The diagonolisation technique is utilized to prove that the halting problem is undecidable. However, I kind of sense that it is making the assumption that decidable sets should be countable. Is this ...
1
vote
1answer
103 views

True or False Time complexity questions

Here is my go at them and any help is appreciated: If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f - g)(n) = \Theta(n^2)$ where we define $(f-g)(n) = f(n) - g(n) \forall n$ TRUE? If $f(n) ...
1
vote
1answer
479 views

Time complexity of algorithms

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. ...