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

-1
votes
0answers
8 views

Can you determine the number of maxterms given the minterms? [on hold]

There is a 4 input function F(a,b,c,d) implemented in a two level sum of products. 3 transformations 1. complement all inputs to F and get function G1 2. Replace ANDs with ORs and vice versa in F ...
0
votes
0answers
14 views

Queue and Stack in Computer Science and relation to MATH

For Creating a Queue Q we use two Stack S1,S2. for insert x in the end of Q we do Push(S1,x). for deleting element from front of Q, (if Q is not empty) we do Pop(S2). if on Q that at first is empty, ...
0
votes
1answer
22 views

recursive definition odd length strings

Given the alphabet {aaa bbb}, give a recursive definition for the language that only contains odd length strings. must be constructive definition we are suppose to treat aaa as one letter and bbb as ...
0
votes
2answers
29 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
0
votes
1answer
32 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
0
votes
0answers
33 views

Every DPDA has an equivalent DPDA that always reads the entire input string

I am trying to understand the proof from Michael Sipser's Introduction to the Theory of Computation, page 132. I don't understand why if $q \in F′$ then $\delta(q,a,\$)$ is set to ...
1
vote
2answers
72 views

Do mathematics researchers regularly solve problems like this?

I'm not sure that this is the right exchange for this question. It asks about the possibilities of research in mathematics and computer science. Extended Background I am very interested in ...
-1
votes
5answers
62 views

How would I show that R is an equivalence relation?

If I were to consider the relation R on ℤ defined by n R m if and only if P(n)=P(m). How would I show that R is an equivalence relation? Any help is appreciated.
0
votes
2answers
731 views

Colored ball probability [on hold]

A triangular box contains five differently colored balls: red (R), green (G), blue (B), white (W), and yellow (Y). Define an appropriate sample space to study the outcome of an experiment where a ...
1
vote
1answer
40 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
5
votes
2answers
5k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
0
votes
4answers
69 views

Number theory divisibility - simple way to prove this is prime?

Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z<y$, then let $x=y/z$. Prove that $x$ must be a prime number. Is there a simple way to solve this? It ...
1
vote
1answer
42 views

In lambda calculus, can the parameter of abstraction be a non-variable lambda expression?

In short, my main confusion is between the two concept variable and lambda expression: I am reading this reference here: ...
3
votes
2answers
30 views

Questions about the functions of the operations of a queue

I am looking at the following two functions of two operations of a queue: ...
1
vote
1answer
295 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
4
votes
2answers
51 views

Question about queues

A queue is implemented with a sequence $Q[1\ldots n]$ and two indices $\def\head{\operatorname{head}}\head[Q]$ and $\def\end{\operatorname{end}}\end[Q]$ such that the elements of the queue are the ...
2
votes
1answer
29 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
-1
votes
0answers
18 views

The max number of repeats of substrings of a sample of a language.

So we suspect that finding the smallest grammar of strings in the language $\{a^n : n \in \Bbb{N}\}$, is hard. But luckily as far as applications to natural language processing, we would rarely ...
0
votes
1answer
35 views

Are minimum cut communities maximal?

I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al. Let $G(V, E)$ be some undirected weighted graph. Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum ...
2
votes
1answer
2k views

Quotient of a regular language

According to wikipedia the right quotient of a regular language with ANY other language is regular. I have not been able to find a proof of this fact. All the sources talk about quotient with another ...
2
votes
0answers
22 views

Strange Turing Machine Definition [closed]

