Theoretical Computer Science

Hi Dears,
I am student of 1st year computer science i have covered following
topics ,
FOR, WHILE, DO WHILE LOOPS, IF, IF-ELSE, SWITCH, FUNCTIONS, ARRAY,
STRINGS AND POINTERS.
Our teacher tell us to make a program of your choice which have 25
marks , plz tell me what program I design which is different from
others and gets me 25 marks .
Plz send me output of your idea .
Thanks

Hi,

The following LP gives the solution to bipartite matching problem
( linear assignment)  with a cost matrix C.

max \sum_{ij} A_{ij}C_{ij}
s.t.  \sum_i A_{ij} = 1 \forall j
       \sum_j A_{ij} =  1 \forall i
        A_{ij} \ge 0

The solution A is guaranteed to be a permutation matrix.
In my research, I have come across a problem where I have
an additional constraint on A. It is something like

w(Ax) + b \ge 1

however, it is evident that if I add this as an additional constraint
to the above LP, A is no longer guranteed to be a permutation
matrix. I still need to retrieve a permutation matrix A imposing
the half space constraint. Can somebody help me how to impose
additional constraints on  A so that it becomes permutation matrix
even with the halfspace constraint? In a nutshell, I want A to
permute x so that it is in the required half space while maximizing
the cost.

I thought of finding the maximum from each row and each column of
A and restrict them to  be one, however, i could only think of ways to
upper bound the maximum. Any help would be  greatly appreciated.

Thanks
–Pannaga

Hi,

Many books define nondeterministic turing machines as those which have
the power of guessing the answer and verifying the answer in polynomial
time. Some say that they are given a certificate, using which they
verify the answer to a problem in polynomial time. Still others define
them to have witness strings which are similar to the certificates
using which the NDTM can verify the solution to a problem in polynomial
time.

Can someone give me a good intuition for the above definitions,
especially those based on "guessing" and "certificates"?

Please let me know if there are any online resources/text books that
give a good intuition for the same.

Thanks a lot,
Vinod.

                           Call for Papers
                             IWPEC 2006
  The 2nd International Workshop on Parameterized and Exact Computation
              Zuerich, Switzerland, September 13 – 15, 2006

Note: Deadline is extended till April 24, 2006.

Overview

The International Workshop on Parameterized and Exact Computation covers
research in all aspects of parameterized and exact computation and
complexity, including but not limited to: new techniques for
the design and analysis of parameterized and exact algorithms,
parameterized complexity theory, relationship between parameterized complexity
and traditional complexity classifications, applications of parameterized
computation, implementation issues of parameterized algorithms,
high-performance computing and fixed-parameter tractability. The goal is
to present recent research results, including significant
work-in-progress, and to identify and explore directions for future research.

IWPEC 2006 will be part of ALGO 2006, which also hosts ESA, WAOA, WABI, and
ATMOS. ALGO 2006 will take place September 11 – 15, 2006 in Zuerich,
Switzerland. The proceedings of IWPEC 2006 will be published in the
Springer series Lecture Notes in Computer Science.

Submissions

Authors are invited to submit an extended abstract in English no longer than
12 pages using at least 11-point font describing original unpublished
research. Simultaneous submission to other conferences with published
proceedings is not permitted. Additional details as necessary may be
included in a clearly marked appendix that will be read at the discretion of
the program committee.
Authors must submit their papers electronically at
http://borbala.cs.uu.nl/iwpecpapers/submit/ .
Authors unable to submit electronically should
contact either of the Program Co-Chairs. Accepted papers are expected to be
presented at the workshop.

Important Dates
Paper submission deadline: April 24, 2006; 23.59 GMT. (Note: extended
deadline.)
Notification of acceptance: May 26, 2006
Workshop: September 13 – 15, 2006

Program Committee

Hans L. Bodlaender (co-chair), The Netherlands
Jianer Chen, USA
Frank Dehne, Canada
Erik D. Demaine, USA
Rodney G. Downey, New Zealand
Michael R. Fellows, Australia
Henning Fernau, United Kingdom
Joerg Flum, Germany
Fedor V. Fomin, Norway
Martin Grohe, Germany  
Edward A. Hirsch, Russia
Kazuo Iwama, Japan
Michael A. Langston (co-chair), USA
Daniel Marx, Germany
Catherine McCartin, New Zealand
Naomi Nishimura, Canada
Uwe Schoening, Germany
Ulrike Stege, Canada
Venkatesh Raman, India
Peter Rossmanith, Germany
Jan Arne Telle, Norway
Dimitrios M. Thilikos, Spain/Greece
Sue Whitesides, Canada
Gerhard J. Woeginger, The Netherlands

