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

learn more… | top users | synonyms

-1
votes
0answers
17 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
50 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++ [on hold]

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
38 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 ...
14
votes
6answers
376 views

What exactly is computation?

I know what computation is in some vague sense (i.e. it's the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of computation, computing, calculate, and ...
7
votes
3answers
358 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 ...
-1
votes
0answers
23 views

Evolution of superscalar/multicore/hyperthreaded RISC pipelines [closed]

I have been reading about the how multiprocessing is evolved, but have not found any single source which as unison provide the complete info about how they evolve from time to time and what changes, ...
0
votes
1answer
14 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
100 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
114 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
42 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
56 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
26 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
80 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
31 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
43 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 ...
0
votes
1answer
24 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
52 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
63 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
65 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
92 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
25 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
290 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
24 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
128 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
39 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
40 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
29 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
105 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
36 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
301 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
36 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
32 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
31 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
37 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 ...
6
votes
0answers
110 views

Has there been any attempt to systematically categorize programming puzzles?

Has there been any attempt to systematically categorize programming puzzles? I notice that some problems are similar to one another, or have analogous methods of solution. I would think there must be ...
1
vote
0answers
46 views

Terminology for a graph with ports on its nodes

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain ...
2
votes
2answers
113 views

Does “contains only” imply “contains”?

Written in English, does "the set S contains only members of set T" imply that S does contain some member of set T? How would this relationship be written formally?
1
vote
1answer
90 views

Is there a term for “delegate” function in CS?

This question is all about terminology (names). When you consider "list", this term is well defined in CS -- despite the fact programming languages use and misuse this term (for example C# ...
3
votes
1answer
184 views

What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

Suppose I have a function $f$ on sets. What is the property of $f$ called when, for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$ i.e. $$\forall x,y : ...
0
votes
1answer
34 views

Terminology for describing a kind of server [closed]

What is the adjective used to describe the fact that a server keep track of queries made by a user. I take the example of a database server.
9
votes
2answers
632 views

What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
2
votes
1answer
47 views

What makes a metaheuristic meta?

According to Wikipedia: ...metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may ...
1
vote
1answer
35 views

Shortcut for “in the worst-case, with high probability”?

I am writing a paper in which the worst-case analysis of a certain randomized algorithm is correct with probability $1-1/n$ (where $n$ is the size of the problem). I find myself writing, time after ...