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

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
29 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
124 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
94 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
71 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
810 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
248 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
169 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
184 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
44 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
99 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
462 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. ...
0
votes
1answer
27 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
0
votes
1answer
77 views

Any algorithm or theorem to decide whether two functions are equivalent? [duplicate]

Any algorithm or theorem to decide whether two functions that are polynomials,rationals and analytic over $\mathbb{N}$ or $\mathbb{Q}$ or $\mathbb{R}$ or $\mathbb{C}$ are equivalent ?
1
vote
1answer
50 views

Are these two notions of “computable function” the same or related?

From http://en.wikipedia.org/wiki/Semicomputable_function, we have: "If a partial function is both upper and lower semicomputable it is called computable." Is this the same kind of "computable ...
1
vote
0answers
53 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
3
votes
1answer
91 views

Why are Truth, Conjunction, and Implication called “Negative” fragments of IPL (intuitionisti logic Proposition Logic)?

Someone answered that negative means we are ""Using"" them . But the point is for all of these there is an Introduction rule too. So why call them negative? I don't know whether it's computer ...
0
votes
0answers
36 views

Euler’s theorem: any sequence of rotations = one rotation about some axis

While learning about transformations in Computer Graphics,I couldn't get why any sequence of rotations is actually equal to one rotation about some axis by Euler's theorem as stated in Computer ...
0
votes
1answer
32 views

Norm of Triangle Matrix

How to find the norm of the following matrix, please? Thank you! $$T := \begin{bmatrix} 1 & n \\ 0 & 1 \end{bmatrix},$$ and $$\|T\| = \sqrt{n^2+1}.$$
0
votes
1answer
49 views

Calculating screen intersection points with lines

I am writing a game and for the life of me can't figure out the most efficient way to program this. I have a boss who comes into the middle of the screen. He then engages 4 lasers which extend well ...
1
vote
2answers
78 views

How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
1
vote
1answer
193 views

Pigeon-Hole Principle and 2d grid

Q:Consider the 2D grid with integer coordinates.Prove that if we take 5ve points on the grid then there exist two of the points whose average is also a point on the grid. I understand the basic idea ...
3
votes
1answer
64 views

Hypercomputation & Higher Dimensional Variants of Conway's Game of Life

Conway's Game of Life is a simple and important mathematical game with some rules of evolution in a two dimensional space. It appears in many subjects in mathematics, artificial intelligence and ...
1
vote
1answer
31 views

Maximum variable string length $m$ needed to represent $n$ items using strings of size $1$ through $m$ with fixed alphabet size

Consider the following problem. You have a list containing $k$ total identifiers comprising $n$ unique identifiers such that $k \ge n$ (i.e. there can be duplicates). These identifiers are long ...
1
vote
0answers
23 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
0
votes
1answer
107 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
0
votes
2answers
235 views

Increase by one, Shortest path, changes the edges or not? [closed]

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
2
votes
1answer
54 views

How much RAM is needed for $2^{14}$ square grid of double numbers?

How is calculated the memory that is needed for matrix of $2^{14}$ by $2^{24}$ double precision real numbers ? Matlab stops responding with 32Gb ram.
0
votes
1answer
61 views

Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
2
votes
1answer
96 views

Entropy determination regarding lossless data compression

Suppose I had many computer data files to compress losslessly and wanted to know what is the theoretical limit to each one as far as minimum filesize possible. How would a math person go about doing ...
4
votes
2answers
125 views

Computers can't deal with limit of $\Delta x \to 0$

While I was studying about finite differences I came across an article that says "computers can't deal with limit of $\Delta x \to 0$ " in finite differences.But if computers can't deal with these ...
8
votes
1answer
550 views

Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
1
vote
0answers
72 views

Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
0
votes
1answer
104 views

Proof of why the partition function Z in probabilistic graphical models (PGM) is NP-complete

I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard? I would like to see a full blown rigorous proof, however, I am as happy to get a ...
2
votes
1answer
54 views

Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
2
votes
0answers
210 views

For those wanting to study theoretical computer science, is Math a degree that worth more than Computer Science? [closed]

At my University, everyone first enrol in a Science and Technology, a very general course, and then choose the specialisation (like Computer Science, Math, some Engineering, etc). As I was finishing ...
0
votes
1answer
46 views

How to take the integral of a derivative to obtain desired result?

I am aiming for the form of derivative below computed over time that causes its differentiated variable V to go from an initial -.001 and increase to reach 10. I will explain my current calcs below ...
2
votes
0answers
93 views

Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
2
votes
1answer
92 views

The disease problem

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion. At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...