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

learn more… | top users | synonyms

0
votes
1answer
29 views

Why “reduce to”, not the other way around?

This action confuses me for a while. As you know, once we come up with a problem and we want to know how hard it is, we will do the "reduction". Intuitively, if we prove problem B is as hard as ...
3
votes
1answer
54 views

How do you call alternatives in the grammatical productions?

I have encountered a question, which asks what is a syntactic form. This motivated me to ask myself, what is the anatomy of the grammatic rule, ...
11
votes
2answers
2k views

Can this algorithm still be considered a Binary Search algorithm?

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as ...
0
votes
1answer
29 views

Is applying a formula a kind of reasoning?

Supposed I have a set of simple rules, e.g. if A is between 10 and 20 and B is between 3 and 5, then use 3 and this rules are used in some kind of (more or less)...
3
votes
1answer
38 views

Common name for inverse of beta reduction

For some transformation, I am currently working on, it is useful to "pull out" subexpressions and replacing them with variables. i.e. $\textbf{transform}(42 + 3 * 4) = (\lambda x. 42 + x) (3*4)$ ...
0
votes
1answer
22 views

Is TD-learning considered a model-based algorithm?

Differently from Sarsa and Q-learning, pure temporal difference learning (TD-learning) works with state value functions $V(s)$ and not state-action Q value functions $Q(s,a)$. It means that, in order ...
1
vote
1answer
34 views

operator precendence grammar

According to this post http://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
2
votes
0answers
15 views

What is the difference between the research area of “ad hoc networks” and “device-to-device communication”?

I wonder what "device-to-device communication" (from a research perspective) covers what "ad hoc networks" don't. To the context of this question: I am reviewing papers which deal with "device-to-...
0
votes
0answers
15 views

Is XSL-Transformation a type of compiling? [duplicate]

I am currently working on a paper based on the topic of creating a source-to-source compiler from an existing application to C#. The existing application is actually just based on XML files, which ...
3
votes
1answer
116 views

Undecidable vs Unsolvable?

In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is ...
0
votes
2answers
50 views

What Exactly Does the Term “Key” Mean with Regards to a Hash Table?

I know it is supposed to be some arbitrary term that is a stand-in for a large class of possible objects. But I still don't understand what part of the array the term "key" is meant to represent or ...
1
vote
1answer
71 views

Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

I am currently learning landau notations and am stuck on the following True/False question. What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. ...
1
vote
0answers
25 views

Inductive Bias - Decision Tree Pruning as a Bias

I am trying to understand inductive bias and have been looking around to try and work it out. I found this which explains what it is briefly but I have struggled to find examples I understand which ...
0
votes
0answers
35 views

Name for this algorithm to roughly shuffle infinite list with finite memory

A couple of friends and I were talking about the best way to attempt to shuffle a infinite list, given finite memory. We immediately concluded that you could not do so, at least not in the same sense ...
0
votes
0answers
34 views

Process's “Name” Language Abuse?

Strictly speaking, do processes have names? From what I understand, talking about process's "name" is an abuse of language, and the process's "executable name" should be used instead.
3
votes
3answers
56 views

Terminology - machine code and byte code

Do "machine code" and "byte code" terms refer to the available instruction set to the CPU and virtual CPU and their encoding (the language specification) or do they refer to the "encoding" of the ...
1
vote
1answer
32 views

If Data-Flow Analysis is able to approximate, what does that mean?

I have been learning about data-flow analysis and have come across the idea of approximations and that the data-flow analysis should be able to under and over approximate a situation. For example, ...
0
votes
1answer
52 views

what is a compiler intrinsic function?

I'm trying to understand what a compiler intrinsic function is. I did find a wiki article but I'm still kind of fuzzy on what it is exactly. If someone could provide a few concrete examples that would ...
3
votes
1answer
50 views

In Data Mining, what does it mean to be greedy?

I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory. For ...
1
vote
2answers
40 views

Is there a name for graphs which contain oriented and non-oriented edges?

Is there a name for graphs which contain oriented and non-oriented edges? I couldn't find on the internet if there exist a specific name for such graphs.
7
votes
2answers
134 views

If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup, how would one refer the speedup ...
3
votes
2answers
104 views

What is running time of an algorithm?

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
2
votes
2answers
87 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
-1
votes
3answers
90 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
60
votes
2answers
6k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the term?...
0
votes
2answers
62 views

What is an upright rectangle?

What is an upright rectangle? I came across the phrase in my homework - "The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to ...
-1
votes
1answer
32 views

