# Tagged Questions

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

13 views

### Applying mathematics in computer graphics [on hold]

I'm currently a third year mathematics student interested in the mathematics of computer design (games, mostly). I have to conduct a research project with a professor at my school for my ...
130 views

### Can Hamiltonian Circuit be solved in Quasi-polynomial time?

Consider a graph $G$. Let’s assume it has a Hamiltonian Circuit . Now, we divide the graph $G$ in to $x$ subgraphs $G_1, G_2, ….. G_x$ in a way such that $|G_i|$ is the power of a prime number where ...
1k views

### Radial Basis Function and Neural Networks

I need a simple explanation about what is the radial basis function? And what is the relationship between the radial basis function and neural networks? And are there any simple examples to explain ...
46 views

### What does double bracket with a number in index mean? [on hold]

I am reading a paper (http://user.it.uu.se/~yi/pdf-files/ecrts12.pdf) and I do not understand one of the notation. The notation is an expression within double brackets and there is a 0 in index : It ...
27 views

### Solve $T(n)=2T(n/2)+\log n$ with $T(1)=1$

Solve$$\begin{cases}T(n)=2T(n/2)+\log n\\ T(1)=1\end{cases}$$ I tried to use the master theorem but it didn't work, so I used the trees methode ...
1k views

### Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
19 views

### How to properly determine observations related to a Hidden Markov Model alike problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
23 views

### Algorithm to find password from hash value

I'm currently trying to solve this exercise (sorry for link to image, but there's a bit text): http://i.imgur.com/ETaCK0H.png But there's a few things in the exercise I don't understand. For ...
29 views

### Course or book - Math Foundations in CS

I want to improve my math skills, now I'm trying to find good route for this purpose. I'm using Khan Academy, and recently found "CS103 - Mathematical Foundations of Computing" course which looks good ...
53 views

### What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
295 views

### What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
323 views

### Belief Propagation Algorithms for Graphical Models with Cycles?

Belief propagation algorithms cannot solve for the probabilities of a cyclic graphical model; they only work for acyclic graphical models. For undirected graphical models (for example Markov random ...
77 views

### How to Calculate Values from Incoming Messages? - Evidence Propagation in Bayesian Network

I'm currently trying to wrap my head around evidence propagation in bayesian network (simple tree propagation) but I'm having trouble finding information about the process. As an example, let's take ...
41 views

### Bit increase when averaging?

I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers. For example, thease values where $N = 4, B = 4$. ...
6 views

### Scilab Programming Question on systems of non-linear equations [closed]

I am new to Scilab. Can anyone please help with the following tutorial question? I am drawing a total blank and don't know where to start. "Consider the following non-linear system of equations: g(x; ...
256 views

### How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
22 views

### What are “bits” when the base is > 2? [closed]

Is a bitshift operator (f(0)=1) generalizable to systems with base n>2? Because it is a trick to shift the bits n steps to the left if we multiply by 2^n, is that generalizable to any base b^n?
16 views

### Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
42 views

### Arc length using bisection error - root finding methods.

Apologies if this is poorly formatted - it is my first time posting a question. I'm trying to find evenly spaced arc lengths along a function (in this case a sinusoid) using the bisection method. ...
35 views

### If NP-complete, prove another is also NP-complete

I've been trying to work on this problem but I don't really know where to start and can't find any resources online. Would it be possible for someone to guide me through step by step.
18 views

### Hilberts tenth problem over $\mathbb R$ with coefficients in $\mathbb Q$

Consider the following decision problem: Given: An equation $f(x_1, \dots, x_n) = 0$ where $f(x_1, \dots, x_n)$ is a polynomial with variables $x_1, \dots, x_n$ and coefficients in $\mathbb Z$. To ...
31 views

11 views

### Is the Antikythera Mechanism Turing-Complete?

Is the following Turing-complete? https://en.wikipedia.org/wiki/Antikythera_mechanism As in, it possible to perform all of the operations of a Turing-machine, albeit with finite memory, with this ...
41 views

### Group theoretic interpretation of 1's and 2's complement

I've been studying 1's and 2's complement, but they still seem mysterious to me even though I completely understand how to manipulate them. They seem like cute tricks that somehow just "work out". ...
22 views

### Encryption - show probability for obtaining specific bit

Assume a person A encrypts a message which consist of the bits m1, ..., mn. The person is using the one-time pad algorithm. Another person B intercepts the ciphertext and we suppose he knows that mi ...
10 views

### Does the Method of Compliments also work for (non-integers)?

I have only ever seen Method of Complements applied to integers, never non-integers (most notably in the field of modern programming) However curiosity got the better of me, and I was wondering if ...
34 views

### Big O for factorials

Hello I have trouble proving:$$(n+1)!\notin O(n!)$$ My first step is the following: $$(n+1)!-cn!\le0$$ Can you please help me with the next step?