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

-8
votes
1answer
110 views

is all math beyond arithmetic just advanced arithmetic? [on hold]

Is it true that at the bare-bones of all advanced math, its all just mostly arithmetic? In computer programming languages they are mostly constrained to arithmetic operators. I suppose this is ...
2
votes
0answers
25 views

Is there a method that determines an unknown permutation better than $\sum_{k=1}^n (k+1)/2$ steps on average?

Suppose I have a random permutation $s \in S_n$ that is unknown to me. However, suppose I can make a query where when I ask if $i$ is in the $j$th position in the permutation, I receive a yes or no ...
1
vote
0answers
17 views

Relative error in perturbed linear system

The linear system $A\vec{x}=\vec{b}$, where $$A_{(n\times n)}=\begin{bmatrix} 1 &-1 &\dots &\dots &-1 \\ 0& 1 &-1 &... &-1 \\ \vdots & \ddots &\ddots &...
1
vote
0answers
27 views

37 percent rule with second-chance-allowed

What is the math behind this? fragment from book Algorithms to Live By: The Computer Science of Human Decisions For example, assume an immediate proposal is a sure thing but belated proposals are ...
1
vote
3answers
58 views

Is there a mathematical difference between currying and partial application?

I know the following example doesn't make what I am saying rigorous, but hopefully it clarifies to some extent what I mean. For various computer implementations, dividing by 2 and multiplying by 0....
0
votes
0answers
40 views

How does the induction proof work in this solution?

Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf From my understanding and this thread, http://math.stackexchange.com/a/928412, we need 3 steps for that proof. ...
2
votes
2answers
45 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
0
votes
0answers
22 views

Consider the system S which can take n input parameters and each parameter can take on m values

(a) What is the maximum number of pairs a single test case for this system can cover? "I know that there are m^n different combinations in this example, but i'm unsure how many pairs a single test ...
1
vote
1answer
19 views

Order of growth rate in increasing order

This question is related to maths, so I post here. Actually it's a computer science question and I am facing this type of question while learning Design and Analysis of Algorithms, but we all know ...
3
votes
1answer
30 views

Difference sets without squares of Integers

I am trying to print numbers occuring in A030193 i.e Let S = set of square numbers; a(0)=0; a(n) = smallest m such that m - a(i) is not in S for all i < n. but I am unable to do it in better ...
1
vote
1answer
50 views

How to rewrite all the boolean operations using if-then-else operator?

Cited by Conditional Term Rewriting Systems: 1st International Workshop Orsay, France, July 8-10, 1987, p. 105 Additional Boolean operations are not needed, because all the usual Boolean ...
0
votes
1answer
21 views

What should be the expected error of a 4th order Runge-Kutta integration in a multivariable (non-linear) context?

I am writing a program where the user input $n$ variables, their initial values and differential equations. They may be non-linear. To find the value of the variables at a time $(t_0 + T)$, I use 4th ...
0
votes
0answers
14 views

Is there a simple way to describe all $O(n)$ algorithms given simple assumptions about the machine?