How is a procedure application a control structure?

In scheme, a procedure application is considered as a control structure. Why is this?
3
votes
2answers
99 views

What defines a tool as a “compiler”

I've been trying to figure out what technically makes a tool or program a compiler. For example, I know that gcc will compile source code to object files or assembly, hence transforming a ...
24
votes
4answers
4k views

What exactly (and precisely) is “hash?”

I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on ...
4
votes
0answers
40 views

Proper pronunciation of “Aho-Corasick?”

Tomorrow I'm going to be teaching a class on Aho-Corasick string matching. I'm pretty sure I know how to pronounce Margaret Corasick's name, but I don't actually know the proper pronunciation of ...
1
vote
1answer
47 views

What is the name of the word problem for free groups under straight line program encoding?

I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free ...
-4
votes
1answer
45 views

How do you call this typical file name order? [closed]

log1.gz log10.gz log100.gz log101.gz log102.gz log103.gz
10
votes
3answers
2k views

What does Θ(1) memory mean?

I have the definition of an in-situ algorithm from the professor, but I don't understand it. In-situ algorithms refer to algorithms that operate with Θ(1) memory. What does that mean?
-1
votes
1answer
153 views

What is the difference between formal language, regular language and regular expression? [closed]

I want to know the difference between these three languages and it would be great if you would give some examples as well, thank you. :)
5
votes
1answer
74 views

How did each class of languages receive their name?

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable ...
1
vote
0answers
64 views

Difference between capacity miss and conflict miss

Premise: Two types of cache miss: capacity miss, conflict miss\ Cache contains only 2 sets, SET 1 and SET 2 Problem: If data A maps to SET 1 and it doesn't exist in SET 1 while SET 1 is fully ...
1
vote
0answers
11 views

What is the term for the object to be identified in a pattern recognition problem?

What is the term for the object to be identified in a pattern recognition problem? So, for example, if one were matching a glyph expected to be an alphabetic letter to a set of templates, what is the ...
3
votes
1answer
31 views

How to correctly define the ratio of an approximation algorithm?

For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal ...
2
votes
1answer
32 views

What is a local inference system?

A inference system is a set of rules that can be used to prove something in some formal model. I understand that. But what does it mean to a inference system to be local? For instance, in the page ...
1
vote
0answers
31 views

Clustering of matrices

I have a matrix of n lines and T columns, containing only 0's or 1's. I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find ...
1
vote
2answers
63 views

Why are Complexity Notations Called Asymptotic?

Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
5
votes
1answer
86 views

Difference between “sort” and “universe”

A very basic question. As title, what is the difference between "sort" and "universe" in type theory? Are they interchangable? Or are there only finite number of sorts, but infinite universes?
3
votes
1answer
44 views

The language of Logical Theory as Metalanguage

I am reading the Handbook of Satisfiability, and in Chapter 1 (History of Satisfiability), I found the following statement: Moreover, necessary and possible are predicates of the metalanguage (...
4
votes
1answer
61 views

What are predicates of a sentence?

I am reading Handbook of Satisfiability in which they say: An algebraic structure, or simply structure, consists of a non-empty set of objects existing in the world $w$, called the domain and ...
0
votes
0answers
64 views

Is there any difference between information architecture and information structure in case of web apps?

In the course of Web Engineering, the course teacher said in the class of Information Design that site map has 4 main kinds. Linear Layout Hierarchical Layout Grid / Matrix Type Structure Network / ...
2
votes
1answer
38 views

What is a good example to illustrate the difference between isomorphic and homomorphic representations?

I am learning about "knowledge representation" in my intro to AI course and one of the key ideas has to do with isomorphic vs homomorphic representations. The examples I find when I google around are ...
4
votes
0answers
33 views

What is the difference between Cased-based Reasoning and Rule-based reasoning?

As stated here, Rule-based Reasoning systems are considered to be "old style" AI that uses rules prepared by humans - as opposed to Neural Networks where machine recognizes pattern i.e. acquires new ...
1
vote
2answers
59 views

How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?

I was reading CLRS and in theorem 11.1 it states: In a hash table in which collisions are resolved by chaining, an unsuccessful search takes average-case time $\Theta( 1 + \alpha )$, under the ...
2
votes
1answer
59 views

What is the difference between modulo and modulus?

Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably. It looks like even Wikipedia claims that "modulo" is "sometimes called '...
1
vote
1answer
37 views

Revisiting Fixed Point: What does it mean in the world of computer science?

A while ago I asked Fixed point, what does it mean in the world of computer science? While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever ...