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
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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: ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-2
votes
0answers
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: ...
8
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
0
votes
2answers
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$. ...
-1
votes
0answers
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; ...
12
votes
1answer
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 ...
-1
votes
0answers
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?
2
votes
0answers
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 ...
1
vote
0answers
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. ...
-1
votes
1answer
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.
1
vote
1answer
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 ...
1
vote
2answers
31 views

Find particular pair of values that satisfy equation

I think this is might be a fairly simple problem, but I can't for the life of me think of a way to approach it. In this equation, for a given $x$ and $y$, with $x,y,a,b$ non-negative integers: $x2^a ...
0
votes
1answer
45 views

Algorithms - Finding Clique of size n in a Graph

I have the following statements (NOTE: $\bar x$ means the complement of $x$): $(x_1 V \bar x_2 V x_3) ∧ ( \bar x_1 V x_2 V x_3) ∧ (x_1 V \bar x_3) ∧ (x_2 V \bar x_3 V x_4)$ I need to do the ...
0
votes
1answer
396 views

checking boolean logical equivalence

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?
1
vote
1answer
42 views

What formal systems are various programming paradigms based on?

I heard that functional programming paradigm is based on lambda calculus and combinatory logic. If I am correct, lambda calculus and combinatory logic are formal systems. What formal systems are ...
0
votes
2answers
55 views

prove that a polynomial is lower bounded

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - ...
0
votes
1answer
44 views

Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: $$\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ ...
1
vote
1answer
77 views

Computational complexity of solving linear diophantine equations?

Is there any good complexity upper bound for checking satisfiability of a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$? I found some estimate on computing the Smith Normal Form $N$ such that ...
1
vote
0answers
19 views

ternary string that contains only $0's$, $1's$, and $2's$

A string that contains only $0's$, $1's$, and $2's$ is called a ternary string. (a) Find a recurrence relation for the number of ternary strings that do not contain two consecutive $0's$. (b) What ...
0
votes
0answers
21 views

What does “symbolic computation” mean in this context?

From Wikipedia In computational mathematics, computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development of algorithms ...
1
vote
0answers
31 views

What is the root of first class object in programming languages?

What is the root of "first class object" of programming languages? (Also see https://en.wikipedia.org/wiki/First-class_function, and ...
0
votes
0answers
18 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) ...
1
vote
3answers
278 views

Rooted Tree and Greedy Algorithms

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send ...
0
votes
0answers
12 views

Minimum number of pages in a B-Tree of order n?

How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages?
0
votes
1answer
19 views

Time complexity for loops

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. int j = 1; int n = any; ...
1
vote
4answers
56 views

How to check if $n!$ is $ O(2^n)$

How can I check if $n! \in O(2^n)$? The definition of $f$ being $O(g)$ is $f(n) \le c g (n)$, where $c>0$. So it would mean $n! \le c 2^n$. What is the clearest way to solve this? (As I am ...
0
votes
1answer
38 views

Hash functions - show how to find collisions

I'm currently trying to solve this exercise (sorry for image, it's for the notation and I'm not allowed yet to post images directly): I have read the exercise question a lot of times and I think I ...
0
votes
0answers
17 views

Balancing integer bins to have a certain summation

Assume that we have bins $$ B_1, B_2 ..., B_n $$ There exists integer bin values $$ V_1, V_2 ..., V_n $$ Let $$ Total_{V} =\sum_{i=1}^{n} V_i$$ There then exists weights ( $ W $) of each bin to ...
7
votes
1answer
986 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
2
votes
3answers
2k views

An algorithm to convert float number to binary representation

I want to know the algorithm of converting a given float (e.g, 3.14) to binary in the memory. I read this wikipedia page, but it only mentions about the conversion the other way. Let me quickly give ...
-1
votes
0answers
4 views

Minimizing the distance between two set of vectors such that the angle of both set is equal

Suppose I have two set of vectors K1,I1 and K2,I2 forming a surface S1 and S2 respectively in R2 or R3. The angle between K1 and I1 is T1 and K2 and I2 is T2 respectively. The goal is to minimize the ...
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
9
votes
2answers
3k views

Fast Matlab Code for hypergeometric function $_2F_1$

I am looking for a good numerical algorithm to evaluate the hypergeometric function $_2F_1$ in Matlab (hypergeom in Matlab is very slow). I looked across the ...
0
votes
0answers
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 ...
1
vote
1answer
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". ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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?
1
vote
1answer
27 views

Minimum spanning tree of graph? proof by contradiction?

this is not a homework but I need to understand it before my exam tomorrow. How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are ...
0
votes
1answer
27 views

Implementation of Heap (ADT) using Array Vs. LinkedList

In data-structure course , I need to implement a binary heap with the following time - complexity requirements: Find Max - O(1) Insert - O(log n) Delete Max - O(log n) Now I thought to implement ...