Questions about genesis and development of computer science as a scientific discipline and its applications.

learn more… | top users | synonyms

6
votes
1answer
64 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
0
votes
2answers
99 views

Why does binary search take $O(\log n)$ time?

My question seems like an elementary question, but it's really not. Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with ...
-2
votes
1answer
41 views

from when do we have the field of computer vision? [closed]

when was the field of computer vision created and what are the disciplines that gave birth to it? I would appreciate it if you could give some web references that have the answer.
-2
votes
1answer
87 views

Why was Alan Turing important? [closed]

What is the importance of Alan Turing? What were his inventions or innovations and why are they so influential?
2
votes
0answers
59 views

What happened to Active Databases?

When reading the literature on declarative programming technology. A particular technology that sounded promising is active databases. It essentially allows the programmer to specify rules about data ...
29
votes
7answers
2k views

What is the definition of Computer Science, and what is the Science within Computer Science?

I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to ...
2
votes
4answers
237 views

Why is it O(1) (and not, say, O(2))?

If the running time of an algorithm scales linearly with the size of its input, we say it has $O(N)$ complexity, where we understand N to represent input size. If ...
5
votes
6answers
5k views

Why do we need assembly language?

We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with ...
7
votes
0answers
169 views

Who are the legislators of Paxos?

In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol. According to this ...
1
vote
0answers
298 views

Difference between Analytical and Difference Engines

I'm not sure if one can compare the two, mainly because what I've read so far, I didn't quite understand, but what are the key differences between these 2 engines?
3
votes
2answers
131 views

Parallel Computing: Past Vs Present

Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on ...
7
votes
2answers
900 views

Why is the laplace transform not popular for image processing convolution?

Why is the laplace transform not popular for image processing convolution? Most textbooks only conver the Fourier transforms.
3
votes
1answer
111 views

Why the name Recursively Enumerable and Recursive? [duplicate]

Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?
4
votes
1answer
103 views

Origin of theta-joins

I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A ...
12
votes
2answers
668 views

How are programming languages and foundations of mathematics related?

Basically I am aware of three foundations for math Set theory Type theory Category theory So in what ways are programming languages and foundations of mathematics related? EDIT The original ...
2
votes
1answer
121 views

Understanding Dijkstra's notation $f.x.y$

I recently discovered that I have a fondness for the work of Dijkstra. I am currently reading random EWDs, and stumbled across one with some notation that I couldn't quite grasp. Dijkstra states that ...
-1
votes
1answer
97 views

Where did the terms memory pool and memory leak come from?

I wonder where those terms came from. Is it computer science related? Or are they related to civil engineering, or swimming sports? Is it some analogy with filling water in a pool, or something ...
9
votes
2answers
416 views

Importance of recursion in computability theory

It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?
2
votes
0answers
85 views

Are there some popular science videos on computer algorithms to recommend?

I am seeking for some popular science videos on computer algorithms for my last lecture delivered in this term. The topic of the videos includes but are limited to algorithm design, algorithm ...
5
votes
1answer
106 views

Origin of quantum complexity theory

Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?
10
votes
3answers
503 views

What is the origin of the client server model?

I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?
7
votes
2answers
99 views

Who (and when) first defined interval graphs?

I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949. So, I'm trying to track down the original paper ...
3
votes
2answers
312 views

Don Knuth and MMIXAL vs. Chuck Moore and Forth — Algorithms and Ideal Machines — was there any cross-pollination / influence in their ideas / work?

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms? I'm interested in citations, ...
5
votes
1answer
98 views

Who conceived the concept of Discrete Event Simulation, and when?

I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of ...
7
votes
1answer
299 views

Origins of the term “distributed hash table”

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...
6
votes
1answer
163 views

Historical relation between computer science and the theory of dynamical systems

I have asked this question at math.stackexchange, but I have been redirected here. My question is, if there is any historical relation between the fields of Dynamical systems (and related fields such ...
11
votes
2answers
338 views

Why is Turing completeness right?

I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can ...
46
votes
5answers
7k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either ...
22
votes
2answers
667 views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
4
votes
2answers
106 views

When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction?

It seems as though modern speech recognition (e.g., through Android, iOS phones) make use of grammar or sentence structure. (e.g., it might have a tough time distinguishing between "grammar" and ...
29
votes
5answers
3k views

Why has research on genetic algorithms slowed?

While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on ...