For example, can all $O(n)$ algorithms (where $n$ is strictly an integer) be described as: for k in 0..f(n): O(1)(k) where $f$ is a linear polynomial in $\Bbb{...
0
votes
1answer
22 views

How does $af\left(\frac{n}{b}\right) \leq cf(n)$ imply that $a^{i}f\left(\frac{n}{b^{i}}\right) \leq c^{i}f(n)$?

This is part of a proof for the third case in the Master Theorem in [CLRS], 3rd edition. $a\geq 1$, $b>1$ and $c<1$. Also, $f$ is a nonnegative function. It makes sense for polynomial ...
2
votes
2answers
43 views

Converting from base $x$ to base $y$

I'm trying to convert from base $x$ to base $y$, but am having trouble understanding why the following method only works when converting to base $10$. Take for instance the number $2132$ (base $4$). ...
1
vote
1answer
31 views

By what measure does the busy beaver function grow faster than any computable function?

It has been proven that the busy beaver function grows faster than any computable function. But I wouldn't think that speed of growth is well-defined. What is the definition? Is there some index?
0
votes
0answers
23 views

FFT butterfly diagram

I got confused in the FFT butterfly diagram. Can someone please help me understand it? If I have the vector $x = (-3, -2, -1, 0, 1, 2, 3, 4)$, and I want to apply FFT to it using the Butterfly ...
0
votes
0answers
8 views

Reassembling a matrix from submtrices in MATLAB

Here I have an image X defined as follows: X=imread('sunset.jpg'); So X is a matrix. Now I subdivide the matrix into $8\times 8$ submatricse as follows: $$B = mat2cell(X(:,:,1), 8*ones(1,...
4
votes
3answers
69 views

Are Pandemic chain reactions confluent? (vertex spills weight to neighbors at threshold, once)

Are resolutions of chain reactions order-independent in the board game Pandemic? More formally: You're given an undirected graph $G = (V, E)$ and a vertex weight $w \colon V \to \{0, \ldots, 3\}$. ...
0
votes
1answer
15 views

Passing variables into function (MATLAB)

I am creating a function that perform multiple regression in MATLAB. The function is created as function [Beta] = george_linreg(y,x1,x2,x3,....,xN). I don't ...
-1
votes
0answers
24 views

The relativised Church–Turing thesis

Barry Cooper states in his computability theory "The relativised Church–Turing thesis" on page 142 as follows: All formalisations of "$B$ computable from $A$" which are sufficiently reasonable ...
5
votes
2answers
101 views

Why does this pattern occur when using modular arithmetic against set of prime numbers?

I have been recently playing around with number theory and going through the project Euler problems. So I am very new to a lot of these things. I apologize for not knowing how to look up my answer. ...
-4
votes
2answers
72 views

As a computer science major, should I take differential equations, linear algebra, or both? [closed]

I've taken three semesters of calculus (altho the way my school does it, Calc III excludes Green, Stokes, Divergence/Curl Theorems and puts them in a class called Calc IV), and I've met my math ...
0
votes
0answers
23 views

How to get increasing int number based on two values

I did ask this question on SO but it seems this will find more appropriate audience here. I have a Google map where I am dropping markers based on events, this happens periodically and after 8 hours ...
0
votes
1answer
43 views

Find a path from $s$ to $t$ with smallest “bottleneck”

Let an undirected graph, $G=(V,E)$ with weights defined by the function $w:E\to\mathbb{N}$ and for each edge: $1\le w(e) \le |V|$. You are given two vertices: $s,t\in V$. Find a path from $s$ to $t$ ...
0
votes
1answer
21 views

Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees ...
2
votes
1answer
49 views

Shortest path from $s$ to $t$ in a graph with $5$ negative edges and no negative cycles?

Let $G=(V,E)$ a directed and weighted ($w:E\to\mathbb{R}$) and let $s,t\in V$. It is given that there are exactly $5$ negative edges and no negative cycles. Find the shortest path from $s$ to $t$. ...
0
votes
0answers
20 views

Find a set of vertices $U\subseteq V$ included in some simple cycle

Let $G=(V,E)$, an un-directed graph. Find an efficient algorithm to return a $U\subseteq V$, where $u\in U$ is in some simple cycle of $G$. So basically we've learned in class about the $low$ ...
3
votes
0answers
51 views

Hyperplane Problem

Given $M$ points in $\mathbb{R}^{N}$, (where $M$ is larger than $N$) I was wondering if there is an approximation algorithm to find a hyperplane which goes through the origin and also intersects as ...
1
vote
1answer
57 views

finite state machine transition table problem

I have the following question which im not able to do. I have done things with DFA/NFA's before but this is the first time ive seen a question like this, I have been looking for similar questions in ...
1
vote
0answers
43 views

What are some properties that the regular languages are not closed under?

In a standard Theory of Computation class, one learns a variety of closure properties of regular languages, including but not limited to: homomorphism, inverse homomorphism, union, complement, ...
1
vote
1answer
20 views

For every $v\in V$, determine if it belongs to some negative cycle in $G$

Let $G=(V,E)$ a directed graph with a weight function $w:E\to\mathbb{R}$. For every $v\in V$, determine if $v$ belongs to some negative cycle. Obviously we need to utilize Bellman-Ford algorithm for ...
2
votes
1answer
50 views

Alphabet on homomorphism

So I am trying to learn for an exam, and I found an exercise but without solutions and I can't really get behind the topic: Let $G = (V,E)$ be a connected graph with $v \geq 2$ Vertices. $P(G)$ is ...
2
votes
2answers
46 views

How to evaluate this infinite series arising from a CS problem? [duplicate]

$$\sum_{i=1}^{\infty}i\cdot((1-\frac{1}{N!})^{i-1}\cdot\frac{1}{N!})$$ where N is an integer and $N \geq 2$? I obtained this series from the following problem: Given a sequence of $N > 2$ unique ...
1
vote
2answers
29 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
0
votes
1answer
24 views

Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...
0
votes
0answers
40 views

Explaining something in Kraft-McMilan inequality proof

I was asked to present the Kraft-McMillan inequality, but I have trouble in understanding why in the following segment of the proof: there is a $$k\ge0 $$such that: $$ a^{-l_1}+a^{-l_2}+.....+(k+1)a^{...
3
votes
4answers
78 views

Does this thing I'm calling 'the operationalization of $x$' have an accepted name?

Given a set $X$ and an element $x \in X$, we can turn $x$ into a function denoted $\tilde{x}$ as follows: for any set $Y$ and any function $f : X \rightarrow Y$, define $$\tilde{x}(f) = f(x).$$ For ...
0
votes
1answer
19 views

Is there any approach to computer vision that doesn't make use of geometry?

I've long been interested in applying my background in functional analysis (especially wavelets) and other related areas to actually create something with "real world" value (not that I don't enjoy ...
0
votes
1answer
23 views

is this k-SAT or 3-SAT reduction?

On introduction to the theory of computation - 2nd edition by Michael Sipser, there's this question with the solution: Question: "7.31: In the following solitaire game, you are given an m x m board. ...
1
vote
1answer
42 views

pumping lemma - choice of partition

there is some thing in pumping lemma that I don't understand it. I think about application to prove irregularity of language. We have for each word (actual length) find partition: $xyz$ such that $\...
0
votes
0answers
23 views

Henkin theory follow complete

Assume that Γ is a a Henkin theory. For any two constants c,d, either $\Gamma \vdash c=d$ or $\Gamma \vdash c \neq d$. There are two constants a,b such that $\Gamma \vdash a\neq b$.Show that Γ is a ...
0
votes
1answer
29 views

Which one of the following is true of this relation?

Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set: a)Symmetric b)...
1
vote
1answer
97 views

Contradiction in Davis–Putnam–Logemann–Loveland (DPLL) Method?!

As we see on page $10,11$ and $12$ on Google Books we know about Unit Clause (UC) and Pure Literal (PL) in DPLL Algorithms. in the following example if assign value $0$ to variables is prior to ...
0
votes
0answers
12 views

Change In Time from Bidirectional Turing Machine to Standard Turing Machine

I'm reading this book on Computational Complexity and on page 37, it has a proof that a bidirectional TM $M$ running in $T(n)$ time can be converted to a unidirectional TM $\widetilde M$ running $4T(n)...
1
vote
1answer
28 views

Proving that $A+B - (A \cap B) = A \cup B$ for binary integers

I hope computing questions are fine here. I'm trying to show that for all binary numbers $A$ and $B$, $A+B - (A \cap B) = A \cup B$. It's confusing me firstly because I'm not sure what the "set ...
0
votes
1answer
13 views

How can I show a set B with 8 elements and two operations (huntington axioms)

How can I show a set B with 8 elements and two operations, such that the axioms of huntington for boolean algebra holds? I found it with set of 2 elemtnts. but can't understand how to start with 8 ...
0
votes
1answer
41 views

Help in proving inequalities in information theory-Kraft-McMillan

I was given a task of proving some inequalities that are related to Kraft-McMillan's inequalities, and i have been scratching my head for quite some time trying to prove it: $$ F(x)= \frac{1}{1-Q(x) }...
0
votes
0answers
19 views

Defining the right number of columns for a website interface

While working on a website interface (I'm a web developer), I came across an interesting problem. 1/ SOME DEFINITIONS In web design, for maintaining a coherent flow of the different elements of the ...
1
vote
1answer
24 views

Floating point numbers

In a certain computer represents numbers in base2, if the distance between 7 and the next largest floating-point number is $2^{-12}$. What is the distance between 70 and the next largest floating ...