i prepare for Autotmata Course Final Exam. in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote: Language of this TM is: {$W \in ...
3
votes
0answers
31 views

What is the desirable function identification when setting up arrows in the category of types?

My question is which functions can not be allowed in a statically typed programming language, so that the "canonical" category is less coarse than what you get if you define it's arrows to be ...
2
votes
1answer
47 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
1
vote
2answers
44 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
3
votes
1answer
93 views

Existence of a general-purpose (almost) universal optimization strategy

From Wikipedia about interpretations of no free lunch theorem A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization ...
3
votes
2answers
349 views

How shall I understand this simple example of No Free Lunch theorem?

I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's Introduction to stochastic search and optimization: My understanding is that a cost function is a ...
2
votes
1answer
50 views

Iteratively Replacing Substrings

This problem came up while I was helping someone. Informally, we have a string of characters and a "rule" which replaces a specific string with another one, and we repeat this rule until we can no ...
2
votes
1answer
35 views

Question concerning the GAP package qpa (find all ideals with a certain property)

I have the following question concerning the GAP package qpa. Let $k$ be a fixed finite field and let $Q$ be a fixed quiver. Let $kQ$ denote the associated path algebra. Since $k$ is ...
0
votes
0answers
18 views

Boehm's and Jacopini's insight and Math

My precalc teacher mentioned "If, then, else" in class today. So from the little programming experience I have, I picked up that the same thing exists in CS. I was wondering what that is called in the ...
3
votes
1answer
103 views

What is the mathamatical term for this programming concept?

In python's itertools, there is a function called permutations. It returns the number of ways to arrange x number of variables into a given space. For example, ...
0
votes
0answers
10 views

Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
0
votes
0answers
10 views

KMP Algorithm-Longest prefix which is also a proper suffix

Im trying to learn KMP Algorithm, im watching this video on KMP algorithm http://youtu.be/SVKe7bvQ4Xk?t=5m4s There is a statement in the video for determining π[K].It says length of longest prefix of ...
1
vote
2answers
42 views

Graph Degree and Some Condition

If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1) $. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that ...
4
votes
7answers
4k views

Why does a complete binary tree of $n$ leaves have $2n-1$ nodes?

A complete binary tree is defined as a tree where each node has either $2$ or $0$ children. A variety of sources have described the relation between nodes and leaves to be $2n-1$ where $n$ is the ...
2
votes
0answers
36 views

Equillibrium between Programming and Math Skills? [closed]

So I enjoy recreationally doing math and programming and am now at a stage where I will be pursuing them in University but I have found myself in a bit of a bind. My programming ability seems to lag ...
4
votes
2answers
67 views

Summation of general series

One of the problems in Donald Knuth's Art of Programming is phrased as follows: Find and prove a simple formula for the sum $\sum\limits_{n=0}^k\frac{(-1)^n(2n+1)^3}{(2n+1)^4+4}$ I have very little ...
0
votes
2answers
48 views

How to correctly calculate the fractal dimension of a finite set of points?

The box-counting dimension is defined by: $\lim\limits_{\epsilon \to 0} \dfrac{N(\epsilon)}{1/ \epsilon}$ What works well if you are solving algebraically or if you can recursively generate more ...
-2
votes
0answers
37 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
0
votes
1answer
218 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
9
votes
2answers
169 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
0
votes
1answer
43 views

testing parallelity/perpendicularity of two 3D vectors with lengths close to zero using dot product

as u know dot product and vector norm(euclidean) definitions are as following: $ \vec v . \vec w = \left\lVert \vec v \right\rVert \times \left\lVert \vec w \right\rVert \times \cos\theta = (v_x ...
5
votes
1answer
99 views

High school research project ideas

I'm starting my last year of high school, and I will have to do an all year research on a mathematical topic. I'm a really passionate learner and I'm very involved in computer science. I am stuck on ...
1
vote
2answers
81 views

Names of 3 input logic gates

I've tried to look this up online, I may have used the wrong terminology. This question is about the names of logic gates with three boolean inputs, and one boolean output. This is a truth table for ...
0
votes
0answers
30 views

On achieving the maximal correlation

I am reading the famous paper of Renyi, entitled "On measures of dependence" (see here1). He redefined the maximal correlation in a very general form for both discrete and continuous random ...
0
votes
1answer
36 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
1answer
68 views

Graph theory / vertex-set list representation

If I were to consider a graph with vertex-set V= {1, 2, 3, ... 10} with the edges taken as all the pairs {x, y} of distinct members of V that have a prime factor in common, how would one write the ...
1
vote
1answer
242 views

Is there a simple algorithm I can use for this?

if I were asked to find all integers between 1 and 100 that leave remainder 3 on division by 5 and leave remainder 4 on division by 7, how would I go about this? It seems like such a simple question ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
1answer
87 views

Public and private RSA keys, using the primes $p = 5$ and $q = 11$

Assume that $p = 5$ and $q = 11$, and all other variables are defined as per the RSA theorem (a) Suppose we consider $e = 3$. Would $(e, n)$ be a suitable public key? (b) Prove that if $d = 27$, ...
0
votes
2answers
37 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.