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

Interpolating transformation matrices

I read not to interpolate transformation matrices by linearly interpolating. Can someone explain to me why interpolating transformation matrices by linearly interpolating the matrix components is a ...
2
votes
1answer
50 views

What format is this?

I was given a snippet and can't seem to parse it myself, what's the name of this format and is there a tool that will render it like latex or mathML like this site does? ...
0
votes
0answers
43 views

What is the highest number that could be written down in principle using all computers in the world?

I read somewhere in the internet, that the capacity of all computers in the world would be about $10^{18}$ bytes. Does this mean, that in principle, a number with $10^{18}$ digits could be written ...
2
votes
0answers
33 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
1
vote
1answer
52 views

How does the function work? [on hold]

Could you explain me the function of the following two algorithms? ...
1
vote
1answer
40 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
0
votes
3answers
52 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
-5
votes
4answers
55 views

How many possible 1mb files are there? [on hold]

If you look at all combinations of data that can be stored in a 1mb file, how many are there before you have every possible 1mb file? How much space does that take up?
0
votes
1answer
19 views

A language $L$ is polynomially transformable to $L_0$

Could someone explain to me the following definition?? A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert ...
1
vote
1answer
10 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
0
votes
0answers
30 views

AoPS Intermediate Algebra vs. Higher Algebra by Hall and Knight? And some more questions about learning math.

Ok. I'm learning algebra at the level of AoPS algebra 2, and I want to quickly progress through math. Allow me to explain the situation. I am highly interested in artificial intelligence/computer ...
0
votes
0answers
29 views

Show that it is NP-complete [on hold]

Show that the problem of determining whether a regular expression over the alphabet $\{0\}$ does not denote $0^*$ is NP-complete. Could you give me some hints how I could do that??
1
vote
0answers
31 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
1
vote
1answer
20 views

Why the only binary MDS codes are trivial ones?

Why the only binary MDS codes are trivial ones? I have been thinking how to draw a contradiction by assuming the MDS code is not trivial. Thank you very much!
2
votes
2answers
17 views

Proving that median of list $[x_1,x_2,…,x_n]$ minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $m$ is some number

The problem is in the title. Here is a detailed description: Let's say we have list $[x_i]_{i=1}^{i=n}$ where $x_i\in\Bbb{N}$. I want to pick such $m\in\Bbb{N}$ which minimises the sum ...
3
votes
1answer
98 views

What kind of edge do we have?

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this: $$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset ...
1
vote
1answer
48 views

Trying to find formula for max number of nodes in a non-Binary tree.

I'm trying to find the max number of nodes in a tree that is defined as follows: The root can have at most $2$ children. Each subtree on the left can have at most $L$ children. Each subtree on the ...
0
votes
0answers
20 views

Is there a universal constant for size of disjoint clauses in 3-CNF

We are given a 3-CNF formula $\Phi$ on n variables, and a guarantee that at least 1% of $2^n$ possible assignments satisfy all clauses in $\Phi$. Now construct set $S$ of disjoint clauses so that no ...
2
votes
0answers
27 views

Linear Algebra Book Recommendation [duplicate]

I am taking an undergraduate course in computer science an is in the first year of my college. I like mathematics and am willing to learn Linear Algebra first and then move on to Abstract Algebra and ...
1
vote
1answer
40 views

How do I solve for the zeros of a Chebyshev polynomical? (on a computer)

I am working on a computer program and have a method that returns a number for a given $x$, $y$. So $f(x, y) = z$, where $f$ is my method. if I know $y$ and $z$, can I find what $x$ will be, without ...
1
vote
1answer
21 views

Discreet Math - Given n>= 5 how many times does fib(4) occur?

I have been trying to solve the below problem (and similar problems) but I have no clue how to tackle it. Can please help me tackle this particular problem, and how to attack similar problems? The ...
1
vote
1answer
14 views

Urn Probability Combination Problem

I am in my first year of Comp Sci and I am reviewing for my Math Final. There are two Urns $U_1$ and $U_2$. $U_1$ has $10$ red balls and $8$ blue balls. $U_2$ has $16$ red and $4$ blue. Suppose you ...
0
votes
0answers
18 views

What does it mean for an equivalence class to straddle a set of states?

In the following question, what does it mean for an equivalence class to straddle a set of states? Assume you currently have two equivalence classes Φ and Ψ. In addition you have a set of ...
2
votes
1answer
22 views

Special Binary Relations/ Empty Relation, Universal Relation And identity Relation?

The universal relation U = A × A. (Correct me if I'm Wrong). I believe that the Universal Relation is an Equivalence Relation The empty relation E = ∅. From my understanding, a Empty relation on a non ...
0
votes
0answers
20 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
71 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
31 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
0answers
26 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 ...
-2
votes
0answers
16 views

Manifolds and Random Number Generators [closed]

I was reading this answer on quora: http://www.quora.com/What-are-the-most-important-uses-for-randomness/answer/Subit-Chakrabarti and was wondering about the following passage: Of course, a much ...
1
vote
2answers
39 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?
0
votes
1answer
27 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 ...
3
votes
1answer
62 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
31 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. ...
0
votes
0answers
30 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
28 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
35 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
16 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
37 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
46 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
32 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
56 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 ...
1
vote
1answer
43 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
52 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!$ ...
1
vote
0answers
45 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
32 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
80 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 ...
2
votes
0answers
33 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
17 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 ...
1
vote
1answer
52 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 ...