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

0
votes
0answers
15 views

C /matlab/ Algorithm for monotonicity of Ploygon

is there any easy and understand able algorithm to check the monotonicity of random polygon and also help me to code in which language(c or matlab) is beneficial to code the algorithm
0
votes
1answer
28 views

What is the monotonicity of a polygon? [closed]

What is the monotonicity of a polygon and why is it necessary to check the monotonicity?
2
votes
1answer
66 views

Relationship between $L^1$ norm and sparsity

I'm doing some research in the field of sparse representation and sparse modeling. I have two variables and their $L^1$ norm is calculated to make comparisons. As I take it the smaller the value of ...
0
votes
1answer
21 views

Load balance N customers over K servers with different capacities

Let's say we have N customers that supply a stream of requests, but each customer i supplies different number of requests per minute - $R_i$. All requests are identical in terms of the amount of ...
3
votes
1answer
64 views

How do computer programs find roots of high-degree polynomials?

My question is motivated by curiosity about the optimization of high-degree polynomial functions. Let's say your experiment data are modeled by a non-trivial 15th degree polynomial. Taking the ...
0
votes
2answers
66 views

Prove correctness of the following algorithm for computing Fibonacci numbers [closed]

I am a student studying for my BS in Computer Science. We recently got asked this question in on of my class and with no book to reference I am going to ask it here for a little help. I know I will ...
0
votes
0answers
49 views

Comparing the methods of applied mathematics to computer graphics

As an applied mathematician working towards my PhD, I have some personal interest in aspects of computer graphics and procedural animation. Looking up people and reading papers in the field of ...
0
votes
1answer
31 views

Pumping lemma for two words that “completely different”

Let $"x"$ and $"y"$ be a words, we will say that two words are "completely different" if for all $1\leq i\leq |x|$ the $i$ letter in $x$ diffrent from the $i$ letter in $y$. Prove that the ...
1
vote
1answer
29 views

Perturbation of roots in Wilkinson's polynomial

I am studying numerical analysis. When I read the online definition I found on this paragraph: Suppose that we perturb a polynomial $p(x) = Π (x−α_j)$ with roots $α_j$ by adding a small multiple ...
1
vote
0answers
17 views

Converting CFG to PDA for $S\to aSd|aBd\\B\to bBc|\varepsilon$

I need to build a pushdowm automata for the context-free-grammar $$S\to aSd|aBd\\B\to bBc|\varepsilon$$ My attempt: I'm not sure if my attempt is correct or not.
1
vote
0answers
16 views

FORTRAN code for logarithmic energies function [migrated]

I need to write a FORTRAN code for the logarithmic energies function \begin{equation} H=-\sum_{i=1}^{N}\sum_{j=i+1}^{N}\ln{|x_i-x_j|}. \end{equation} where {${x_1,x_2,\dots,x_n}$} is a set of point on ...
2
votes
1answer
52 views

Using Rice's theorem to prove undecidability of $A_{TM}$

Can you use Rice's theorem to prove that the acceptance problem is undecidable? Wikipedia says that it can be used to solve the Halting problem too but I can't see how that works either. Here is the ...
1
vote
1answer
46 views

From a set of rules, derive the implications?

I've only just become interested in this domain, so sorry if I'm not using the correct terminologies. What I want is the following: Say I have a set of rules (or constraints), I want to derive some ...
2
votes
1answer
155 views

How to show that a function is computable?

Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable? Please note that $\phi_i(x) ...
0
votes
1answer
99 views

How to find an index of a computable function?

Is there an index $i$ such that $\phi_{p(i)}(0) = i + 2$, for a total computable function $p$? I know about the s-m-n theorem and fixed point theorem, and how to apply them to some basic ...
1
vote
1answer
93 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | ...
1
vote
1answer
104 views

Structural induction on binary trees

I have some problems understanding structural induction, maybe because it is such a rigorous way of thinking, so I don't really know where to start here.. This is taken from our Algorithms course and ...
0
votes
0answers
18 views

Minimum Label Spanning Tree of Odd Hole Disjoint Graph

