Questions about how specific notions have to be understood as well as conventions of notation.

learn more… | top users | synonyms

0
votes
2answers
45 views

How to find out what are accept, loop and reject in this Turing Machine?

I am trying to find out accept, loop and reject in this Turing Machine because it doesnt have any...I am not sure if I completely understand it but this is the turing machine I am talking about... ...
6
votes
1answer
44 views

Matrix equality up to row/column permutations problem name

Sorry for the trivial question; has the following decision problem an "official" (possibly short) name? Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same ...
0
votes
1answer
76 views

What is the formal description of a Turing machine?

I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what "formal description" entails.
1
vote
1answer
53 views

Shortest directed path connecting given subset of vertices

Given weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$ source vertex $v \in V$ vertex subset $U \subset V$ how to find a shortest directed path from $v$ containing all vertices ...
1
vote
3answers
46 views

Confusion with the Running Time of an algorithm that finds duplicate character

I have the following simple algorithm to find duplicate characters in a string: ...
-1
votes
2answers
66 views

Mathematical function vs Computer program

In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration. Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets. Then relation $R \subseteq A_1\times ...
2
votes
1answer
46 views

n-Cube as a Cayley Graph

I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how ...
0
votes
3answers
388 views

Why is constant always dropped from big O analysis?

Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$. However, ...
0
votes
0answers
19 views

Cyclic definition of NP-completeness [duplicate]

Trying to understand the concept of NP-completeness, I came across this pearl on Wikipedia: From NP-complete: A decision problem L is NP-complete if it is in the set of NP problems and also ...
2
votes
2answers
79 views

What are these special strings called?

Is there any specific name for strings of data that have well defined format ? For example URLS, domain names, IP Addresses, Email addresses, File Paths etc. are all having well defined delimiters and ...
0
votes
3answers
44 views

How do I mathematically express a set generated using two loop variables within a single for loop?

I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration. For example, assuming ...
8
votes
6answers
1k views

How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best ...
0
votes
1answer
49 views

How do people measure performance overhead?

How do people measure performance overhead? Whenever someone is bragging about how their program or application performs better than another, they talk about particular measurements, eg time, ...
0
votes
1answer
21 views

Canonical infinitely ambiguous languages

In an article I am currently reading the grammar S → SS | a | ε is being described as canonical infinitely ambiguous. The infinitely ambiguous part I have no problem recognizing, but does ...
1
vote
1answer
40 views

Can Java be accurately described as statically and dynamically typed?

Java seems to be categorized as a statically-typed language [1], but I'm wondering if it would be accurate to describe it as generally statically-typed but having some dynamic typing because of the ...
5
votes
2answers
92 views

Unknown notation “$e^T$” in a machine learning paper

I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained ...
3
votes
1answer
37 views

What is the common terminology to refer to the nth ancestor of a tree root?

Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a ...
4
votes
2answers
111 views

Is it theoretically exist a computer that never affected by computer virus? [closed]

Is it theoretically exist a computer that never affected by computer virus? just wonder if there could be a revolution on the computer?
0
votes
0answers
15 views

In multi criteria decision making, what notions are there to get a subset of the Pareto set?

In the multi criteria decision making context, let $\mathcal{A}$ be a set of alternatives or choices. Each alternative $\alpha\in \mathcal{A}$ is a vector of $k$ criteria $\alpha=(v_1,v_2,\dots,v_k)$. ...
-1
votes
1answer
43 views

How to read edge labels like “01, 1” on a state diagram?

Is this state machine a moore machine or a mealy machine? I am confused because the states have outputs and the transitions have output based on the input. I tried making a state table but I think ...
1
vote
1answer
34 views

Variable programs and variable data

I'm reading "Sets for Mathematics" by Lawvere, and he uses the following metaphor at the end of section 1.3: "we will see...how any abstract set F of the right size can act as mappings between given ...
3
votes
3answers
82 views

Difference between diameter of a graph vs longest path of the graph

I am curious what is the difference between diameter of a graph vs longest path of a graph. I just read diameter of a graph can be solved using Floyd warshall in O(V^3) while longest path can be ...
3
votes
0answers
28 views

What is a polyad?

I've read the wikipedia article, but I don't speak category theory (and I'm not sure how to start so I'm just picking something that sounds interesting). So, can someone give me a simple, possibly ...
0
votes
1answer
151 views

