CMPU-181, Spring 2013 Asmt. 3 Instructions Due: Friday, March 1 @ 3:00 p.m. For this assignment you will write an article that describes the BUBBLE-SORT and MERGE-SORT algorithms, and compares their performance. Imagine that you just discovered these two sorting algorithms, but that no one had ever carefully compared their performance on large lists of numbers. Your article should be in the form of a scientific research paper that reports the results of a comparative evaluation of these two search algorithms. Begin, as usual, by creating an asmt3 directory in your own CS account. Go into that directory and start up emacs. Download one of the template TEX files from either asmt1 or asmt2 to get started. Your article must have the following sections: -- Background Describe both the BUBBLE-SORT and MERGE-SORT algorithms. To assist you in this part, you must find at least one article on the web that you can cite as a reference for each algorithm. You must cite your references in your paper as described later on. -- Empirical Evaluation Describe, at a high level, what the Scheme functions in the file, sorting-functions-feb-11.txt, do. (The sorting-functions-feb-11.txt file is located in the asmt3 directory.) Describe how you used them to generate some timing results for the BUBBLE-SORT and MERGE-SORT algorithms on randomly generated lists of numbers. Compare the performance of these two algorithms on various sizes of lists. Look at the comments in the file, sorting-functions-feb-11.txt, for further information on what the functions do and how to use them. Open up the file sample.pdf to see some helpful information about Latex and Bibtex. Also, look at the sample.tex file to see how the sample.pdf file was generated. -- Conclusions Summarize your results and conclude that the MERGE-SORT algorithm is much faster than the BUBBLE-SORT algorithm! --------------------------- Using Bibtex to generate a bibliography section in your paper. First, create a separate plain-text file, called myrefs.bib. (You can call it anything, but it must end with the .bib extension.) This file is your BIBTEX file that contains information about your references. There is a sample myrefs.bib file in the asmt3 directory. Each reference that you cite in your paper must have a BIBTEX entry in the myrefs.bib file. There are several kinds of BIBTEX entries. The ones you use will depend on the kind of reference you are making (e.g., to an article in an academic journal, to a book, to an unpublished article, to a web page, etc.). For example, here's a BIBTEX entry for a journal article by Michael Bratman: @article(bratmanSharedCoopAct, author = "Bratman, Michael", title = "Shared Cooperative Activity", journal = "The Philosophical Review", year = 1992, pages = "327-341", volume = 101, number = 2) And here's a BIBTEX entry for a book by Michael Bratman: @book(book-bratman-87, author = "Michael E. Bratman", title = "Intentions, Plans, and Practical Reason", year = 1987, publisher = "Harvard University Press", address = "Cambridge, MA") Notice the format of these entries. The kind of entry is indicated by @article or @book. The content of the entry is specified between the parentheses. The first bit of content is the name of the entry (e.g., book-bratman-87). This name is for your own use; it can be practically anything you want. The rest of the content stipulates values for a variety of "fields" (or "parameters"). Notice that articles and books have many fields in common, including: author, title and year. However, the article entry has some fields that the book entry does not; and vice-versa. For example, the article entry has fields named journal, volume, number and pages, whereas the book entry has fields named publisher and address. *** Important *** Notice the placement of commas between each bit of content in a Bibtex entry. Notice that anything other than simple numbers must be put inside double quotes. Other kinds of Bibtex entries include the following: inproceedings, incollection, mastersthesis, techreport and phdthesis. You can Google these kinds of entries to find out how they are formatted and the information that they contain. For example, you could Google "Bibtex techreport" to learn about techreport entries. You might also want to find out how to specify multiple authors for a single Bibtex entry. ONCE YOU HAVE SAVED YOUR LATEX and BIBTEX FILES... Suppose your Latex file is named, sample.tex, and your Bibtex file is named, myrefs.bib. Look at the sample.tex file provided in the asmt3 directory to see examples of how to cite references in your Latex file. Notice the "\bibliographystyle" and "\bibliography" commands in the sample Latex file. The latter command tells the bibtex program where to find your Bibtex entries. To run the pdflatex program on your TEX file: pdflatex sample To run the bibtex program on your TEX/BIBTEX files: bibtex sample ==> Execute these commands one after another, a couple of times. Then look at the pdf file, sample.pdf, by typing: acroread sample.pdf =================================== When you are finished creating your paper... * create a new directory for submitting relevant files electronically * copy your TEX, BIB, and PDF files into that new directory * submit that directory using the submit181 command --> Let me know if you have any trouble submitting electronically. Turn in a printout of your PDF file to me, or put it in the box outside my office door. You need not print out your Latex or Bibtex files.