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
1answer
31 views

Calculating an Intensity Centroid

I am trying to understand the theory behind calculating an Intensity Centroid (image processing), in particular defining moments. As defined by Rosin 1: $m_{pq}=\underset{x,y}{\Sigma}x^py^qI(x,y)$ ...
0
votes
1answer
73 views

Computability problems — can't solve

I have a pair of exercises I can't solve (tomorrow I'll have a test). I need some kind of solution so I can apply it to other exercises...thanks to all! In the following $W_n$ means the domain of the ...
1
vote
0answers
11 views

is the suggested PDA correct?

so i have this language $$ L = \{x^{i} v^{j} z^{j+2} w^{k} v^{i+k} | i,j,k \ge 0 \}$$ i made this PDA for it . states $ = \{q_0 ... q_5 , final\} $ alphabet $= \{ x,v,z,w \}$ stack ...
0
votes
1answer
56 views

Fractional Knapsack- explanation

The following algorithm is given: ...
0
votes
1answer
224 views

Basic idea of proof

I am trying to understand the proof that the expected running time of quicksort is $O(n \log n)$. Could you maybe explain me the basic idea? I am confused right now. EDIT: Suppose that we use the ...
4
votes
2answers
114 views

Help with deriving an absolute strategy (very fun if anything)

My friend and I are trying to figure out a solution or even a best path to figuring out a certain win strategy to this game. This game that my friend made, calling it the number game for short, is ...
0
votes
0answers
13 views

Prove that $ALL_{CFG}$ is undecidable by reducing from PCP

I'm studying for a Computability exam that I have in a few weeks, and have come across this question which I'm having a hard time solving: Prove that $ALL_{CFG}=\left\{ \left\langle ...
0
votes
1answer
30 views

Time complexity function

I'm not sure I should post this on the Mathematics website or the Computer science website of Stack Exchange. If I'm wrong I will replace my question. So I'm trying to calculate the time complexity ...
0
votes
0answers
31 views

Bitwise Operations and the Naming Convention of their Operators

So I just recently came across a bitwise operation on StackOverflow which shifts the bits in a binary number to the right while zero-filling from the left. The left side zero-filling overwrites the ...
1
vote
2answers
47 views

Alternate plain English algorithm for Towers of Hanoi

There are four plain English algorithms for the Towers of Hanoi Puzzle available on Wikipedia, but when I was first solving the puzzle, I came up with an algorithm that is different from any of the ...
2
votes
0answers
40 views

Neighbor-full partition of $\{0,1\}^n$

What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$) We say $A$ and $B$ are neighbors if their ...
0
votes
0answers
37 views

Clique Percolation Method calculation

According to Clique Percolation Method as shown in Wikipedia I could not understand why the result of Graph1 is Graph2 if we assign k to be=2, According to the definition of CPM, then the cluster ...
4
votes
3answers
65 views

WolframAlpha has a different answer for a definite integral, why?

So I ran into this contradiction and I'd appreciate if someone could help explain what is happening: So when i perform the following integral on paper: $$\int_{-1}^1(\sqrt[3]{x} -2)\;dx \; = [\frac ...
2
votes
1answer
56 views

How to understand or derive the formula $Mantissa$ $bits$ $/$ ${log_2}$ $10$ = $Decimal$ $digits$ $of$ $precision$?

I asked a question a couple days ago about floating point precision on stackoverflow called, "Is floating point precision mutable or invariant?" and I received the following response. The formula ...
2
votes
1answer
29 views

pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
0
votes
1answer
61 views

Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
1
vote
0answers
34 views

Formal (Mathematical) Definition of N-Clan?

I tried many times to find a formal definition for the following important concepts in Graph Theory and Network Analysis: 1) N-Clique. 2) N-Clan. 3) K-Plex. 4) K-Core. Reference , but ...
1
vote
0answers
11 views

What is the maximal possible 'non-empty' K-Core of a Graph G

Since any graph can be extracted to find K-Core easily, since finding K-Core is Pronominal problem, what is the maximal possible 'non-empty' K-Core of a Graph G. Is it k+1 ? or what exactly ?
0
votes
1answer
17 views

Does this component have 2 2-clan and also 2 2-clique

I have done many examples with n-Clan and also with n-Clique, but I found an example online as shown in the figure bellow, it says there is only 1 2-Clan and also 1 2-Clique, nevertheless I think it ...
3
votes
1answer
26 views

Pumping Lemma for CGF question

I'm going through a pumping lemma for a proof that: the language $B = \{a^nb^nc^n \mid n\ge 0\}$ is not context free The first case considers when both v and y contain only one type of alphabet ...
3
votes
2answers
103 views

Computing the $n^{\textrm{th}}$ permutation of bits.

I've seen this post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are algorithms to quickly permute the NEXT ...
0
votes
1answer
20 views

Software for computing n-Clique, n-Clan, n-Plex?

I am studying graph theory and complex network into details, I would like to ask if some one could help providing a useful (academic) tools or some good tools for computing n-clique, n-clan, n-core, ...
1
vote
1answer
27 views

K-Clan detection based on a given connected Graph

I have the following definition of the K-Clan: A k-clan is a k-clique where the diameter of the corresponding sub-graph is at most k. and here according to the graph bellow I do not know why 135 is ...
1
vote
0answers
34 views

Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $

Problem Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $ My first idea was this: There can be an "a","b" or a "c" at the beginning of a word Then we ...
1
vote
1answer
49 views

Find regular expression that defines a given language

I want to find a regular expression that defines a language L over the alphabet {0,1} with a following condition: every word contains exactly two 000 substrings. For example, a valid word would be ...
0
votes
1answer
28 views

