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.

learn more… | top users | synonyms

3
votes
1answer
49 views

Image Reconstruction:Phase vs. Magnitude

Figure 1.(c) shows the Test image reconstructed from MAGNITUDE spectrum only. We can say that the intensity values of LOW frequency pixels are comparatively more than HIGH frequency pixels. $$ ...
1
vote
1answer
26 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
2
votes
0answers
27 views

Generating interesting random TMs

To get a more intuitive understanding of the halting problem I want to generate some random TMs and see how they behave, what some heuristics can tell about them, etc. The problem is that, if I ...
0
votes
0answers
35 views

another series problem [duplicate]

I need help in simplification below are the two formulas for AGP series: if $n$ is even $a\cdot r^{(n-1)/2} + d\cdot( 1 + r + r^2 + r^{(n-1)/2})$ if $n$ is odd $a\cdot r^{(n-1)/2} + d\cdot( 1 + ...
0
votes
0answers
42 views

need help in simplification

I need help in simplification below are the two formulas for AGP series: if $n$ is even $a\cdot r^{(n-1)/2} + d\cdot( 1 + r + r^2 + r^{(n-1)/2})$ if $n$ is odd $a\cdot r^{(n-1)/2} + d\cdot( 1 + ...
1
vote
1answer
66 views

another counting problem

There are $k$ warriors that participate in the Wars, which have happened for the past $n$ years. Each year there has been a victor. Further, a particular warrior $W$ has won the Wars an even number of ...
1
vote
0answers
24 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
1
vote
0answers
22 views

What does “modular” in “modulr functions” mean?

From Wikipedia If $\Omega$ is a set, a submodular function is a set function $f:2^{\Omega}\rightarrow \mathbb{R}$, where $2^\Omega$ denotes the power set of $\Omega$, which satisfies one of the ...
0
votes
2answers
57 views

minmizing average problem

Given a set containing N numbers, minimize the average where you can take out any string of consecutive numbers in the set. |N|<=100000 Ex. {5, 1, 7, 8, 2} You can take out {1,7}, etc. but the ...
0
votes
0answers
31 views

Two definitions of matroid

From Wikipedia, a finite matroid $M$ is a pair $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$ either with the following properties: The empty set is in $F$. if $X \in ...
0
votes
0answers
8 views

Rank feasible subset of a greedoid

From Wikipedia, given a greedoid $(E,F)$, with ground set $E$ and the class $F$ of feasible sets, A subset $X$ of $E$ is rank feasible if the largest intersection of $X$ with any feasible set has ...
0
votes
1answer
56 views

Function Combination on Computer Science

I read some material on Computational Function, every one could describe the result of following combination? suppose $g_1(x)=3x$, $g_2(x)=4x$, $f(x,y)=x+y$, how we compute combination of $f$ with ...
0
votes
0answers
71 views

Primitive Recursive Predicate Challenge

I'm an Computer scientist, and I recently ran into a challenge. If we have primitive recursive predicate $P(x), Q(x)$, I think that all of following 4 expressions can be primitive recursive. Any hint ...
0
votes
0answers
46 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
1answer
49 views

Complexity & Computation & Logic Problem [closed]

As i study for prepare to CS Final exam, i have some challenges. can i say all of following statements are true? 1) each infinite recursive set, is union of two disjoint infinite recursive set? 2) ...
1
vote
2answers
48 views

Compressing binary numbers

If I have a arbitrarily long random binary number with the condition that the probability that a given digit is 0 and 1 is 1/4 and 3/4, respectively. What is the best way to compress this into a ...
1
vote
1answer
35 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
0
votes
1answer
20 views

Understand the English paragraph on association rule.

I am currently studying Association Rule Pattern Mining. I am reading the explanation on wikipedia about it. Somehow, I feel like I have a problem in understanding the paragraph below. Can somebody ...
0
votes
0answers
27 views

Using the pumping lemma to prove that a certain language is not regular

I've been trying to understand the pumping lemma since forever, I just don't know what it does, I have no clue what any of it does. My college professor sucks, he thinks writing a bunch of stuff on a ...
11
votes
4answers
168 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
4
votes
3answers
114 views

How is math used in computer graphics? [closed]

I'm doing a research paper on the mathematics of computer graphics and animation (3D) and I do not know where to start. What mathematical equations and concepts are used for computer graphics and ...
0
votes
0answers
38 views

Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
-2
votes
1answer
34 views

Assume that a text file contains the string “aabbaaccde” . Write Huffman code [closed]

Assume that a text file contains the string "aabbaaccde" . 1-Write Huffman code a, b; c, d and e . 2-What is the size of the compressed file? how can solve this question
2
votes
2answers
72 views

Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
1
vote
0answers
20 views

Finding the upper bound of the length of a closed walk

I am having trouble understanding a part of the proof of Lemma 2 (Page 184). It says the length of the tour is $$ \leq \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2} $$ I ...
0
votes
1answer
21 views

Reduction between languages in P

I have a simple question about the class P: Is there exist a polynomial time reduction between every two languages A, B in P?
0
votes
1answer
35 views

Do sets require a general equivalence relation over all elements?

and does this mean there cant be sets of things I have not defined equivalency for? This is maybe a weird question and maybe not even a meaningful one, my understanding of sets and such is not ...
1
vote
1answer
53 views

