# Tagged Questions

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 ...

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 ...
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 ...
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: ...
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. ...
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??
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 ...
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 ...
43 views

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. ...
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? ...
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 ?
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 ...
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 ...
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 ...
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 ...
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}.$$
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...