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. For ...

learn more… | top users | synonyms

1
vote
2answers
48 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
3answers
29 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
1k 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(S_1) = h(S_2)$. If we imagine the rows permuted randomly, and we proceed from the ...
0
votes
2answers
47 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 ...
2
votes
0answers
162 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$. ...
2
votes
0answers
54 views

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

I have a set of numbers $\{a_1,\dots,a_n\}$ and another number $k$. I need to find whether sum of any combination of numbers in the set produces $k$. It can be $a_1 + a_2$ or $a_1 + a_2 + a_3 + a_7$. ...
1
vote
2answers
597 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
5k 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
49 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. ...
10
votes
2answers
872 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
72 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
75 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) ...
1
vote
1answer
221 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
135 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 ...
1
vote
1answer
78 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
vote
3answers
103 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 ...
1
vote
1answer
71 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
27 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 ...
1
vote
1answer
100 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
63 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
76 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
91 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 ...
0
votes
1answer
177 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
-1
votes
1answer
79 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
1answer
33 views

Convex hulls for a finite amount of points

I'm trying to understand what a convex hull intuitively is, and say given for a set of points $(x,y)\in\mathbb{R}^2$ how is it generated from these points? I tried reading the wikipedia article and ...
-1
votes
1answer
104 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
-3
votes
1answer
306 views

How to obtain $\operatorname{lcm}(a_1,a_2,a_3,\ldots,a_n)\%1000000007$ [closed]

The problem is that you have $n$ numbers whose value can be in range $[1,100000]$. The task is to find the LCM of all these numbers. Now the answer can be very large so it should be printed MODULO ...
1
vote
1answer
210 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
0
votes
1answer
22 views

Linear equation so that the solutions has to be integers.

I have this equation $$-X_5-32X_4-32^2X_3-32^3X_2-32^4X_1=[PARAMETER]$$ I want to get all the solutions to this equation with a given parameter(integer) and all of the solutions has to be integers ...
0
votes
1answer
67 views

How do you find the probability of a certain state in Markov Chain?

This question appears without answer in an old exam I found (not a homework question) Suppose messages that enter a system need to be processed by two servers. They arrive at the system at a ...
2
votes
2answers
162 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
2
votes
1answer
56 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
0
votes
0answers
118 views

to maximize the summation

let F=$∑i=1$ to $N$ $((abs(A[i]-X))^P mod $K$)mod K$ $A[1..N]$ is an array with $N$ elements, the problem is to find $X$ such that the above summation F maximized where $X$ can take any value from ...
5
votes
1answer
216 views

Mathematical definition of Blender's F-Curves

I'm designing software for generating animation curves. I'd like the curves to be based on those found in Blender 3D, which they call "F-Curves." According to the page on the Blender Wiki, they are ...
0
votes
2answers
48 views

How to prove that for all 25 ppl and 4 groups, there is a group of at least 6 ppl from the same group?

As of Jun.17, I predict that Brazil, Germany, Italy, and Argentina will make it to the semi-finals of the FIFA World Cup. Suppose you have a group of 25 footballers from those four countries. Prove ...
6
votes
2answers
716 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
36 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
34 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 ...
1
vote
1answer
70 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
32 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
55 views

What does “modular” in “modular 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
60 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 ...
-1
votes
1answer
71 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 ...
1
vote
2answers
283 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
99 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
56 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 ...
12
votes
4answers
239 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 ...
5
votes
3answers
2k 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
73 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
2answers
412 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 ...