From siva@cs.uh.edu Mon Nov 11 16:06:28 EST 1996 Article: 16805 of comp.theory Xref: utcsri comp.theory:16805 Path: utcsri!rutgers!news.sgi.com!news.tamu.edu!news.mty.itesm.mx!news.uh.edu!siva From: siva@cs.uh.edu (D. Sivakumar) Newsgroups: comp.theory Subject: Re: Any suggestion? Date: 11 Nov 1996 13:02:09 GMT Organization: Department of Computer Science, University of Houston, Main Campus Lines: 31 Distribution: inet Message-ID: < 56784h$b5g@Masala.CC.UH.EDU> References: < 328290B7.97A@mankato.msus.edu> Reply-To: siva@cs.uh.edu NNTP-Posting-Host: eve.cs.uh.edu X-Newsreader: TIN [version 1.2 (PGP) PL2] I wish all students who ask solutions to their HW problems adopt this nice format: (1) The user-id says "student@somewhere" and the "real name" is "ACC student": *> ACC student (student@mankato.msus.edu) wrote: (2) "Cut and paste" the relevant portion of the HW assignment into a file called "HW", and then post from it: *> : Content-Disposition: inline; filename="HW" (3) Do not remove the "problem number", the LaTeX-ese, the homeworkish-sounding phrases "Give a dynamic prog.... Your algorithm should take ..." *> 9. You have $n$ objects that you wish to put in order using the *> relations ``$< $'' and ``$=$''. For example, with three objects *> 13 different orderings are possible. *> $a=b=c$ $a=b< c$ $a< b=c$ $a< b< c$ $a< c< b$ *> $a=c< b$ $b< a=c$ $b< a< c$ $b< c< a$ $b=c< a$ *> $c< a=b$ $c< a< b$ $c< b< a$ *> Give a dynamic programming algorithm that can calculate, as a *> function of $n$, the number of different possible orderings. *> Your algorithm should take a time in $O(n^2)$ and space in $O(n)$. -- D. Sivakumar Assistant Professor of Computer Science, Dept. of CS @ UH

Back to David Neto's Usenet tidbits