IWPEC Steering Committee

Jianer Chen, Frank Dehne, Rodney G. Downey, Michael R. Fellows,
Michael A. Langston, Rolf Niedermeier, Venkatesh Raman

More information

More information can be found on the following websites:
– ALGO website: http://algo06.inf.ethz.ch/
– IWPEC-06 website: http://algo06.inf.ethz.ch/iwpec
– Website on IWPEC-series: http://www.scs.carleton.ca/~dehne/iwpec/
– Submitting a paper to IWPEC-06: http://borbala.cs.uu.nl/iwpecpapers/submit/
—
Hans Bodlaender – Institute of Information and Computing Sciences
Utrecht University – P.O. Box 80.089 – 3508 TB Utrecht – the Netherlands
ha…@cs.uu.nl                     http://www.cs.uu.nl/~hansb/index.html

APOLOGIES FOR MULTIPLE COPIES

===============================================================

                      IEEE Hot Interconnects 14
                        FINAL CALL FOR PAPERS
               Stanford University, Palo Alto, CA  USA
                          August 23-25, 2006

                            IMPORTANT DATE
                  Submissions deadline extended to
                     April 22, 2006 (Midnight, EDT)
                 http://www.hoti.org/hoti14/cfp.html

                           Sponsored by the
                          (Pending Approval)
                        IEEE Computer Society
  Technical Committee on Microprocessors and Microcomputers (TCMCOMP)
                   Technical co-sponsorship by the
                     IEEE Technical Committees on
                    High-Speed Networking (TCHSN)
             Communications Switching and Routing (TCCSR)

The international forum where the high-performance computing and high
speed networking communities meet.

–

Hot Interconnects is the premier international forum for researchers
and developers of state-of-the-art hardware and software architectures
and implementations for interconnection networks of all scales,
ranging from on-chip processor–memory interconnects to wide-area
networks. This yearly conference is very well attended by leaders in
industry and academia.  The atmosphere provides for a wealth of
opportunities to interact with individuals at the forefront of this
field.

Themes include cross-cutting issues spanning computer systems,
networking technologies, and communication protocols.  This conference
is directed particularly at new and exciting technology and product
innovations in these areas.  Contributions should focus on real
experimental systems, prototypes, or leading-edge products and their
performance evaluation.  In addition to those subscribing to the main
theme of the conference, contributions are also solicited in the
topics listed below.

TOPICS

 * Novel and innovative interconnect architectures
 * Multicore processor interconnects
 * Advanced chip-to-chip communication technologies
 * Optical interconnects
 * Protocol and interfaces for interprocessor communication
 * Survivability and fault-tolerance of interconnects
 * High-speed packet processing engines and network processors
 * System and storage area network architectures and protocols
 * High-performance host-network interface architectures
 * High-bandwidth and low-latency I/O
 * Tb/s switching and routing technologies
 * Innovative architectures for supporting collective communication
 * Novel communication architectures to support grid computing
 * New results with backplanes for Advanced Telecom Computing
Architecture
   (ATCA) networking systems

SUBMISSION GUIDELINE

 * Papers need sufficient technical detail to judge quality and
   suitability for presentation.
 * Submit title, author, abstract, and full paper (six pages,
   double-column, IEEE format)
 * Papers should be submitted electronically at the specified link
   location found on http://www.hoti.org
 * Submission deadline (extended to): April 22, 2006 (Midnight, EDT)
 * Notification of acceptance: May 18, 2005
 * For further information, please, see
   http://www.hoti.org/hoti14/cfp.html

ABOUT THE CONFERENCE

 * Conference will be held at the William Hewlett Teaching Center at
 Stanford
   University
 * Papers selected will be published in proceedings by the IEEE
   Computer Society
 * Revised versions of selected papers will be invited to a special
   issue of IEEE Micro magazine
 * Presentations are 30-minute talks in a single-track format Online
   information at http://www.hoti.org

GENERAL CO-CHAIRS
 * Fabrizio Petrini, Pacific Northwest National Laboratory
 * James P.G. Sterbenz, University of Kansas

