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

0
votes
0answers
12 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 ...
1
vote
0answers
17 views

Strange Turing Machine Definition [on hold]

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 ...
2
votes
0answers
27 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 ...
0
votes
2answers
38 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 ...
0
votes
1answer
34 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 ...
0
votes
1answer
32 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 ...
0
votes
0answers
17 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
78 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
8 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 ...
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 ...
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 ...
-2
votes
0answers
35 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
8
votes
2answers
166 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 ...
1
vote
2answers
79 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
28 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
2answers
50 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 ...
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 ...
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. ...
1
vote
1answer
241 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 ...
5
votes
1answer
98 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 ...
0
votes
1answer
42 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 ...
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
2answers
36 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.
0
votes
1answer
25 views

Computable Function and Predicate Question

I See on Our Lecture note on Theory of Computation Course that: .... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute ...
2
votes
4answers
90 views

What is a bit-shifting standard C function for calculating $f(x) = \frac{(2^{16}- 1)}{(2^{32} - 1)}\cdot x$

I need to take 32-bit unsigned integers and scale them to 16-bit unsigned integers "evenly" so that $0 \mapsto 0$ and 0xFFFFFFFF $\mapsto$ ...
1
vote
2answers
41 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 ...
2
votes
0answers
19 views

Count the second smallest element of $S$ [duplicate]

Show that,given a set of numbers $S$,we can count the second smallest element of $S$ with $n+ \lceil \lg n \rceil-2$ comparisons at the worst case. How can I do it? I don't really know how to ...
-3
votes
1answer
59 views

State whether the following claim is true, and then prove or disprove it. Give a detailed structured proof, justifying every step. [closed]

State whether the following claim is true, and then prove or disprove it. Give a detailed structured proof, justifying every step. $$\forall n \in \mathbb{N}, [(\exists k \in \mathbb{N}, n = ...
0
votes
2answers
34 views

Trying to disprove a statement - some partial working included

I am trying to find a counter example to show that the statement below is false, but I am having difficulty in trying to find a reasonable argument. Here is the statement: $n^2-12n + 35 \geq 0$ for ...
0
votes
0answers
17 views

Low pass filter to maintain edge information

I am looking for a kernel as low pass filter that satisfy as:I must find a kernel that statisfies as follows: In the my reference paper, the author suggest gaussian kernel that is The gaussian ...
0
votes
1answer
74 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
1
vote
0answers
37 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
1
vote
2answers
30 views

What does “symbolically tractable” mean?

What does "symbolically tractable" mean in the following quote? "Traditional treatments of mechanics concentrate most of their effort on the extremely small class of symbolically tractable dynamical ...
0
votes
0answers
42 views

Which field of mathematics deals with streams of events?

I am looking for the area of mathematics that deals with streams of data: a stream of data in this sense is an ordered list of events. An event is an immutable piece of data seen only once. The event ...
0
votes
3answers
25 views

A property regarding intervals

While I was solving a problem on TopCoder I used the following assumption. I have n intervals: $ [a_1,b_1], [a_2,b_2],...,[a_n,b_n]$ and a number $T$ such that: $$ a_1 + a_2 + ... + a_n \leq T \leq ...
1
vote
1answer
36 views

How Jaccard similarity can be approximated with minhash similarity?

In Page 81 of this book, Mining of Massive Data Sets. It says the following: Now, consider the probability that h(S1) = h(S2). If we imagine the rows permuted randomly, and we proceed from the top, ...
0
votes
2answers
42 views

Getting a diverse set of three numbers from two numbers

I'm using this information to build an interface to pick a color, but I feel that this question is purely math-related. Please correct me if this is the wrong StackExchange site for this. I am making ...
1
vote
0answers
44 views

What are the numerical methods for huge polynomial systems? [migrated]

Let a system of $n$ polynomial equations of degree $d$ with $m$ variables. I'm interested in a sparse system with $d = 3$, $n \sim 2000000$, $m \sim 50000$ and integer coefficients. What are the ...
0
votes
0answers
51 views

Continuations vs. Yoneda

There is this observation (worldpress blog) that the continuation monad (Wikipedia) stems from the Yoneda embedding. For fixed data types $R$, the monad maps data types $T$ to types $(T\to R)\to R$. ...
1
vote
0answers
40 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers {a1....an} and another number k. I need to find whether sum of any combination of numbers in the set ...
1
vote
2answers
82 views

Retrieve the initial cubic Bézier curve subdivided in two Bézier curves

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, ...
2
votes
1answer
38 views

Rounding Percentages

Okay so I have been having a problem and would really appreciate any help. I have posted a table below with the aim of making this as simple/precise as possible. ...
1
vote
0answers
33 views

Why is there information loss here?

I posted this a while ago, but realized that actually this works, but produces information loss. Here is the process: Let's try to reduce a number $x$. We will be using base $\beta$ for this process. ...
0
votes
0answers
17 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
10
votes
2answers
158 views

Applications of Geometry to Computer Science

How is differential geometry (or any type of theoretical math) related to computer graphics and/or computer programming? A friend of mine has only a bachelors degree in pure math and got hired by ...
4
votes
3answers
52 views

Show that $\frac{x^4 +7x^3+5}{4x+1}$ is big-theta($x^3$)

I'm having trouble grasping how to set these types of problems. There are a lot of related questions but it's difficult to abstract a general procedure on finding constants that give the given ...
2
votes
1answer
29 views

Simple minimization problem

Suppose we want to execute a program on a processor which can run in three different modes. Each mode can be describe by a pair $(E,\tau)$ where $E$ denotes the energy consumption per cycle (in nJ) ...
-2
votes
1answer
99 views

The “Four beer caps” puzzle [closed]

Four beer caps are placed on the corners of a square table with arbitrary orientations. There is a robot on the table that acts upon three commands: (a) “flip a corner cap”, (b) “flip two diagonal ...