What is pass-by-value-result and its advantage and disadvantage? [duplicate]

I have searched on Google, but I can't quite understand what is pass-by-value-result. What is the advantage and disadvantage of using pass-by-value-result? If I have a program code like this, what ...
2
votes
1answer
32 views

Resizing and aliasing in computer science [closed]

If you resize an 1000x1000 raster image to 10x10 and resize it back to 1000x1000 is this considered to be an example of aliasing?
4
votes
2answers
54 views

What is Finite Automata Bowl?

I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the ...
1
vote
2answers
76 views

Why should leaf nodes in a red-black tree be black?

From the property of Red-Black Trees we know that: All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms") But what is the reason that we ...
0
votes
0answers
23 views

Name for a Type of Simulation

I have come up with a type of simulation "game" but I cannot find anything describing it online. The simulation has a 2D "world" with a number of automatons on a discrete grid, similar to the game ...
2
votes
1answer
69 views

Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
1
vote
1answer
104 views

Is Wikipedia's formal definition of NP correct?

Wikipedia's formal definition of NP based on deterministic verifiers states: A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such ...
-2
votes
1answer
23 views

Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
3
votes
1answer
55 views

O(f) vs O(f(n))

I first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$ Afterwords in Discrete Math another Professor, without knowing of the first, told ...
0
votes
1answer
49 views

Can a context free grammar for $L$, generate a string not in $L$?

from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the ...
2
votes
1answer
50 views

Limits to the definition of a language

Is there any limit to what we can define as a language? Is any set of symbols a language? For example, given the alphabet $\Sigma$, do we say that the language $L = \Sigma$ has alphabet $\Sigma$? ...
3
votes
4answers
177 views

Why does merge sort run in $O(n^2)$ time?

I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O ...
1
vote
2answers
135 views

Should O(1) necessarily stand for a non-zero constant?

I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant ...
23
votes
6answers
2k views

Explaining the difference between computer science and computer literacy

What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows" computer science computer programming ...
2
votes
3answers
87 views

Language Recognition Devices and Language Generators

I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses ...
1
vote
2answers
100 views

Why are pushdown automata countable? [closed]

I began a chapter in a textbook on computational theory where they begin to talk about decidable languages. The problems in this section are pretty confusing and I honestly don't know how to begin ...
3
votes
0answers
59 views

“Data-race free” programs

In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows: Program $\Pi$ is data-race free if, for all histories $H$ ...
3
votes
1answer
104 views

What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'? [closed]

The principles of calculus, historically, are differentials and integrals [1], while those of algebra are operators and equation solving [2]. Contemporary principles are analysis and abstract objects, ...
3
votes
1answer
281 views

Tree : Forest :: Path :?

A forest is a collection of trees. Is there a similar notion for paths? e.g., a _______ is a collection of paths.
1
vote
1answer
55 views

Definition of “infix” in formal languages

I've got a simple question: Let's say we have the following definition of a language over some alphabet: $L = \{w \mid w \text{ contains the infix } aab\}$ Does that mean $aab \in L$? or does ...
1
vote
1answer
103 views

Does NP-Complete imply non-satisfiability?

I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language. It sounds to me as though the problem could be difficult to ...
4
votes
2answers
456 views

What is the no free lunch theorem?

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser ...
3
votes
2answers
53 views

Dependent types vs refinement types

Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of ...
3
votes
1answer
172 views

Why ⊢ for affirmative predicates and ⊨ for ¬negations?

I read a book which says that in Predicate Calculus, syntactic theorem proving is identical (complete and sound) with semantic entailment and this is very useful because it is easier to prove positive ...
-3
votes
2answers
32 views

Description of “Logistics Domain” in AI

While reading some papers in AI (for a project I have to do), I see expressions "blocks world domain" and "logistics domain". I know what blocks world domain is, but I don't know the definition of ...
-1
votes
2answers
52 views

What does a wedge in a graph look like?

I am reading Decompositions of Triangle-Dense Graphs by Gupta et al. On page 2, in Definition 1 what is a wedge in a graph? I know what triangle is but I don't know what wedge is and google isn't ...
1
vote
2answers
40 views

Are loop counters spatially or temporally local?

Consider this nested loop: for (i=0 to n) for(j=0 to n) for (k=0 to n) sum := sum +k end for end for end for Do ...