Yong Luo | 1 Dec 13:45 2006
Picon

How fast is the fastest sorting program in type theories?

[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]

Dear all,

I would like to know the complexity of Quicksort in type theories.

According to private conversation, the complexity of Quicksort in type
theories is: Cubic. But I am not sure whether it is a correct analysis.

I have implemented a type theory with pattern matching. The complexity of
Quicksort is O(n log n) in the best case (see the following link for
details).
 http://www.cs.kent.ac.uk/people/staff/yl41/TPF.htm

The complexity of Quicksort might be different for different
implementations. I would like to collect all the results and make a
comparison.

Thank you,

Yong
==============================
Dr. Yong Luo
Computing Laboratory
University of Kent

Yong Luo | 5 Dec 15:05 2006
Picon

Is Quick Sort slower than Insertion Sort in type theories?

[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]

Dear all,

I posted an email about Quick Sort few days ago. Thank you for your reply.

Insertion Sort is primitive recursion, so it is easy to program it in type
theories and the average complexity is O(n^2).

Quick Sort is not primitive recursion, so there are proofs in the program
when it is programmed in type theories. I am told that the average
complexity "might" be O(n^3), or might be worse. Please let me know if you
know of any work on this.

Regards,

Yong
==============================
Dr. Yong Luo
Computing Laboratory
University of Kent

Erik Ernst | 6 Dec 22:19 2006
Picon
Picon

[TYPES/announce] ECOOP 2007 - CFC, with last CFP - ONE WEEK

[ The Types Forum (announcements only), 
     http://lists.seas.upenn.edu/mailman/listinfo/types-announce ]

- Apologies for multiple copies -

  *** ECOOP 2007 ***

The 21st European Conference on Object-Oriented Programming, ECOOP 
2007, http://2007.ecoop.org/, will be in Berlin, Germany, on July 30 
to August 3, 2007.  The deadline for submission of technical papers 
is in one week, and this is the last call for papers.  Two other 
submission deadlines are in two weeks.

Submission dates (firm deadlines):
  - Technical papers: December 13, 2006
  - Workshop proposals: December 20, 2006
  - Tutorial proposals: December 20, 2006

The ECOOP 2007 conference invites high quality technical papers 
presenting research results or experience in all areas relevant to 
object technology, including work that takes inspiration from or 
builds connections to areas not commonly considered object-oriented.  
Submission at http://cyberchairpro.borbala.net/ecooppapers/submit/.  
For more details, please visit http://2007.ecoop.org/mainconf/.

ECOOP 2007 invites proposals for workshops addressing different areas 
of object-oriented technology.  Workshops should serve as a forum for 
exchanging late breaking ideas and theories in an evolutionary stage.  
For more details see http://2007.ecoop.org/workshops/.

(Continue reading)


Gmane