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

2
votes
2answers
164 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
2
votes
2answers
644 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
2
votes
1answer
96 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
2
votes
2answers
132 views

Minimum queens to reach $8 \times 8$ squares as a graph problem

A homework problem asks What is the minimum number of queens to reach all squares on a $8 \times 8$ chess board? We are expected to solve this by somehow casting the problem as a graph problem ...
1
vote
2answers
251 views

Huffman Encoding Proof Probability and Length

If the frequency of symbol i is strictly larger than the frequency of symbol j, then the length of the codeword for symbol i is less than or equal to the length of the codeword for symbol j. I ...
1
vote
2answers
3k views

Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.

Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then $$ $$ (i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$) $$ $$ (ii) if $a$ | $b$ and $a$|$bc$ for all integers $c$; $$ $$ (iii) if $a$ |$b$ and ...
1
vote
1answer
1k views

Show $\{0^m1^n | m \neq n\}$ is not regular

I'm going through Michael Sipser's Introduction to the Theory of Computation, and in one of the exercises we are asked to show that $\{0^m1^n | m \neq n\}$ is not a regular language (i.e. is not ...
1
vote
1answer
1k views

How to fit non-linear matlab data?

I'm working on a problem in scientific computing namely fitting data to this equation $c(z) = 4800 + p_1 + p_2 \cdot z/1000 + p_3 \cdot e^{ -p4 \cdot z/1000}$ The data is in a background question ...
1
vote
2answers
136 views

How can the following language be determined in polynomial time

I'd love your help with understanding why the following is decidable and can be determinate in polynomial time ($L \in P$). $L=\{(\langle M \rangle,w)|M$ is a Turing machine with Q states and one ...
0
votes
1answer
54 views

Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

$\displaystyle T(n) = T\left(3n\over4\right) + T\left(n\over6\right) + 5n$ is not in the proper form for the Master theorem so I can't really apply it. The only idea I had was changing the ...
0
votes
1answer
43 views

Expected number of fragments generated by a random binary space partition (should be plain combinatorics)

Let $S$ be a finite ordered set of non-intersecting finite line segments in the plane. Let's randomly shuffle the elements of $S$ such that each possible permutation of those elements has equal ...
0
votes
1answer
46 views

Make individuals distinct

I am trying to construct an ALCQ knowledge base (KB) for some sentences. Here is what I have: Abox (Yiannis is a person and he drinks only one kind of a coffee, frappe): Person(YIANNIS) $\forall$ ...
0
votes
1answer
54 views

Did I do this big-Omega proof correctly?

Prove or disprove: 6n^3 – 4n^2 + 3n +2 is in Ω (5n^3 – n^2 + n +1). So I'm not sure if I did this right or not, any pointers or the correct steps would be helpful Ǝc ∈ ℝ+, ƎB ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ ...
0
votes
2answers
289 views

the strings of five decimal digitis

My question is : Consider strings of five decimal digits, such as 00147, or 99999. In each case below, what is the number of such strings satisfying the given property? (a) The string has no repeated ...
0
votes
1answer
103 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
0
votes
1answer
126 views

How to approach this Secret Sharing scheme?

Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they ...
0
votes
1answer
307 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
0
votes
3answers
84 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
0
votes
2answers
290 views

Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. ...
0
votes
1answer
132 views

Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov ...
0
votes
1answer
318 views

Comp Sci Math; Hamming Distance

I've been tasked with this question but I have no idea how to answer it. What is the maximum possible hamming distance between two points from level i in a n-cube?
-3
votes
1answer
306 views

How to obtain $\operatorname{lcm}(a_1,a_2,a_3,\ldots,a_n)\%1000000007$ [closed]

The problem is that you have $n$ numbers whose value can be in range $[1,100000]$. The task is to find the LCM of all these numbers. Now the answer can be very large so it should be printed MODULO ...
31
votes
6answers
3k views

Simple “real life” NP-hard problems?

There are many proofs lying around that games like Lemmings or Sudoku or Tetris are NP-hard (generalized version of those games, of course). The proofs, as I recall, are not difficult but not simple ...
18
votes
4answers
4k 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: ...
17
votes
2answers
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
15
votes
4answers
11k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
10
votes
2answers
883 views

What is the best way to self-study GAP?

Background: This year I'll do another Group Theory course ( Open University M336 ). In the past I have used Mathematica's AbstractAlgebra package but (although visually appealing ) this is no longer ...
5
votes
2answers
2k views

Learning Proofs (for Computer Science)

Harvard's math curriculum, for freshmen, is divided into 4 classes beyond the BC Calculus level, Math 21, 23, 25 and 55. Math 21 is your classic plug-and-chug multivariable calculus and linear algebra ...
5
votes
3answers
27k views

What is the 3SAT problem? [closed]

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
31
votes
8answers
4k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
18
votes
2answers
23k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
12
votes
5answers
2k views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
12
votes
3answers
873 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
10
votes
2answers
870 views

Applications of Geometry to Computer Science

How is differential geometry (or any type of theoretical math) being used in computer science? Any research I have done on this topic leads me to some sort of applied math concept. I know that there ...
8
votes
4answers
578 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
7
votes
1answer
504 views

Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a ...
6
votes
3answers
851 views

Is learning haskell a bad thing for a beginner mathematician?

Haskell is a programming language which uses some concepts from category theory like functor, monad, etc. My question is: Learning intuitive concepts about category from Haskell will ruin my intuition ...
7
votes
1answer
9k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
5
votes
0answers
63 views

Where can I learn more about the “else” operation / “else monoid”?

(The set of natural numbers $\mathbb{N}$ starts at $0$ for me.) Let $X$ denote a set, and define $X_\bot = X \uplus \{\bot\}.$ Let $\mathbf{else}$ denote the binary operation on $X_\bot$ defined as ...
14
votes
6answers
4k views

The Practical Implication of P vs NP Problem

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it. Suppose that we can prove all questions that can be ...
12
votes
3answers
357 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
7
votes
8answers
11k views

Why does a complete binary tree of $n$ leaves have $2n-1$ nodes?

A complete binary tree is defined as a tree where each node has either $2$ or $0$ children. A variety of sources have described the relation between nodes and leaves to be $2n-1$ where $n$ is the ...
6
votes
1answer
148 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
3
votes
0answers
98 views

Computability and continuous real functions

I have found somewhere the following statement: "Every computable real function has to be continuous," but I'm not able to prove it and the "proofs" that I found in some blog posts don't seem ...
1
vote
1answer
38 views

Is $L_1$ context free language?

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L ...
10
votes
3answers
6k views

fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ large) If I am interested in the solution for only one of the unknowns, what are the best approaches? for ...
9
votes
3answers
11k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
7
votes
4answers
1k views

Does DTIME(O(n)) = REGULAR?

(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to ...
6
votes
4answers
12k views

Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
5
votes
1answer
360 views

Matrix Chain Multiplication?

The following are questions about using dynamic programming for matrix chain multiplication. Pseudocode can be found in the Wikipedia article on matrix chain multiplication. 1) Why is the time ...