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

6
votes
2answers
1k views

Mathematical way of determining whether a number is an integer

I'm developing a computer program, and I've run into a mathematical problem. This isn't specific to any programming language, so it isn't really appropriate to ask on stackoverflow. Is there any way ...
0
votes
0answers
46 views

Deriving the fundamental equation relationship

I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...
5
votes
4answers
761 views

Is the set of non finitely describable real numbers closed under addition and squaring?

Is the set of non finitely describable real numbers closed under addition and squaring? If so, can someone give a proof? Thanks.
8
votes
3answers
4k views

Simplifying Catalan number recurrence relation

While solving a problem, I reduced it in the form of the following recurrence relation. $ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $ However ...
1
vote
2answers
59 views

Confusion related to P and NP problems

I have this confusion related to P and NP problems. Why is P a subset of NP? I didn't get it. P problems can be solved in polynomial time. However, NP problems cannot but only verify if a solution is ...
1
vote
1answer
138 views

Minimum number of moves to convert a list of any integers into a permutation

Given a list of integers of size n, how to find the minimum number of moves to convert it to a Permutation? In one move, we are allowed to decrease or increase any element of the list by one. For ...
0
votes
4answers
98 views

What algorithms are used to determine the difference of two squares?

I'm taking a discrete math class this semester. The professor said that by the end of the semester he wants us to have an understanding of RSA encryption. One thing that we have gone over in class is ...
1
vote
1answer
112 views

NP-Complete Problem

Consider the following NP problem called A: its input is a graph G and a number k > 1. Its witness, if there is one, is a pair $S;T$ of sets of points in $G$ such that S is an independent set of size ...
3
votes
1answer
149 views

finding the minimal property of a graph

While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs. My question is ...
2
votes
2answers
96 views

Weird series of numbers - any logic in it?

I have the following table where the first column is an index, the second column has all the powers of 2 raised to i. I can't understand what does the third column represent. It should be something ...
3
votes
2answers
135 views

What exactly is a FLOP?

I know that is a "FLoating-point Operation" but,what exactly mean this!? Can anyone make me a mathematical example of a FLOP? For example, is $\sqrt{2}$ a FLOP?
2
votes
1answer
45 views

to check the required property of a given graph.

Can a graph be self-centered if it contains a vertex of degree one. The simplest counter example that came to my mind is Path. But how to prove the statement if we consider any graph with a vertex of ...
0
votes
1answer
172 views

The following Post Correspondence Problem unsolvable?

I have been trying to play around with the following Post Correspondence Problem for about one hour now with no success, which leads me to believing the following problem is unsolvable. Is the ...
2
votes
2answers
33 views

Get A⊕(B+1) from A⊕B

I have numbers A,B,C.D. (⊕ is XOR) C = A⊕B D = A⊕(B+1) Is there any way to get D from C, when I do not know A and B? How? Thanks for help!
6
votes
2answers
109 views

Find the most vertical line in a point set in $O(n \log n)$ time

Input: a set of $n$ points in general position in $\mathbb{R}^2$. Output: the pair of points whose slope has the largest magnitude. Time constraint: $O(n \log n)$ or better. Please don't spoil the ...
2
votes
2answers
47 views

finding signs of 3 numbers

This is slightly more of a coding problem than a math problem but I think it is still relevant. So let's say I have 3 numbers A,B,C and I can only call a given function if two are negative and one ...
0
votes
1answer
118 views

Array resize problem

I need help with this problem if anyone can help. Suppose you have an empty array of size $s$. Then you keep inserting elements in it. But before you insert an element, if the array is filled, then ...
0
votes
1answer
37 views

Resizing array problem

I need some help with this problem. Suppose you have an array of size $n$ where $n = 4^i$ for some $i \geq 0$, with initially $n$ elements in it. Let $m$ be the current number of elements in the ...
1
vote
0answers
50 views

Mean matching size

Suppose there is a simple bipartite graph $G(X,E,Y)$, where $|X|=n_1$, $|Y|=n_2$, $|E|=m$. The edges $E$ are chosen uniformly at random. The question is what is a mean value of the size of the ...
4
votes
1answer
100 views

Which categories correspond to the untyped and typed lambda calculus?

Simply typed lambda calculus is the internal language of Cartesian Closed Categories. What category has its internal language the typed lambda calculus? And the untyped lambda calculus? Can we in ...
0
votes
1answer
97 views

Questions about DFA with Sigma* exiting arrow and RE

Assume Sigma* contains all english alphabet chars. Then in my DFA, I have an exiting arrow of Sigma* and another exiting arrow of "a"(symbol from the alphabet) from one state. Will this be a valid ...
3
votes
1answer
102 views

to check a property of square of a graph

I am trying to work out a problem. Given a self-centered graph, is the square of the graph also a self-centered graph? I tried numerically on few graphs given in ...
2
votes
1answer
79 views

How is naive CLIQUE algorithm polynomial time?

I am reading Introduction to Algorithms 3rd for my CS course. Just before theorem 34.11 on pg 1087, it says the running time of the naive algorithm to try all k-subsets of $V$ is ...
0
votes
1answer
94 views

Doing research on Google Matrix and PageRank algorithm

I'm doing research on Google Matrix and PageRank algorithm. In a paper, there are terms that I'm unaware of, such as stationary distribution, stochastic matrix, convex combination, markov matrix, ...
1
vote
1answer
47 views