Can the MLST problem be solved efficiently using odd hole inequalities if my graph G is a vertex disjoint union of odd holes with the additional constraint that the max degee of any vertex = 4 and min ...
0
votes
1answer
28 views

Binary subtraction with borrowing vs. 2's complement

Consider the following two binary numbers which are using sign-magnitude representation. Therefore, both are positive numbers. ...
0
votes
0answers
16 views

how to generate parity check matrix for a non-systematic generator matrix?

Introduction: Suppose $C$ is an $\left [ n,k \right ]$ code. Let $I_{k}$ be the $k\times k$ identity matrix. Let $P$ be a $k\times \left (n-k \right )$ matrix. Then, $\left ( I_{k} | P\right )$ is ...
0
votes
0answers
27 views

If $f(n) = \Theta(n^{\log_b{a}}\lg^k{n})$ where $k \ge 0$ , then the master recurrence has solution $T(n) = \Theta(n^{\log_b{a}}\lg^{k+1}n) $.

I'm working through problems to the book "introduction to algorithms". I'm going through the section on the master recurrence and have been running into some roadblocks. I found a solution to the ...
2
votes
1answer
13 views

Closed form expression for $n_j$ defined by $n_j=\lceil n_{j−1}/b\rceil$ clarification

I came across this answer to this question: Closed form expression for $n_j$ defined by $n_j=\lceil n_{j-1}/b \rceil$ I was hoping someone could clarify the following step: $q−1 \leqslant ...
1
vote
3answers
128 views

Isomorphism of Non-Symmetric Matrices

$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$. Example: An example of $6 \times 3$ non-symmetric matrix is $$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & ...
0
votes
1answer
20 views

Free context grammar for $\mathscr{L_2}=\{0^i1^j2^k|i,j,k\geq0,i+j=2k\}$

I need to bulid a free context grammar for $\mathscr{L_2}=\{0^i1^j2^k|i,j,k\geq0,i+j=2k\}$ My try: Let denote $T_{x}$ for $k=x$ $$S\to T_{0,1}|T_2\\T_{0,1}\to\epsilon|002|112|012\\T_2\to ...
3
votes
1answer
45 views

Free context grammar for $\mathscr{L_1}=\{a^{3n}b^{5n}|n\geq0\}$

I need to bulid a free context grammar for $\mathscr{L_1}=\{a^{3n}b^{5n}|n\geq0\}$ My try: $$S\to N_0|N_1|N_2\\N_0\to \varepsilon\\N_1\to aaabbbbb|N_2\\N_2\to aaaN_1bbbbb$$ I'm not sure if ...
1
vote
1answer
21 views

Analysing a context-free grammar

Let: $$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$ I need to find if: the word $aabbbcc $ is in the grammar, and if so to write a very left series, ...
0
votes
0answers
43 views

Two's complement involving binary numbers [Single-precision floating point number]

Given the following bit pattern: 0010 0100 1001 0010 0100 1001 0010 0100 What decimal number does it represent, assuming it is a single-precision floating point number?
1
vote
1answer
446 views

Coloring problem on directed graph

Let $D=(V,E)$ a directed graph. How to color nodes of $D$ in white and black such that: No two white colors are adjacent, and For each black node there exists at least one white node which is ...
1
vote
1answer
91 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
0
votes
0answers
32 views

What's the triplet loss back propagation gradient formula in Deep Face Recognition(VGG)?

I am trying to implement triplet loss described in Omkar M. Parkhi, Andrea Vedaldi, Andrew Zisserman "Deep Face Recognition" 2015. So how to calculate the gradient of W' in back propagation?
0
votes
1answer
61 views

Prove that this function is primitive recursive?

Let $g : \mathbb{N} \rightarrow \mathbb{N}$, $n\mapsto$ the $(n+1)^{th}$ natural number which is not prime. I have to prove that $g$ is a primitive recursive function. My attempt is by minimization ...
0
votes
2answers
62 views

Is this integral less than infinity?

