Subject: RE: [hackers-il] Re: An Analysis of the Joel Test in regards to O S [was Re: Rules for Open Source development (the serious version)]

From: Chen Shapira <[email-masked]>
Date: Wed, 23 Jan 2002 19:19:40 +0200

> Is computer science a science then? (I'd say yes, but then 
> again, I'd say
> yes to engineering in general)
> What's the difference between SE and CS?

IMO, CS isn't a science, and it isn't about computers either.

Sciences are deeply related to the scientific method. 
So, a scientist has a theory, he formulates an experiment to test his
theory, runs the expiriment several zillion times to make it statisticaly
significant and then discusses the results and either change the theory or
the experiment.

CS isn't even remotely like this (except debugging, which is a bit like a
science). 
In CS theories are proven by mathematic methods, not by experiments. No one
runs an algorithm with diffrent inputs and times it to learn how fast it is.

So CS is a bit more like Math. A method-developing meta-science.
Except while math deals with sets and functions, CS deals with processes.

Thanks, 
Chen.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 23 Jan 2002 22:39:28 -0500

Chen Shapira <[email-masked]> writes:

> Sciences are deeply related to the scientific method. So, a
> scientist has a theory, he formulates an experiment to test his
> theory, runs the expiriment several zillion times to make it
> statisticaly significant

Well, not always ;-) There wouldn't be much of a scientific progress
it that were a requirement...

The key word is reproducibility of experimental results, and honesty
about assumptions and limits of applicability (see Feynmans famous
"Cargo Cult" address).

> In CS theories are proven by mathematic methods, not by
> experiments. No one runs an algorithm with diffrent inputs and times
> it to learn how fast it is.

Oh yes, they do. At least in the fields of algorithms, complexity
analysis, etc, etc. If you develop a new algorithm that works as NlogN
rather than the state-of-the-art N^2, you do run tests and plot the
graphs, and then others check your results (reproduceability).

Disclaimer - IANAC(omputer)S(cientist) by training, but I dare say I
do have some limited experience with CS literature.

While CS can be considered close to applied math, it's close enough to
the iron to be related to engineering (so it much of solid state
physics - another field where theoretical work is done using
sophisticated mathematical methods, but experiment is crucial, just to
provide an analogy). Not software engineering though, which is quite
different.

-- 
Oleg Goldshmidt | [email-masked] 
If it aint't broken it hasn't got enough features yet.

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 24 Jan 2002 13:51:07 +0200 (IST)

> IMO, CS isn't a science, and it isn't about computers either.

To quote Dijkstra:

"Computer Science is no more about computers, than Astronomy is about
telescopes."

However, I do not entirely agree with this claim. FOA, Computer Science,
like any other science, holds many fields and schools: plain algorithmics,
OOP, FP, databases, typing systems, Operating Systems, cryptography and
cryptology, AI, and I could go on. They are all lying under the umbrella
named Computer Science. As someone who studies Electrical Engineering, I
can tell that it is as diverse as CS is, and I suppose the same applies to
other fields.

Programming in some language requires thorough understanding of how a
computer works and runs programs. I can testify for that from my
experience on Freecell Solver. CS is named so because despite that on %99
percent of the cases,  one will write a program in a Turing Universal
programming language, to implement its theory. That's why it has a lot to
do with computers.

Naturally, knoweldge of CS can help in real-life. But, so does knowledge
of other fields, as all human knowledge is contigious.

> significant and then discusses the results and either change the theory or

Then can you argue that Mathematics is not a science? I disagree. In
physics, you may have to perform experiments to demonstrate what happens.
But the end result is that one will have to build a model to explain
what's going on behind the scenes.

As for mathematics, it is also experimental. A proof cannot be held valid
if one finds a case when it is wrong. And moreover, many mathematical
theorems emerged from noticing the various sub-cases that were collected
over the years.

> runs an algorithm with diffrent inputs and times it to learn how fast it is.

Actually, I saw graphs plotting the performance of the various sorting
algorithms at least twice. O(n) can be 2*n and it can be 10^6*n - one
still has to benchmark to evaluate the performance.

Regards,

	Shlomi Fish

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Eran Tromer <[email-masked]>
Date: Sun, 27 Jan 2002 01:07:39 +0200

> runs an algorithm with diffrent inputs and times it to learn how fast it is.

Sadly, sometimes we do -- when we can't obtain a sufficiently tight 
analysis. For instance, consider the Lenstra-Lenstra-Lovasz (LLL) 
algorithm [1].

The problem addressed (Shortest Vector Problem) is an optimization 
problem which, in general, is NP-complete (moreover, it's NP-hard to 
approximate within some constant factor). The LLL algorithm runs in 
polynomial time, but is only proved to produce a solution that is 
roughly 2^n times worse than the optimal solution (i.e., exponentially 
far off). However, in practice for certain parameters LLL invariably 
gives significantly better results. For instance, it been successfully 
used to break some cryptographic schemes even though the proven bounds 
on the output quality would suggest otherwise.

So, what to people do to show the security of their cryptographic 
schemes in light of attacks based on reduction to the Shortest Vector 
Problem? You guessed it -- they perform experiments with well-known 
implementations of LLL, and report the empirical results [2]...

It should be noted that many great minds have tried to produce a better 
analysis of this algorithm, to no avail to date.

Other cases where we have an algorithm we don't fully understand (in a 
similar sense) include the simplex method for linear programming and the 
Buchberger algorithm for computing Grobner bases.

   Regards,
     Eran Tromer

[1] For a brief introduction and a review of applications see
     http://citeseer.nj.nec.com/joux94lattice.html
     For in-depth coverage of the theory see
     http://theory.stanford.edu/~csilvers/cs359/
[2] Examples:
     http://www.ntru.com/NTRUFTPDocsFolder/NTRUTech012.ps.gz
     http://www.wisdom.weizmann.ac.il/~oded/PS/cfh.ps