Specify conditions for $\alpha$ so that the iteration $x_{n+1} = x_n - \alpha f(x_n)$ converges to root of f.

Specify conditions on $\alpha$ so that the iterative process $x_{n+1} = x_n - \alpha f(x_n)$ converges to root of f if started with $x_0$ close to the root. It is suggested that the proof should ...
3
votes
2answers
79 views

why is it necessary to show NP in order to show NPC?

I am reading Introduction to Algorithms 3rd for my CS course. Lemma 34.8 says to prove a language $L_2$ NP-complete: If $L_2$ is a language such that $L_1 \le_P L_2$ for some $L_1 \in$ NPC, then ...
2
votes
2answers
661 views

Reference request - Any suggestion for good Abstract Algebra pdf for computer science?

I'm a computer science student and I'm starting to learn Abstract Algebra next week. I'd like to get a suggestions for good PDF book about Abstract Algebra. Thanks!
1
vote
3answers
671 views

Is indistinguishability an equivalence relation?

Let x and y be strings and let L be any language. We say that x and y are distinguishable by L if some string z exists whereby exactly one of the strings xz and yz is a member of L; otherwise, ...
4
votes
1answer
57 views

Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always ...
1
vote
0answers
33 views

Lower bound on building heap.

A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO as following THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only ...
3
votes
2answers
487 views

Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
9
votes
5answers
458 views

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction. I get the intuition behind this question. Clearly, the given function isn’t even growing ...
1
vote
1answer
107 views

Applying substitutions in lambda calculus

For computing $2+3$, the lambda calculus goes the following: $(\lambda sz.s(sz))(\lambda wyx.y(wyx))(\lambda uv.u(u(uv)))$ I am having a hard time substituing and reaching the final form of $(\lambda ...
1
vote
1answer
100 views

Can kCNF have less than k variables per clause?

An example given by my prof in her notes: The following formula is in 4CNF: $(w\vee y\vee \neg z)\wedge(w\vee\neg x\vee z)\wedge(w\vee\neg x\vee \neg y\vee z)$ I originally thought that maybe ...
23
votes
12answers
3k views

How is the set of all programs countable?

I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish ...
1
vote
2answers
376 views

set theory subsets and inheirtance in Java

I started reading Concepts of Modern Mathematics and naturally, I came across set theory. I was wondering if someone could clarify my understanding for subsets by way of inheritance in Java or any ...
1
vote
1answer
506 views

Basic Maths question regarding the selection sort formula.

I'm training to be a software developer and use Stack Overflow a lot, but I'm afraid some basic Maths has gotten in my way. I apologise in advance for a question that may be too easy to be posted here ...
6
votes
1answer
991 views

Optimal Yahtzee (Dice roll) decisions: Probability and weighting choices

I'm a senior in computer science, and I have a hobby of taking on little projects that I find interesting. My current one is a Yahtzee optimal play solver. One would enter their current roll, and it ...
3
votes
3answers
359 views

Enumerating Rooted labeled trees without Langrange inversion formula

I am wondering how to enumerate rooted labeled trees without the Langrange inversion formula. Because each tree is a collection of other trees, the recursive generating function becomes $$C(x) = x + ...
14
votes
2answers
1k views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
1
vote
0answers
43 views

Good reference for co-groups, perspective of co-algebra applications

There are lot of applications of state transition systems STS (computer science, planning problems in robotics and so on) and lot of algorithms are devised, but the mathematical background for STS is ...
0
votes
1answer
89 views

What is a basic definition for Big Oh, and it's component parts?

this is a question that somewhat straddles the boundaries of computer science (data structures and ). I'm mostly fine with data structures, until encountering big oh notation.. at which point my head ...
0
votes
1answer
1k views

Proving the relative error of division.

The problem says to show that the relative error for division on a computer is $$Rel(\frac{x_{A}}{y_{A}})=\frac{Rel(x_{A})-Rel(y_{A})}{1-Rel(y_{A})}$$ $$\approx Rel(x_{A})-Rel(y_{A})$$ provided ...
2
votes
1answer
981 views

The time complexity of finding a neighborhood graph provided an unordered adjacency matrix

Imagine I have an unordered adjacency matrix for some graph $G$ with a set of vertices $V$ and a set of edges $E$. I would like to find a subset of edges that determines a $k$-hop neighborhood graph ...
0
votes
1answer
44 views

How to compute the number of sequential words in a phrase and why the formula is strange?

Say I have a sentence consisting of n words. That word can be I like horse and I also like cats and kitten. I want to compute the number of sequential words. For example, I, Like, Horse, ...
5
votes
3answers
599 views

What are some interesting coding projects (doable in Java) that relates to group theory?

I would like some ideas of possible programs I can write in Java that involves some computational aspects of group theory. My only ideas so far is to write a program that computes the product of two ...
0
votes
1answer
103 views

Decimal expansion in logic Church thesis

How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable? I have some idea in terms of Cantor's diag. argument, but I need to ...
5
votes
2answers
5k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
1
vote
1answer
143 views

Proof of the pumping lemma for Context-Free Languages

I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows: If $A$ is a context-free language, then ...
2
votes
2answers
855 views

Master Theorem $T(n) = 4T(n/2) + \lg n$

In class today, we did the following problem: $T(n)=4T(n/2) + \lg n$ So by notation in CLRS, we have $a = 4$, $b = 2$, $f(n) = \lg n$. Thus, $n^{\log_b a} = n^2$. My algorithm lecturer claimed that ...