Questions tagged [notation]
Use this tag whenever you have a question about what some particular symbol/notation means.
193
questions
0
votes
1
answer
33
views
An elementary question about grammar
Recently, I am studying grammar in automata. And, I have few information about this subject.
I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$.
Is it true if I say that $S\to aASA$ ...
- 13
-1
votes
1
answer
88
views
Understanding reductions and notation
I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
- 1
2
votes
2
answers
57
views
Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?
While working with complexity classes, I've come along the definition of $DP$ (or $D^p$):
$$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$
I am interested in a different (and much ...
- 301
0
votes
0
answers
65
views
Function types in Computer Science Metanotation
See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF.
I often make use of the BNF syntax observed there, as a substitute for ...
- 141
0
votes
1
answer
40
views
When to use subscript and when to make it a function?
Let's say, I have a set of cats $C = \{ a, b, c, ... \}$. Each cat has a tail. I can say, that the lengths of the tails of cats are denoted as $t_a$, $t_b$, etc. Otherwise, I can say that they are ...
- 113
11
votes
3
answers
3k
views
Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"
To me, the only difference is that when we say $O(...
0
votes
1
answer
38
views
Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?
I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution.
My approach was that it has infinite because,
lets say we have $x = a^5$ and $y = a^7$.
...
- 17
0
votes
3
answers
95
views
Is there a notation for types?
Is there a notation for statements like the following:
If both operands are of type int, then the result is of type int. If ...
- 113
1
vote
0
answers
32
views
Dot symbol in set-builder expressions in CRDT literature?
In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
- 11
1
vote
1
answer
42
views
What does :: indicate in all-quantifier predicates?
Can somebody explain to me the meaning of $::$ in the following predicate?
$$(\forall i : P(i) : Q(i)) \equiv (\forall i :: P(i) \implies Q(i))$$
- 121
1
vote
1
answer
147
views
What order B-tree is this?
I am studying B-trees and reading Introduction to Algorithms by Cormen et al.
Unfortunately, they have this diagram Figure 18.1 and they do not list the order of the tree.
I understand that for a B-...
- 135
-2
votes
1
answer
59
views
What is the BigO of a C# function when runtime is 3n - logn + 1
I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
- 5
1
vote
1
answer
59
views
Simplifying Notations in Recurrence Relation
In the CLRS book, section 4.4 they try to resolve the following recurrence:
$$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$
Later, they write the same recurrence as
$$T(n) ...
- 222
1
vote
0
answers
43
views
How can I define nested structs as mathematical notation?
My purpose is to write a academic paper related to shared computing more abstractly and I need to refer to these variables in both equation and its corresponding pseudocode.
In my pseudocode I have ...
- 135
2
votes
2
answers
131
views
How can I define programming struct variables as mathematical notation?
My purpose is to write a journal paper related to shared computing more abstractly (simply cost model) and I need to refer to these variables in both equation and its corresponding pseudocode.
I want ...
- 135
-1
votes
1
answer
55
views
what does $(1 + (λ, λ))$ Genetic Algorithm mean?
I am discovering the topic of Genetic Algorithms, I read a bit about it on wikipedia and towardsdatascience. When I checked papers some papers, I found them using the notation "$(1 + (λ, λ))$&...
- 310
1
vote
0
answers
16
views
Contiguous-substring operator
If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
- 11
1
vote
1
answer
27
views
Definition a Turing machine (which may or may not halt) as a function... notation?
I would like to define a Turing machine as follows.
Let Z be an alphabet, and let L be the set of all sentences of this alphabet. For instance, Z={0,1}, then L is the set of all binary sentences.
A ...
- 345
1
vote
1
answer
38
views
What does ({a,b}*)² mean?
Pretty much just the title. Is it all possible combinations of a and b that have 2 letters ?
- 27
-1
votes
1
answer
52
views
What does x sign mean in functions
I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?
0
votes
1
answer
467
views
What is the meaning of this symbol that looks like an inverted uppercase A?
I found this symbol in a book I'm reading. Does anyone know what this symbol means? Does it mean for all js?
1
vote
1
answer
109
views
What is the origin of the Bottom Type notation? Why does it look like... a bottom?
I couldn't help but notice the opening summary in Wikipedia's article on Bottom Types:
In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also ...
- 421
3
votes
0
answers
101
views
How to write a job shop problem with these constraints in alpha|beta|gamma notation?
I have a job shop scheduling problem with the following characteristics. How would I write that in alpha|beta|gamma notation (see 1,2)? I know some of the parts, but not all. I add my suggestions in <...
- 131
1
vote
1
answer
37
views
What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?
We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}.
I found an ...
1
vote
1
answer
25
views
Set notation for ACL matrix
This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation ...
- 81
0
votes
1
answer
36
views
On lambda calculus notation: FGa
If we've got this expression:
FGa
where F and G are functions (as well as a, of course; but let's treat a as a constant).
It must be understood that:
first apply F taking G as input; then apply the ...
- 135
1
vote
2
answers
545
views
Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?
Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?
2
votes
1
answer
89
views
Raising to the T in machine learning
What does it mean when in a machine learning paper there is
$(arg)^{T}$, what does the T does to an arg in this 3b1b video on neural networks he puts the: $(w^{l-1})^{T}$
- 21
1
vote
1
answer
287
views
Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o
New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning.
If you have a given an ...
- 113
8
votes
4
answers
4k
views
Arrow notation?
can someone explain what the following notation is?
For j <- 1 to n
Legal <- True
I've seen these in various places, including wikipedia articles.
It ...
- 190
1
vote
1
answer
30
views
Notations for dealing with generators in algorithms
This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is:
...
- 133
1
vote
0
answers
49
views
Infix to reverse polish notation (RPN)
I have an example: m = n = p = (-1) ^ (m + n + p) * (m + n + p);
I don't know what to do with multiple "=". Should I treat them as a sign with the lowest priority or just put them in end of ...
- 11
26
votes
3
answers
6k
views
Is there any reason why the modulo operator is denoted as %?
I would like to know if there is any reason why many programming languages use the notation % for the modulo operator?
It is used in the most "famous" ...
- 1,046
2
votes
3
answers
95
views
Meaning of $\log^{O(1)}(a+b)$
What's the meaning of $\log^{O(1)}(a+b)$ ? Is it simply $(\log_2(a+b))^k$ where k is calculated in constant time ? That is the base 2 logarithm usually in computer science when no other base is set, ...
- 1,006
0
votes
0
answers
51
views
Function notation/mapping for this type of functions?
In short, what is the proper function notation/mapping for this type of functions?
From Wikipedia regarding maps:
In the communities surrounding programming languages that treat functions as first-...
- 119
1
vote
1
answer
41
views
Notation within gaussian function
On our lecture slides we have two different notations of the gaussian function.
First it gets introduced as follows:
$$p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \...
- 13
3
votes
1
answer
749
views
Does there exist standardized language-agnostic data structure notation?
I wonder if there exists language-agnostic data structure notation. Preferably a standard, allowing to describe data structures and basic data types. e.g. something like a subset of ...
- 133
1
vote
1
answer
2k
views
Convention of a += operator in pseudocode
I have to write some algorithm in pseudocode for a paper. For this I have the "$\leftarrow$" to assign a value.
$x \leftarrow y^2$
now I want to write a method which adds to the variable. In ...
- 123
2
votes
1
answer
199
views
What does the notation $ [ i \neq k ] $ mean?
I can't figure out what the notation $[x \neq k ]$ means. Here's a bit of context:
The formula is:
$Pr[A_i^k = 1] = \frac{[i\neq k]}{|k-i| + 1} = \begin{cases} \frac{1}{k-i+1} \text{ if } i \lt k \\ 0 ...
- 271
0
votes
2
answers
644
views
Same notation/terminology for union of sets and concatenation (Kleene star)?
For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
- 119
1
vote
1
answer
365
views
Is grammar that describes an equation in prefix (Polish) notation always unambiguous?
I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation:
$$Expr \rightarrow + \, ...
- 37
3
votes
2
answers
63
views
Parentheses after Typing Environment
I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: Γ(x) = k. For example, ...
1
vote
1
answer
181
views
Determining asymptotic notation of a complex function
$$
5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40
$$
I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
- 11
0
votes
2
answers
68
views
Transformation Function: Gonzalez and Woods
I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation
$$
T \left(u, v\right)
=
\sum_{x=0}^{M-1}
{
\sum_{y=0}^{N-1}
...
- 1,190
1
vote
1
answer
51
views
Why in the code i ≃ n?
i=2;
while(i<n)
{
write('*');
i=i*i;
}
Why $n ≃ i$?
I mean suppose $n=1000$ and so $i= 2,4,16,32,256,65536$ is in every steps.
In the book wrote $2^2 ...
- 33
4
votes
1
answer
90
views
Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?
Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (...
user110815
2
votes
2
answers
222
views
Typesetting LTL in Unicode?
Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as
$$
(\mathop{⬦}ψ)\ \,\land\ \,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\...
user110121
5
votes
1
answer
115
views
Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.
For example he says that the running time of a single-tape ...
- 163
3
votes
2
answers
2k
views
Weight functions in graph algorithms
In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$.
Why ...
- 133
1
vote
1
answer
52
views
Asymptotic notation and random variables
I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).
Suppose that the two ...
- 123