Assume the following integral: $$ \int\limits_{-\infty}^{\infty}\frac{f\left(x\right)} {BB\left(\lceil abs\left(x\right)\rceil\right)}\mathrm{d}x $$ Where $f\left(x\right)$ is any computable ...
4
votes
1answer
38 views

Doubt about neural networks that allegedly compute beyond the Turing limit

The question is about a new result by Cabessa & Siegelmann. http://binds.cs.umass.edu/papers/2014_cabessa.pdf : "In this context, we show that the so-called plastic recurrent neural networks ...
1
vote
2answers
57 views

Leaping frog algorithm

I need your help with a riddle, I need to find the best algorithm to catch a frog, The frog is on the Natural numbers, it begins at point L, each time it goes K Leaps right (means if it was at point ...
2
votes
0answers
151 views

Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
2
votes
3answers
67 views

Turing Machine divisibility by 6 [closed]

I need to design a TM to check if a binary number can be dividied by 6. I don't know how to design it. Thanks
0
votes
0answers
12 views

What is the size of Quotient in integer division with remainder?

Suppose $a=(a_{k-1},\dots,a_1,a_0)_Z$ and $b=(b_{l-1},\dots,b_1,b_0)_Z$ then $ab=m=(m_{k+l-1},\dots,m_1,m_0)_Z$ so $m$ is a $(k+l)$-digit number in the base $Z$. Let $b_{l-1}>0$ and $a=bq+r$ where ...
0
votes
4answers
105 views

Books recommendation on Graph Theory (Beginner level)

What are some of the best books on graph theory, particularly for the beginners. Thank you.
-6
votes
1answer
40 views

Cardinality of two power sets Question [closed]

Problem 5 (2 pts) Given two finite sets A and B with the cardinalities A= n and B = m. (a) What is the cardinality of the powerset P(A x B)? (b) How many functions is there from A to B?
1
vote
0answers
40 views

Optimal object in category? Metric, objective function on category objects. Optimization over category?

Is there notion about optimal object in category (that can be found by some algorithms, or - more importantly - that can be constructed (if unknown) by some algorithms), about metric and objective ...
0
votes
1answer
25 views

What is the complementary slackness conditions for a primal dual pair?

I'm trying to understand what exactly the complementary slackness conditions for a primal dual pair is and how it's calculated. I understand that we have a given linear programming problem. And that ...
1
vote
0answers
52 views

Levenberg-Marquart with Hessian and gradient

I am minimizing a sum-of-squared-differences function using the Levenberg-Marquardt method. The off-the-shelf numerical implementations I have have looked through (MATLAB, Numerical Recipes in C ...
2
votes
1answer
47 views

Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
5
votes
1answer
61 views

Concrete Mathematics - How is it that A(2n + 1) = 2A(n)?

This is might sound like a stupid question, and I'm pretty sure I know the answer to this question, but I'm not certain. Anyway, on page 14 of Concrete Mathematics, the author has just finished going ...
0
votes
0answers
76 views
5
votes
2answers
401 views

Programming and ZFC

Suppose I have a simple program that implements an algorithm (say depth-first search), written in a simple imperative programming language with the standard for loops, recursions, conditional ...
0
votes
1answer
25 views

what is the data byte encoded in binary Hamming code?

the problem I am presented with is a binary hamming code shown below: 011101000100, what was the data byte encoded and sent from this hamming code? and the solution is ...
1
vote
0answers
35 views

Additive combinatorics in Hamming weights of addition of numbers modulo $2^n$ with prescribed Hamming weight

I wonder if anyone could point me to a reference about the following type of combinatorics problem: Fix $n $. For an integer $k \in [n] = \{1, \ldots, n\}$, let $A(k)$ be the set of integers in $[0, ...
0
votes
1answer
26 views

How does state transition matrix works

Suppose I have a simple vehicle moving in 2D. The state vector for the vehicle is X=[x y vx vy ax ay], that is, it contains the position (x,y), the velocity (vx, vy) and the acceleration (ax, ay) of ...
0
votes
1answer
33 views

What do these propositions show?

I am going through some lecture slides and have come to something that I do not understand. I get the general idea of what he is trying to do but I am not sure how the propositions show this. The ...