TECHNICAL CO-CHAIRS
 * Tal Lavian, Nortel Networks Labs and University of California at
Berkeley
 * Dhabaleswar (DK) Panda, The Ohio State University

PROGRAM COMMITTEE MEMBERS
 * Adnan Aziz              University of Texas, Austin, USA
 * Alan Benner             IBM, USA
 * Andrea Bianco           Politecnico di Torino, Italy
 * Ron Brightwell          Sandia National Laboratory, USA
 * Piero Castoldi          Scuola Superiore Sant’Anna, Italy
 * Sarang Dharmapurikar    Washington University, St. Louis, USA
 * Hans Eberle             Sun Microsystems, USA
 * Juanf Fernandez         University of Murcia, Spain
 * Andrea Fumagalli        University of Texas, Dallas
 * Paolo Giaccone          Politecnico di Torino, Italy
 * Mitchel Gusat           IBM Zurich, Switzerland
 * Doan Hoang              University of Technology, Sydney, Australia
 * Olav Lysne              Simula Research Lab, Norway
 * Pankaj Mehra            HP, USA
 * Rami Melhem             Univ. of Pittsburgh, USA
 * Cyriel Minkenberg       IBM Zurich, Switzerland
 * Greg Pfister            IBM, USA
 * Yuval Shavitt           Tel Aviv University, Israel
 * Craig Stunkel           IBM T.J. Watson Research Center, USA
 * Anujan Varma            University of California, Santa Cruz, USA
 * Joe (Zuoguo) Wu         Intel, USA

PUBLICITY CO-CHARS
 * Luca Valcarenghi, Scuola Superiore Sant’Anna
 * Rajeev Sivaram, IBM Research

PUBLICATION CHAIR
 * Ron Brightwell, Sandia National Laboratories

FINANCE CHAIR
 * TBA

TUTORIAL CHAIR
 * Luca Valcarenghi, Scuola Superiore Sant’Anna

WEBMASTER
 * Liz Rogers, LRD Group

STEERING COMMITTEE
 * Allen Baum, Intel
 * Lily Jow, Hewlett Packard
 * Mark Laubach, BroadBand Physics
 * John Lockwood, Washington University in St. Louis
 * Daniel Pitt, Santa Clara University

===== http://www.hoti.org/ ======

–
—
Luca Valcarenghi, Ph.D.
Scuola Superiore Sant’Anna di Studi Universitari e di Perfezionamento
Sant’Anna School of University Studies and Doctoral Research
Center of Excellence for Communications Networks Engineering (CEIRC)
via G. Moruzzi 1, 56124, Pisa (PI), Italy
ph.: +39-0505492138
fax: +39-0505492194
web: http://www.pisa.cnit.it/people/Members/valcarenghi

Hello all,
 I am working on an algorithm for subgraph isomorphism detection. I am
looking for some sample graphs to test it. I would greatly appreciate
if anyone could provide me with links/references to some sample graphs,
preferably obtained from some application domain(chemical, vision etc).

Thanks in Advance.

- Raju

P.S: I am aware of the graphs available at
http://amalfi.dis.unina.it/graph/ and have already tested my algorithm
on these.

What is the best way to multiply a chain of matrices with dimensions that
are 10×5, 5×2, 2×20, 20×12, 12×4 and 4×60?

Thanks.
Jessica

Hi. I’m looking for a good solution to this problem:

Lets say I have a container of timestamped events. The timestamps don’t
have to be unique – it’s likely that more than one event can be
scheduled to happen at the exact same time – and nothing can be assumed
about the temporal distribution of events. The container must support
insertion and deletion of events. Then I need an operation that lets me
iterate over all events in a given interval, where the events in that
interval get visited in a sorted manner.

First I thought of balanced binary search trees, but it’s not clear to
me how searching and traversal could be combined (sorry if it’s
obvious). Yet I’m looking for something with similar amortized costs –
O(log(n)) for insertion and deletion. O(log(n)) for setting up an
iterator, and O(n) to iterate over the next n events.

Hy everyone. An amazing opportunity for you. You can browse all the
information related to the Beach Houses, Form Houses & cars. So plan
your weekend with your family. Effort less thing, just  make look over.

 www.eazyrentals.com

   It’s not a Spam, If not interested pls ignore this mail.