Spring 2016»CSCI 230 Homework 4

CSCI 230 Homework 4

Assigned: Sunday, April 3, 2016
Due Date: Thursday, Apr. 14
Due Time: 5 mins before beginning of class

Last modified on April 12, 2016, at 08:39 AM (see updates)

Suffix Trees


Learn about a new data structure (one you have hopefully not seen before), and report your findings to be evaluated.

This is an individual assignment. You must work on your own (but you may talk to the instructor, TA, and/or a librarian).

Learning Outcomes

  • Be able to identify the advantages and disadvantages of the use of specific data structures in specific problem situations.
  • Apply written communication skills to produce a report on a topic of data structures and algorithms.


Write a paper on Suffix Trees. You goal is to produce a paper using the ACM Proceedings format.

  1. Your paper should have an Introduction section, which describes (each in a separate subsection):
    • the data structure itself,
    • how it is constructed,
    • how it is accessed,
    • its complexity, and
    • and its advantages and disadvantages.
  2. Find two papers each describing a distinct, important application of suffix trees (e.g., DNA, music analysis, etc.).
    • These papers should have appeared in a journal or conference (you may search the ACM Digital Library or the IEEE CS Digital Library).
    • These papers must have a reference/bibliography section at the end (i.e., no abstract-only papers, wikipedia articles, or other Internet-only posts.).
    • I.e., we want computer science papers that have gone through normal peer review.
  3. Write a summary of what each paper discusses, i.e., what have you learned from reading it.
    • This should produce two sections, one per paper.
    • For each section, provide a title based on the paper's original title (or a clear description of the area of suffix trees it covers).
    • Beware of plagiarism. Paraphrase, or quote (small amounts, as needed). The paper should consist mostly of your words (not quote after quote).
  4. Write a short "Conclusion and Future Work" section, summarizing
    • what you have learned from the two papers,
    • what other applications areas exist, and
    • how you may potentially use this data structure in the future.
  5. Create a bibliography with, at least, six items.
    • The first two items should be the above papers. You should cite them in your prose - where you use information from them.
    • Look at the references provided at the end the two papers, and highlight two references from each paper that you think would help you learn more about this topic.
    • Add those two references to your bibliography. Again, use the ACM format.
    • Anything you use in your paper should be appropriately referenced. It is OK to use our book as a reference. If so, include page numbers of what you are referencing (very important - use this format, e.g., "pp. 55-58.")
  6. Print the original two papers,
    • highlight interesting passages,
    • Write comments and questions on the margins, and
    • highlight the two references you selected to include in your bibliography.


  1. Submit a printout of your paper at the beginning of class on the due date.
  2. Attach a printout of the two original papers (annotated as described above).
    • The three papers should be stapled carefully together (otherwise we are not responsible if they are separated / misplaced). You may use the department's large volume stapler (in the copy room), if needed.
  3. Be prepared to present what you learned from your article to the class. Your goal is to introduce this state-of-the-art data structure topic to people that have not seen it before.


Your grade will be based on the depth/quality of your work (e.g., explanation, questions, etc.), and your potential class presentation.

Relevant Quote

"We are drowning in information, while starving for wisdom. The world henceforth will be run by synthesizers, people able to put together the right information at the right time, think critically about it, and make important choices wisely." ~ E.O. Wilson