Questions tagged [notation]
Use this tag whenever you have a question about what some particular symbol/notation means.
190
questions
0
votes
1
answer
31
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
0
votes
0
answers
25
views
How many computer numbers can there be, with a basis $\beta$, and $n$ digits for the mantissa?
Cheers, I have to prove that, given a basis $\beta$ (e.g. $\beta = 2$ for binary), $n$ digits for the mantissa and $e$ for exponent ($ m \leq e \leq M, m \lt 0 \lt M$) for the floating point ...
11
votes
3
answers
2k
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$.
...
- 7
0
votes
3
answers
87
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 ...
- 101
1
vote
0
answers
27
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
39
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
48
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
51
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
50
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) ...
- 212
1
vote
0
answers
34
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
103
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
41
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
14
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
26
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
37
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
50
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
457
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
77
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
85
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
32
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
21
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
196
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
56
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
160
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
7
votes
4
answers
3k
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 ...
- 180
1
vote
1
answer
28
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
47
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
27
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,026
2
votes
3
answers
94
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, ...
0
votes
0
answers
40
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
36
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
538
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
1k
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
191
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
553
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
324
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
60
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
150
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
1
answer
44
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,170
1
vote
1
answer
50
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
87
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
202
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
105
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
46
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
1
vote
1
answer
3k
views
Meaning of L* if L is a language
I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
- 13
3
votes
3
answers
70
views
Why is subarray $A[p..k-1]$ empty when $k=p$?
I'm working through a proof of correctness for merge sort.
I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
- 215
2
votes
1
answer
39
views
When and what must be present on the left-hand side of the turnstile in metalogics?
Let me show the problem on an example...
An actual task from one of the former exams:
Consider a simple functional language:
$$e::= x|n|e_1e_2|\lambda x.e$$
With typing rules:
$$\tau ::= \mathtt{int} ...
- 179