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

2
votes
1answer
41 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
72 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 ...
9
votes
2answers
176 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
97 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
34 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
3answers
75 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
69 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
42 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
244 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
106 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
51 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
44 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
40 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
27 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
96 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
43 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 ...
0
votes
2answers
35 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
20 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 ...
2
votes
1answer
81 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
39 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
33 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
45 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
48 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
43 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 ...
0
votes
0answers
56 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
83 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
78 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
38 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
20 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
173 views

Applications of Geometry to Computer Science

How is differential geometry (or any type of theoretical math) being used in computer science? Any research I have done on this topic leads me to some sort of applied math concept. I know that there ...
3
votes
3answers
55 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
32 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
110 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
68 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
63 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
20 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
57 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
48 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 ...
0
votes
0answers
19 views
2
votes
3answers
88 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
2
votes
1answer
51 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
19 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
2
votes
1answer
47 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
0
votes
2answers
55 views

The value of loop variable at the end of a loop in the insertion sort

I am looking at the algorithm of the insertion sort: Input: $A[1 \dots n]$ ...
0
votes
0answers
27 views

Space-dependent diffusivity and finite-differences

I want to implement a finite difference code of this simple diffusion equation with space-dependent diffusivity: $$\partial_{t}u =D\partial_{x}^{2}u+\partial_{x}D\cdot\partial_{x}u$$ I go for a ...
0
votes
1answer
26 views

Finding final value of sum from double summation code fragment.

sum = 0; inc = 0 for i from 1 to n for j from 1 to i sum = sum + inc inc = inc + 1 What does it mean when it is asking the "final value of sum" from above code ...