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

learn more… | top users | synonyms

-1
votes
0answers
11 views

What is a 4-way parallel algorithm? [on hold]

What is the definition of a 4-way (or 8-way) parallel algorithm? What means 4-way? How can we implement such an algorithm?
0
votes
0answers
23 views

Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
1
vote
2answers
42 views

Which all nodes will qualify as an ancestor?

I was going through the fundamentals of tree structure and the definition for ancestor is as follows: A node u is an ancestor of v if there is a path from u to v. Consider the node ...
4
votes
5answers
94 views

Please explain a greedy algorithm in a naive manner [on hold]

I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms. From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local ...
3
votes
1answer
34 views

How can an approximation ratio be less than 1?

A question in my algorithms text-book requires that we, Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this problem. It is my understanding that $(1 - \frac{1}{k})$ ...
1
vote
0answers
11 views

What is the meaning of the term 'ware'? [migrated]

In computer science, the term 'ware' is used as the tail of another word like 'software', 'hardware', 'middleware', 'malware', 'firmware' etc. I want to know what is the etymology of the term 'ware' ...
9
votes
3answers
584 views

What is the purpose of using NIL for representing null nodes?

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
2
votes
1answer
27 views

About the definition of “differential privacy” in communication complexity

In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense. So the two parties $A$ and $B$ draw two strings $X$ ...
2
votes
1answer
50 views

Tolerated use of the term topology

In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees : 1) The first one: Node ...
2
votes
1answer
44 views

Depth perception - detect how far into a scene a user is looking

I would like to know about how we can detect how 'deep' into a scene a user is looking. If looking into a 3D environment, with an object close to the user and one further away, how can we detect when ...
-1
votes
0answers
22 views

What is an adaptive cache prefetching policy?

what is meant by the term "adaptive cache prefetching policy" and how is it different from regular methods of prefetching a cache? what are the advantages of adaptive cache prefetching?
0
votes
1answer
53 views

Understanding the definition of endless sets

In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise: I don't understand exactly, what an endless set is (I find it very hard to ...
1
vote
0answers
23 views

Name hiding in c++ [closed]

What exactly is name hiding in c++? what are the advantages? i already went through a couple of links but couldn't get a proper explanation for the same.
0
votes
0answers
39 views

Which of the two properties isn't satisfied?