show how 42.25 would be stored as a floating point number with an 8-bit mantissa and a 4-bit exponent.

So I know that in binary: 42: 00101000 0.25: 01 I then put combine the numbers so it would be: 00101000.01 Once I get this point I'm not sure how to show the mantissa as an 8-bit and the exponent ...
1
vote
1answer
37 views

In formal languages, why is $L^0 = \{ \epsilon \}$? Why isn't it the empty set ∅?

It just doesn't make logical sense to me that a language to the power of $1$, is itself, but to the power of $0$ is only a tiny part of itself (since every language contains $\epsilon$) Wouldn't it ...
2
votes
0answers
38 views

What exactly is wrong with this argument (Lucas-Penrose fallacy)

Argument "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
0
votes
0answers
24 views

Size of remaining search space for Vehicle Routing Problem given a partial solution

The vehicle routing problem is a NP-hard problem that, in its most basic form, involves scheduling routes for v vehicles that have to make n deliveries in total. So a solution (schedule) has the form ...
0
votes
0answers
19 views

Rent's Rule and Modularity?

Rent's Rule http://en.wikipedia.org/wiki/Rent%27s_rule plays a very important role in the engineering of computer circuits, as well as in models of processing (be it of information, be it of brain ...
0
votes
1answer
15 views

Brauer Algorithm [duplicate]

I'm working on a problem and I'm looking at an equation: $lg(n) + (1 + o(1))(lg(n))/(lg(lg(n))$ All I want to know is, what does o(1) mean? Thanks!
11
votes
4answers
754 views

why is $2.2250738585072014\text{e}{-308}$ not a number? [closed]

In programming the min value of a float is: $$2.2250738585072014\text{e}{-308}$$ but when I type this into a calculator, it says Not a Number. what I am wondering ...
1
vote
1answer
21 views

What is the total speedup?

This is a repost of a StackOverflow thread. I was told that people on this forum will be able to answer this question faster. So here it is: This is not homework. I'm taking a computer architecture ...
0
votes
1answer
42 views

What is the difference between finding the sum of a series and its closed-form solution?

In complexity theory, it is sometimes necessary to find the "closed-form solution" of a summation. This was put in our exam guide as "solving arithmetic and geometric series", which I initially ...
1
vote
2answers
23 views

Expected codelength for Huffman-algorithm with probabilities

I am unable to solve the following problem: Let $$n \geq 2$$ $$p_{1} \geq p_{2} \geq ... \geq p_{n}$$ $$p_{i} = 2^{-k_{i}}$$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n}p_{i} = 1$. $p_{i}$ is the ...
3
votes
1answer
76 views

Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee ...
2
votes
2answers
34 views

Tweaking formulas to increase scoring

I am building a model for SVM classification. However, the confidence score that i have would be from negative to positive. This is the formula i am using to normalize the confidence score ...
0
votes
1answer
27 views

Can we program a computer to check a proof in first-order arithmetic is valid, and can we find out whether such a statement is true?

Slightly confused by this. I wish I knew what more to add, but I know it's asking something about the halting problem, and something about Godel but I cannot seem to figure it out.
2
votes
1answer
42 views

How to show that the Restricted-3-color decision problem is in the polynomial class

I'm struggling to answer a past paper question, which asks to prove that the defined problem is in the polynomial complexity class(P). The question is mentioned below The only strategy I can come ...
0
votes
1answer
20 views

Languages in coNP

if a language $L \in$ coNP, i.e. it's complement is in NP, then does L have a deterministic turing machine that decides it? i think that this is false, but am unsure how to show it? my guess is using ...
0
votes
0answers
17 views

determining whether a turing machine

For $i\in \mathbb{N}$, define $L_i :=${$ ⟨M⟩ |$ On input $101$ M halts after at most i steps} For any fixed i the language $L_i$ is decidable as if there is no end state up to the i$^{th}$ position ...
0
votes
1answer
22 views

Proving from Myhill-Nerode that the minimum DFA is the smallest automaton recognizing $L$

From this paper, In the proof of (Myhill-Nerode theorem) it's stated that if $L$ is a regular language and the index of $\sim_L$ is $i_L \in \mathbb{N}$ then it's both necessary and sufficient for ...
0
votes
0answers
20 views

How to calculate effect of different variables/parameters on a quantity?

I am developing a game for iOS. In the game I have around eight different parameters that directly affect the score of the player. We can say that these eight variables decide the difficulty of the ...
0
votes
1answer
55 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
2
votes
1answer
139 views

A few questions about KSVD algorithm (dictionary learning) in a paper

To learn more about dictionary learning, I am currently trying to understand the concept in detail and to do so, I've found the following paper quite informative: KSVD: an algorithm for designing ...
1
vote
1answer
38 views

Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
0
votes
1answer
20 views

Find the language recognized by the given deterministic finite state automaton

I got 01* U 1(01)01 as my answer. I'm not sure if its right.
1
vote
0answers
62 views

Permutation and Combination Problem-word arrangement

There are three pieces of paper.In the three papers ,a string (non-empty) has to be written such that none of the string on any paper is prefix of some other string.Also alphabet size of characters ...
0
votes
1answer
31 views

Regular Expressions that define given languages

A few of these here I just wanted to make sure I had right. For $\Sigma = \{0,1\}$ a. The language consisting of all strings of 0's and 1's that have even length and where 0's and 1's alternate I ...
3
votes
1answer
23 views

How to compute $\cos(x)$ within $n$ digit accuracy when $x = \sqrt{y}$ with $y \in \mathbb{N}$

How does one compute $\cos(x)$ within desired $n$ digit accuracy when $x = \sqrt{y}$ with $y \in \mathbb{N}$ and $x$ is not rational? The reason I am asking this question is that calculators ...