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
14 views

Complexity of matrix inverse

I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination if $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
5
votes
5answers
7k views

What is the difference between discrete and continuous mathematics?

I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable. Examples are given stating that ...
1
vote
3answers
55 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....
1
vote
0answers
24 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
2answers
185 views

Largest number definable

If $a_n$ is defined as the largest integer definable using $n$ characters in some standard theory like PA or $Z_2$. Can we prove or disprove that there is some finite integer $k$, such that for all $...
0
votes
1answer
647 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
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
1answer
29 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 ...
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
18 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 ...
0
votes
2answers
2k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ---...
1
vote
1answer
453 views

Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$

$f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ I have attempted to solve it by letting $n = 2^k$ $f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$ Then set $S(k) = f(2^k)$ $S(k) = 3*S(k-...
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 ...
-2
votes
0answers
27 views

How does $af(n) < f(bn)$ imply that $a^i f(1) < f(b^i)$? [closed]

From CLRS 4.6.3 I don't understand how you can exponentiate functions in that way...
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
21 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?
4
votes
3answers
68 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\}$. ...
4
votes
2answers
1k views

Question regarding stack operation notation in PDA

I'm currently reading two books: An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz. Introduction to the Theory of Computation, 2nd Edition by Michael Sipser. What ...
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,...
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
vote
2answers
586 views

Can anyone explain the average case in insertion sort?

I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof Here is an example of insertion sort running a on a set of data ...
-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 ...
1
vote
1answer
1k views

How to use BFS or DFS to determine the connectivity in a non-connected graph?

How can I design an algorithm using BFS(Breadth First Search) or DFS(Depth First Search) algorithms in order to determine the connected components of a non-connected graph? The algorithm must be able ...
5
votes
2answers
100 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
1answer
422 views

Data Representation Question

A computer stores a number of $16$ bits word using floating-point arrangement. Given that the first bit is reserved for the sign and followed by $6$ bits for the exponent using biased form. The ...
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
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
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
48 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$. ...
19
votes
4answers
5k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
0
votes
1answer
19 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
1
vote
1answer
54 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 ...
0
votes
1answer
33 views

reductions from $SAT$ to $DSAT$ and $DSAT$ to $SAT$

can someone help me to prove or disprove the 3 claims about reductionsbetween $SAT$ and $DSAT$, where: $SAT=\{<\phi> | \text{$\phi$ is bolean formula in $CNF$ and there is an interpretation ...
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
50 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
4answers
144 views

integer sequences

Is anybody aware if there exists good computer software which tries to find, in a brute force manner, patterns in given finite sequences of numbers. For example , if you would give the Fibonacci ...
0
votes
1answer
453 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
2answers
99 views

Standard notation for the transform that turns a function $A \rightarrow (B \rightarrow C)$ into a function $B \rightarrow (A \rightarrow C).$

Suppose we're given sets $A,B$ and $C$. Then to each function $f : A \rightarrow (B \rightarrow C)$, we can assign another function $F : B \rightarrow (A \rightarrow C)$ by defining: $$F(b)(a) = f(a)(...
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, ...
7
votes
1answer
1k 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 ...
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
38 views

Fast Rational Bézier Surface Evaluation Problem

I am currently writing a NURBS ray tracer. What I do is convert the NURBS into rational Bézier patches and then perform the intersection test using Newton's method. To do this fast (the ray tracer ...
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 ...