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
0answers
14 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 ...
4
votes
2answers
512 views

Proof that Newton Raphson method has quadratic convergence

I've googled this and I've seen different types of proofs but they all use notations that I don't understand. But first of all, I need to understand what quadratic convergence means, I read that it ...
3
votes
1answer
88 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 ...
0
votes
1answer
11 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!
-2
votes
0answers
17 views

i have this gui calculator code. but i don't know how to make the arithmetic operation appear on textfield. can someone help me tnx . [on hold]

import java.awt.; import java.awt.event.; import javax.swing.; import javax.swing.event.; import java.awt.event.; import javax.swing.border.; class CalculatorFinal extends JFrame implements ...
11
votes
4answers
711 views

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

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 ...
3
votes
1answer
290 views

Help with Recurrence relations forward substitution

Thanks in advance to anybody who can help, The question: solve by recurrence relation using forward substitution and verify by mathematical induction. $T(n) = 2T(n/7)$ for $n > 1, n$ is a power ...
0
votes
1answer
24 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 ...
2
votes
1answer
14 views

The reason for using normalized data as inputs of Neural Networks [on hold]

Hello I would like to forecast time series and in many algorithms are used as inputs normalized data -1, 1. What is the reason for this normalization? My original data have scale from 1 to 2. Thank ...
1
vote
1answer
20 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 ...
-3
votes
0answers
36 views

SimRank Example? [on hold]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
1
vote
2answers
20 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
58 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
28 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
0answers
89 views

Combinatorial algorithm problem of a symmetric matrix.

Given a matrix A of a regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $ A_x$ is the symmetric matrix of the graph $(G-x)$, where $C$ is the ...
4
votes
4answers
8k 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 ...
0
votes
1answer
20 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
28 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
19 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
16 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
37 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 ...
6
votes
1answer
722 views

Strange behavior with {xor, and, or} bit operations on integer offsets

I thought of a problem today: given a range of integers $[a, b]$, for all pairs of integers $(x, y)$ in that range, what is the number of them such that $x$ op $y \in [a, b]$, where op is one of {xor, ...
0
votes
1answer
11 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
13 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 ...
2
votes
1answer
62 views

Proof of algorithm refinement

I recently had an interview in which I was asked to produce an algorithm to that computes the pairs of integers, from a list, that add up to a integer k. I then had to increase the time efficiency of ...
1
vote
1answer
27 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
16 views
7
votes
4answers
186 views

Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
0
votes
1answer
19 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 ...
1
vote
0answers
40 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
384 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
6
votes
2answers
227 views

State of the progess of the automated proof checking

I recently came across a concept of automated proof checking. I am very intrigued by the idea, that in the future all the proofs could be verified by a computer. Moreover, some proofs were already ...
4
votes
3answers
925 views

What is the CFG of the language that generates all strings over alphabet $\{a, b, c\}$?

The most obvious one that I found was, $$S \rightarrow SSS | A | B | C$$ $$A \rightarrow Aa | \epsilon$$ $$B \rightarrow Bb | \epsilon$$ $$C \rightarrow Cc | \epsilon$$ However, I realize this CFG is ...
2
votes
3answers
157 views

Calculating a SQRT digit-by-digit?

I need to calculate the SQRT of $x$ to $y$ decimal places. I'm dealing with $128$-bit precision, giving a limit of $28$ decimal places. Obviously, if $\,y > 28$, the Babylonian method, which I'm ...
1
vote
1answer
64 views

A decision problem that is Cook reducible to its complement

I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements. Can anyone give me ...
0
votes
1answer
358 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
3
votes
1answer
22 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 ...
10
votes
1answer
234 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
2
votes
1answer
27 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
0
votes
1answer
22 views

Use the Pumping Lemma to prove that $L=\{a^{m}b^{2^{n}} \}$ is not regular.

Normally pumping lemma proofs aren't too hard; you just experiment with different values of $i$ and sort of stumble on the solution. However, this problem is really bugging me and I am spending a lot ...
4
votes
2answers
286 views

Image Reconstruction:Phase vs. Magnitude

Figure 1.(c) shows the Test image reconstructed from MAGNITUDE spectrum only. We can say that the intensity values of LOW frequency pixels are comparatively more than HIGH frequency pixels. $$ ...
0
votes
1answer
19 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
1answer
31 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
1
vote
1answer
57 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
0answers
20 views

What's the mathematical model of Consistent Hash?

What's the mathematical model of Consistent Hash? There are several implementations: Karger's implementation using a bucket cycle: Jump Consistent Hash [Highest Random Weight (HRW)][3] hashing: ...
1
vote
1answer
164 views

Related Integer Combination

The title and tags are a little goofy since I'm not quite sure what to call this. This may be more of a computer science question, but I thought I'd ask here too. I have two integers $n$ and $m$ ...
1
vote
1answer
17 views

What does the notation $\{ \pm 1 \}^X$ in relation to functions and hypothesis classes means in the context of PAC learning over half spaces?

I was reading the following paper (on PAC learning over half-spaces) and encountered the following notation for a hypothesis class (on page 4): $$\mathcal{H} \subset \{ \pm 1 \}^X$$ However, it was ...
1
vote
3answers
303 views

Calculate integer summation when lower bound is a variable

How do you calculate the following sum? \begin{equation*} \sum_{i=k}^n i \end{equation*}
0
votes
0answers
31 views

About Katz centrality

I am studying Graph Theory and Network Analysis, I have this measurement formula which called Katz centrality: My question is: why $A^k$ will grow [infinitely] in $k$ for most cases. As I think ...