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

Number of subtrees of a tree

Define a subtree to be any connected subgraph of a tree. Prove that the number of subtrees of a complete binary tree is not polynomial in the number of nodes. Give an example of a class of trees ...
2
votes
2answers
152 views

Computing all simple paths in a distributive lattice in parallel.

(All arrows point downward.) For the poset $P: 2 < 4, 1 < 3, 1 < 4, 3 < 5$ we get the graph: A linear extension of this poset is $1,2,3,4,5$. "A downset or ideal of a poset $(P, ≤)$ is ...
2
votes
0answers
48 views

Induction Problem ($n^2 ≤ 2^n$) [duplicate]

So I have this induction problem: $$n^2 ≤ 2^n \;\text{ for } \; n ≥ 4$$ I know the base case is ($n=4$) which checks out. I know the hyp is ($n=k$) giving $k^2 ≤ 2^k$. However, I am getting ...
0
votes
2answers
58 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
1
vote
1answer
95 views

unary propositional connective

Let F be a unary propositional connective, such that F(p) is always false, regardless of the value assigned to p. i. Give the truth table for F. (Hint: how many lines does it have?) I have: p | ...
0
votes
1answer
175 views

Propositional Logic - induction

(a) Let C be the set {∧,∨} of propositional connectives, and let P be any set of propositional variables. i. Suppose that: φ is a well-formed formula that uses only connectives in C and variables ...
0
votes
1answer
58 views

Language equivalence - manipulation of languages with Star operator

Why is this always true $(A^{*} \cap B^{*})^{*} = (A \cap B)^{*}$ ? $A^{*} = \{ x_{1}x_{2}...x_{k}| k \ge 0$ and each $x_{i} \in A\}$, and similarly for B. Assuming A and B are any languages i.e. ...
2
votes
1answer
37 views

“Kolmogorov complexity with time”

Kolmogorov complexity of object is minimal length of program that print this object. 1)Kolmogorov complexity is not a computable function. 2)If there is little program that print object for billion ...
3
votes
2answers
196 views

Simple problem whose approximation ratio is still open.

I am preparing for a talk on "Approximation Algorithms", aimed at undergraduate students. In order to motivate the topic, I want to give them an example of a problem which is easy to describe and has ...
4
votes
2answers
121 views

Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and $s$ has length $i$}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
1
vote
0answers
26 views

What do you call a mildly-context sensitive grammar in which the LHS must appear in the grammar spec?

For instance: $$ S \rightarrow aAbAb \\ aAb \rightarrow AAa \\ A \rightarrow Aa | a $$ $aAb$ is alright to have on the left-hand side since it occurs directly in the grammar spec. Further indirectly ...
1
vote
1answer
107 views

Signed binary arithmetic

I'm having trouble with a fairly simply concept, signed binary arithmetic. I know how to do 1's and 2's complement, convert from binary, decimal, octal, and hex, multiply and add bytes and bits, but ...
1
vote
1answer
140 views

Number guessing game with expensive answers

I play the number guessing game with positive integers and a known constant upper bound. Every time I make a guess about the number I have to pay 1 dollar but if my partner answers 'Yes' I have to pay ...
3
votes
1answer
195 views

What Is The Difference Between The Maths That Physicists Use And The Maths On A Typical Mathematics Degree

Physicists are widely respected for using and sometimes even inventing mathematics yet physicists study Physics which is a subject in its own right. So surely someone studying physics spends less ...
2
votes
0answers
124 views

How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
0
votes
1answer
155 views

Arithmetic Hierarchy problems

Is $\Sigma^{0}_n$ closed under intersection? I think yes m I correct? Let $L_1$ be an $\Sigma^{0}_1$ complete language, and $L_2$ be a $\Pi^{0}_1$ complete language, such that $\emptyset \neq L= ...
3
votes
1answer
51 views

A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
-3
votes
1answer
478 views

Is solving the PvsNP example question a solution to PvsNP?

This example question was created by the claymath institute. The PvsNP question states, suppose the dean leaves you with a task to house a group of 400 students inside dorms. But there is only enough ...
4
votes
3answers
92 views

Does the set of computable numbers get bigger if we strengthen our language?

This might be a silly question, but can one given an example for a number, which is not computable? I want to get a mental picture of what these real numbers are, which you can't write down. At the ...
3
votes
1answer
51 views

Can this simple functional language be simplified further without losing any computational power?

Here is a definition of a very simplistic programming language (it is not Turing complete). Input to a function is any natural number. The following functions are primitive to the language: ...
1
vote
2answers
352 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
3answers
137 views

How long time will it take to sort $10^6$ numbers and $10^9$ numbers for two algorithms if they take the same time to sort $1000$ numbers?

Question We are given two sorting algorithms. The running time of Algorithm $1$ is $O(n^2)$ while Algorithm $2$ has running time $O(n \cdot log (n))$. Assume that Algorithm $1$ and Algorithm $2$ take ...
-4
votes
1answer
222 views

How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
0
votes
1answer
582 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 ...
3
votes
1answer
69 views

How to take one's complement of a positive integer?

Of course we can do that by converting the number to binary and then converting it back to decimal, but to do that directly in decimal?
2
votes
2answers
98 views

