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
66 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
5 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
0answers
24 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
34 views

Equillibrium between Programming and Math Skills? [on hold]

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
162 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
77 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
48 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
35 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
95 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
40 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
40 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
35 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
23 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
41 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
34 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
50 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
39 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
36 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
0answers
35 views

Maximum number of compressed RLE strings under any given length

Given a random string of length L (for instance, "01100010000101" of length "14"), and knowing that this string is only numerical, how many other strings under the form Y one can achieve by ...
-2
votes
1answer
98 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 ...
2
votes
1answer
52 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
1
vote
1answer
57 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
1
vote
1answer
58 views

Is there a more general proof for the halting problem?

Note:If this question is better suited for a different site, please tell me in the comments. Summary:Is there a proof for the impossibility of the halting problem that doesn't involve calling it on ...
0
votes
0answers
18 views

n-1 dimensional hypercube perpendicular to given edge in m dimensional Hamming hypercube

Suppose to have a $m$-dimensional direct binary hypercube of $n=2^m$ nodes with appropriate labeling of nodes given the corrisponding m-bit string. Picking a directed edge $e=(u,v)$, is there a ...
1
vote
1answer
53 views

Computing a solution of the Laplace-Eigenvalueproblem with Neumann-b.c.

Good day! I was considering the Laplace-Eigenvalueproblem with Neumann b.c., i.e. find $u \in H^1(\Omega) \setminus \{0\}$ and $\lambda \in \mathbb{R}$, such that: \begin{eqnarray} -\Delta u \ ...
-1
votes
1answer
47 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...