Calculate the probability that at least k of his favourite students are awarded?

Our hero - Maga is going to make a new contest for making the best teams. He is really excited about it. There will be S students in the contest. First N students in the final standings will be ...
1
vote
1answer
39 views

What's a more optimal native C-language algorithm to set bit $k$? [closed]

Let $n$ be an integer (for example an unsigned int which is usually 32- or 64-bits), let the number of bits be $|n|$. Let $0 \leq k \lt|n|$. I usually do: ...
0
votes
1answer
39 views

Is there any algorithm (if possible, I need the codes) for Jordan normal form decomposition for large matrices in practice?

Although it is an ill-posed problem as B Kågström said in "An algorithm for numerical computation of the Jordan normal form of a complex matrix", I wonder what people do when they need to do Jordan ...
2
votes
0answers
28 views

Bijection of simple set

Let $X$ is simple set (http://en.wikipedia.org/wiki/Simple_set) $Z \subset X$ is infinite recursive set. $Y = X$ \ $Z$. How to prove that there is a computable bijection $f$ that $x \in X ...
2
votes
0answers
42 views

Turning a cup into a donut: parametrising the continuous deformation

A cup and a donut are topologically equivalent because one can be continuously deformed into another. What if you had a particular cup and a particular donut and wanted to write down (or simulate on a ...
2
votes
1answer
45 views

Time complexity of random algorithm

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$. At first I thought to perform the analysis by saying ...
0
votes
1answer
21 views

Proving the following bijection

Let $F = \lbrace S_1, S_2, \dots, S_n \rbrace$, where $S_i \subset \lbrace 1, 2, \dots, 3m\rbrace$ and define a function $f: F \to \mathbb{N}$ by $$ f(S_i) = \sum_{j \in S_i} (n+1)^{3m-j} $$ then ...
4
votes
2answers
88 views

Mathematical concept for formal languages

A formal language is defined as a subset of finite-length strings over an alphabet. It is similar to the mathematical concept "relation", but the lengths of its strings are not fixed. Since the name ...
0
votes
1answer
29 views

Is $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) $?

Intuitively I know that $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) $ but how would I go about proving this? I am at my wit's end on this. $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) \Leftrightarrow \exists c, ...
0
votes
1answer
40 views

Exact calulation of trigonometric functions

My question is a bit related to computer science and I am not quit sure if this place is a good one for it. Let me know if I should move it. So as you know values of functions like sin or cosine can ...
0
votes
0answers
90 views

Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
1
vote
1answer
23 views

Myhill-Nerode theorem for the language: $L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$

I have to use the Myhill-Nerode theorem for the following language: $$L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$$ An equivalence relation is the following: $$x \sim y\ \Leftrightarrow \forall\ \ ...
2
votes
3answers
44 views

Strong Induction, assuming k<n where k and n are not numbers

In strong Induction for the induction hypothesis you assume for all K, p(k) for k If for example I am working with trees and not natural numbers can I still use this style of proof? For example if I ...
2
votes
1answer
86 views

How much of mathematics could be created now using computers [closed]

What great mathematical achievements of the previous times could be easily gotten today using computers and heuristic algorithms of CS. I do not mean calculation of constants, but mostly proving ...
0
votes
0answers
18 views

Quantization minimizing the quadratic error

I am working on a quantization problem which could be express in these terms : Given a set of positive reals $\{x_1, x_2,\dots,x_M\}$, I need to find another set $\{y_1,y_2,\dots,y_N\}$ of size $N ...
0
votes
0answers
37 views

What connections between computer science and ergodic theory?

I have a background in ergodic theory, but I am switching to computer science/programming. I would like to know if tools from ergodic theory could be useful, especially something around coding of ...
1
vote
1answer
36 views

Designing a context free grammar

I have to design a grammar over the alphabet $\sum=(a,b)$, so that $c^a(\alpha)=c^b(\alpha)$ and the second part $c^a(\alpha)\leq c^b(\alpha)$ , where $\alpha$ is a word and $c^a$ and $c^b $ are ...
1
vote
1answer
39 views

Using rgb triplets in “scalar” math

So I'm reading a computer graphics research paper and I'm confused as to how to interpret certain formulas that are being used. In the paper, a value σ is defined as an RGB triplet. Later on, that ...
9
votes
0answers
161 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
0
votes
1answer
59 views

Number of all finite sequences from a set? [duplicate]

Given a set $\Sigma$ of letters, apply the Kleene star operation to it, and we get $\Sigma^*$, the set of all finite-length sequences from $\Sigma$, called strings (allowing a letter appearing more ...
0
votes
0answers
29 views

Proof that whether some arbitrary Turing machine on some input outputs $5$ is undecidable

Consider the language $L = \{<M, w> \mid w \, \text{run on } M \, \text{evaluates to} \, 5\}$, ie the problem of deciding whether, for a TM $M$ and input $w$, if you run $w$ on $M$ then $M$ will ...
0
votes
0answers
21 views

Adding a natural number to a normalized fraction

I am currently writing yet another rational number class where the fraction should always be normalized. When adding a natural number to a normalized fraction, it possible to get a non-normalized ...
0
votes
0answers
26 views

Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...