Show that the following sequence of function $\Phi_n$ is not a measure of complexity: $\Phi_n(x)=\left\{\begin{matrix} \text{ nr of commands } m \text{ that TM } T_n \text{ executes with ...
15
votes
6answers
459 views

What exactly is computation?

I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of ...
7
votes
3answers
383 views

Standard definition of Turing machine

I have followed two famous book on "Automata and Formal Language Theory": Micheal Sipser's book Jeffrey Ullman and John Hopcroft's book in both books, tuple level definition of Turing machine ...
0
votes
1answer
17 views

What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
4
votes
2answers
102 views

What is the formal name for an “entry” in an ontology?

I am trying to wrap my head around ontologies and their related counterparts (RDF, OWL, etc.). My understanding is that an ontology, at the end of the day, really boils down to some database storing ...
0
votes
0answers
13 views

definition of 'vehicle' in consensus theory

I would like to ask about the definition of 'vehicle' in consensus theory. I always encounter that in papers in the following context: Cooperative control of multiple autonomous vehicles poses ...
1
vote
1answer
122 views

What is the difference between cyber security ontologies and scenario ontologies in this system?

I have been reading the paper Towards a Cognitive System for Decision Support in Cyber Operations. And I have been trying to understand the role of two ontologies proposed here, cyber security ...
2
votes
1answer
44 views

What does feedforward inversion mean in the context of convolution and catastrophic codes?

i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication - April 1968) (here) and i cannot understand - what is "feedforward inversion"? ...
5
votes
1answer
60 views

What is the name for the complexity class $O(n^{1+\epsilon})$

Sometimes problems can be solved in $O(n^c)$ time for any $c > 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive ...
0
votes
0answers
27 views

Markov algorithm: pick rule first, then position, or the other way around?

A Markov algorithm is a string rewriting system (well, not a set of rules but a list of rules since they need to be ordered) with a strategy for applying rules that ensures determinism. I think the ...
2
votes
1answer
94 views

What is a contiguous subarray?

What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in ...
4
votes
1answer
51 views

How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of ...
3
votes
1answer
33 views

Why in a min priority queue (heap based) it is called “decrease-key” and not just “set-key”?

When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to ...
2
votes
1answer
45 views

Strongly connected components on a DAG

What is supposed to be the right result of an SCC algorithm running on a DAG. should it return "no components" or "there are V components of size 1"? I suspect it will return the latter (since it ...
1
vote
3answers
98 views

Is there a name for an inverted state machine?

I recently needed something like a state machine, but with a slightly different use case. In general, I would say a state machine knows about a set of states, and different events. Depending on the ...
-1
votes
1answer
25 views

the name of state when data reading from hard drive [closed]

In computer organization and architecture, what is the name of the state when data must be read from hard drive? I have tried to search it on StackOverflow and textbooks but could not find the answer. ...
3
votes
1answer
61 views

the meaning of heuristics in artificial intelligence

I would like to know what 'heuristics' actually means in artificial intelligence. For example, I am reading a paper by Engelbrecht on the convergence analysis of the particles of the algorithm. The ...
1
vote
1answer
70 views

Computer Programs and lambda terms without normal form

λ-calculus an ideal mathematical model in which to interpret programs. A program can be interpreted as a lambda term, and the term can have or not have a normal form. What role the terms without ...
20
votes
2answers
2k views

What does “context” in “context-free grammar” refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
0
votes
2answers
69 views

How to expand 2D graphic and functions to 3D?

So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D. I want to expand the 2D objects and functions to 3D which I don't expect to be too ...
1
vote
2answers
93 views

Terminology - the reason for symbol reuse in programming languages

What is the term in programming language creation that is the rationale for symbol reuse? Though potentially confused with overloading, it is not so much the application of symbol reuse, but the ...
1
vote
1answer
31 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
-1
votes
1answer
36 views

Deterministic processing on probabilistic input [closed]

I've designed an algorithm, is which responsible to process some samples from normal distribution under aegis of some deterministic steps. In other words, the algorithm generate unique response to a ...
8
votes
4answers
299 views

Why is binary search called binary search?

I heard several possible explanations, so I would like some trustable reference. Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from ...
3
votes
1answer
26 views

How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can ...
3
votes
1answer
138 views

How to improve my these specific math skills? [closed]

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite ...
0
votes
1answer
51 views

What is the difference between an embedded system and dedicated system?

To my understanding, a dedicated system is a computer system capable of performing 1 specific task an embedded system is a computer system within a larger system that performs a specific task Is ...
0
votes
2answers
42 views

What does least fix point and greatest fix point mean in Safety games

In safety games there are these mathematical notation about greatest fix points and least fix points but I don't get it. How would we describe them plain English without mathematical symbols.
2
votes
1answer
30 views

Nomenclature for deterministic algorithms that might fail

What do you call an algorithm which is Deterministic When an answer is returned, it is correct For some input, the algorithm returns no answer (fails, in bounded time). Such algorithms crop up a ...
3
votes
3answers
106 views

Splicing squares on a Turing Machine finite tape

Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The ...
-2
votes
1answer
38 views

What's the difference between all these terms?

What's the difference between them - Physically based simulation, Physically based animation, Physical simulation for computer animation, Physically based animation for Computer graphics, Physically ...
8
votes
2answers
378 views

Difference between time complexity and computational complexity

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
0
votes
1answer
39 views

Term Rewriting vs Unification

How is term rewriting different from unification, and what's the difference between term rewriting languages and logic programming, like Prolog?
0
votes
1answer
34 views

A query about serial data transmission

I was studying computer science and I learnt that Serial Data transmission is when one bit is transmitted at a time over one wire/channel. Then what does '8 bit serial' data transmission mean? I was ...
1
vote
2answers
44 views

Instruction level parallelism

Can we distinguish instruction level parallelism and SIMD instructions (SSE, 3D now...) ? Or is SIMD instructions one of the multiple ILP techniques ? Thank you.
0
votes
1answer
35 views

Information Systems (IS) and Data Warehouse

I'm working on a research project about the adoption of DWH systems and doing some literature review I find many documents that refer to Information System. I tried to find the right definition of ...
1
vote
1answer
47 views

Differences between linear/nonlinear vs. deterministic/nondeterministic neural nets

When speaking of neural networks, I don't get the difference between nonlinear and non-deterministic. Basically, both say that the output of something is not directly correlated to the input? Hope ...