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
vote
1answer
41 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
75 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
597 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!
0
votes
3answers
555 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
55 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
438 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
448 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
103 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
56 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
319 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
446 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
827 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 ...
2
votes
3answers
283 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
650 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
86 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
909 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
812 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
43 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
529 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
102 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 ...
3
votes
2answers
4k 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
138 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
776 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 ...
2
votes
1answer
220 views

Are linear shift register sequences corresponding to reciprocal polynomials equivalent?

I am looking into sequences generated by LFSRs (linear shift register sequences). I was wondering if sequences corresponding to reciprocal connection polynomials (that is, corresponding to shift ...
1
vote
1answer
68 views

Knapsack-like problem

I need to express an integer $n$ as the sum of integers $x_i$ below some threshold $t$, minimizing the number of $x$s, and maximizing a lower threshold $q$. $$\min_{\# x} \max_{q} : \sum_i x_i = n ...
2
votes
1answer
556 views

How to construct a grammar $G$ such that $L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\} $?

Construct a grammar $G$ such that $$L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\}$$ My attempt: I first constructed a grammar for the langugage $L(G_1) = \{ a^nb^m|n = 2m,m,n \ge = 0\}$, $G_1 = (\{ S\}, ...
5
votes
1answer
134 views

Maximal subset with rank $k$

I'm trying to solve the following problem for an algorithm I'm trying to develop and I couldn't find anything helpful in scholar google. Here is the question: Suppose I have a set of $N$ vectors ...
3
votes
1answer
130 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
4
votes
3answers
847 views

Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $ where $(f+g)(n) = f(n) + g(n) $ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
3
votes
0answers
47 views

Covering $n$ points with fewest disks with fixed radius $\epsilon$

The title says it all. I have a set of $n$ points in $\mathbb{R^{2}}$ and I am looking for an algorithm that tells me the fewest numbers of disks of radius $\epsilon$ that cover the set of $n$ ...
3
votes
3answers
637 views

Understanding recursive definitions of a language.

I am having difficulty understanding the recursive definition of a language. The problem asked how to write this non recursively. But I want to understand just how a recursive definition of a ...
1
vote
2answers
233 views

Determining function for recursive Fibonacci algorithm

I'm given a function: int fib(int n) { if (n == 0 || n == 1) return n; return fib(n - 1) + fib(n - 2); } from which I am supposed to determine a ...
1
vote
1answer
67 views

How to compute the complexity

1) If $a(n)=O(n^2)$ and $b(n)=O(n^3)$. Can someone tell me how to compute the computational complexity of $$ c(n)=\sum_{k=1}^{n}a(k)b(k) $$ What rules apply? I think it might be $O(n^6)$, but this ...
1
vote
2answers
43 views

Solving for x. Do I require iterations?

I have the following expression (used in a computer program): $$f(x)=b^{{k}^{ax}}$$ where $k$ is a constant and $a$ and $b$ are given. I need to calculate the distance from this curve to a point $P: ...
0
votes
1answer
44 views

Difficulty understanding some algebra done in a problem

The main problem is about computer science, trying to show that $f(x)=e^{x^Tx'}$ is of the form $\exp{\Big( \frac{||x - x'||^2}{2\sigma^2} \Big) }$, so it could be a kernel function. (see here for ...
1
vote
1answer
25 views

If I am checking for $s$ divides $n$ on the interval $S = [3, n-x]$, how large can I make $x$ to ensure I have verified $n$ is prime?

$\forall x \in \mathbb{Z}^+$, $x > 1 \longrightarrow x-2$ does not divide $x$ I have not yet proven this, which might be a good aside for my discrete math. One of my current assignments in ...
1
vote
1answer
82 views

Combinatorics question. Bit stuck.

Why can't there exist 5 5-digit binary numbers such that each pair has 1 or 2 digits in common? Another way to state the condition is that any pair has either 3 or 4 digits that are different.
0
votes
1answer
148 views

Cyclomatic complexity - understanding the paths issue

Also I know that cyclomatic complexity determines the number of linearly independent paths through the source code. An independent path=a path that executes at least one statement that the other paths ...
2
votes
1answer
88 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
8
votes
2answers
716 views

Common Lisp for mathematicians?

I am interested in learning Common Lisp. There seems to be a lot of material either for (experienced) programmers, or for people with no background, in programming or in mathematics. I was wondering ...
0
votes
1answer
111 views

Help with simplifying boolean functions algebraically

I have 2 boolean functions that I am having some difficulty solving algebraically. NOTE: ~ means NOT, & means AND, + means OR 1) $(\sim b~\&~\sim d)+(b~\&~\sim ...
1
vote
1answer
243 views

How to use a graph cut

I have to use a graph cut to create a binary image from a grayscale image. I can easily compute both energy functions $E_{data}$ and $E_{smooth}$. But after that, I don't know what is the next step. ...
1
vote
1answer
97 views

Difference between language is decidable and function calculable by turing machine

I'm trying to understand the difference between saying a language is decidable and a function is calculable by a turing machine. I must have understood something wrong, because for me it doesn't make ...
1
vote
1answer
150 views

Euclidean Division to avoid need for floating point arithmetic

In simple terms (that Google has been unable to provide the answer), is there an approach to dividing a whole integer by a quotient & remainder? As a specific example, ...
-1
votes
1answer
82 views

Limiting search space for efficient line matching [closed]

I have 2D line segments extracted from an image. So i know end point coordinates of them. also, i have some reference 2d line segments. Both line segments are now in vector form. comparing to ...
1
vote
1answer
176 views

Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ ...
1
vote
1answer
582 views

How do I find the number of bit strings with 3 consecutive 0s in a bit string of length n?

Say n is 8. How would I ever solve this problem? I've Googled around and searched this site but I haven't come up with much. I'm not even looking for the answer necessarily, just the process by ...