Boolean Algebra-Simplification Assistance Needed

I have to show that (!(P.Q) + R)(!Q + P.!R) => !Q by simplifying it using De Morgan's Laws. Here is what I did but I'm not sure it's right. (!(P.Q) + R)(!Q + P.!R) => !Q (!P + !Q + R)(!Q + P.!R) ...
6
votes
2answers
2k views

Fast Matlab Code for hypergeometric function $_2F_1$

I am looking for a good numerical algorithm to evaluate the hypergeometric function $_2F_1$ in Matlab (hypergeom in Matlab is very slow). I looked across the ...
1
vote
1answer
131 views

How to perform divide step of in-place Quicksort?

I have an example of quicksort, it says like this: The divide step of in-place quicksort works by showing how the following list would look after performing the division with the first element as ...
0
votes
2answers
83 views

Generating a random number of higher range

I had a discussion with my friend about writing a function (a computer program) which generates 9 values randomly using a random number generator which generates 4 values, i.e I have a PRNG rand(4) ...
3
votes
2answers
479 views

Masters in Numerical Analysis?

My interests in CS are fairly narrow; I'm mainly interested in numerical analysis and numerical methods for solving differential equations. However, during my undergrad I mainly focused on other, more ...
1
vote
1answer
41 views

Can convex hulls contain duplicate points?

Given 4 vertices: (-3.2, 0.8), (-3.2, -0.8), (3.2, -0.8), (3.2, 0.8) A function which I did not write, and given vertices, will return the points of a convex hull. Using the points above, it ...
1
vote
1answer
75 views

How to determine which encryption system is being used?

I came across this question in a local contest. I was not able to solve it at that time. Also, no solution was provided. I was wondering if someone can help me to understand how to tackle this kind ...
2
votes
0answers
129 views

Modular Inverse over some given finite field. Which method is more efficient?

I'm trying to do division in some given finite field (let's say mod p). I have 2 Python methods here that are currently doing that, but I'm not sure which is better or if 1 or both is simply wrong. ...
1
vote
0answers
52 views

A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
2
votes
1answer
135 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
1
vote
3answers
229 views

Understanding mathematical set theory syntax

While reading a paper, I came across some operators and syntax that I am not familiar with, and I'm not sure how to google to find the definitions or explanations I am looking for. For reference, I ...
2
votes
1answer
159 views

Is there a computer programm or CAS (maybe GAP?) that can calculate with projective (indecomposable) A-modules (A is a finite dimensional k-algebra)?

I have the following question(s): I have an "Algebra-With-One" $R$ as a subalgebra of a full matrix algebra in GAP. Furthermore, I have 5 primitive orthogonal idempotents $e_1,...,e_5$, which sum up ...
1
vote
1answer
178 views

Create a formula from a set of number ranges

I'm not sure what what to call what I would like help creating so please bear with me. Basically I have a program which assigns you a number of points(a competition point not a point on a graph or ...
2
votes
1answer
101 views

Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory?

This question is admittedly very programming related, but I felt that it is better suited to the Mathematics crowd than Stack Overflow. I would like to generate Hlibert walks through the pixels in ...
2
votes
1answer
113 views

Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
3
votes
1answer
361 views

Finding best case, worst case, and average case for an unknown algorithm

I have been given a paragraph explaining what an unknown algorithm does: An algorithm checks to see if a list of integers is sorted, it starts at the beginning of the list, and scans along until a ...
1
vote
1answer
75 views

Modal logics and logics with integer or even rational numbers - is that possible?

I am trying to find some research trends (publications, keywords for futher search, etc.) on logics and modal logics whose predicates can containt integer or even rational numbers (like x>2, x^2>3, ...
5
votes
1answer
269 views

Are there dual logic gates?

In category theory the usefulness of dualising such devices as monoids to comonoids has been shown, where multiplication which takes two inputs to one output is dualised to comultiplication which ...
2
votes
2answers
153 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
2
votes
1answer
43 views

Interpretation of “expected cost” of an algorithm

I'm studying randomized algorithms and I sometimes come across results like (1) The algorithm has an expected $O(f(n))$ cost. and (2) With constant probability, the cost is bounded by ...
1
vote
1answer
400 views

I don't understand the proof for reducing Subset-Sum to Scheduling with release time.

I found this proof for showing that Scheduling with Release Time is NP-Hard by reduction to Subset-sum, but I don't understand it: Scheduling With Release Time: Given a set of $n$ jobs with ...
0
votes
2answers
109 views

Is polynomial time reduction commutative?

True or False: $D_1$ and $D_2$ are decision problems, and $D_1 \leq_p D_2$, then cannot be that $D_2 \leq_p D_1$ I think it is false because we already have a mapping for all yes instance from $D_1$ ...
2
votes
1answer
163 views

Large numbers calculation

I think this question has more mathematical background than computional, then I'm gonna ask it here. I was thinking about large numbers calculation. Let's say I have the number $16777735$ stored in ...
2
votes
2answers
277 views

Why does DP solve a problem in polynomial time whereas brute force is exponential?

I am just learning DP, so maybe this is a noob doubt. I've read (while trying to understand the difference between DP and greedy approach - and I am still not fully clear) that DP goes through all ...
1
vote
1answer
860 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 ...