Computer Science 690A, Fall '22
Course Diary:

Research Methods in Computer Science I

---

Copyright 2022 by H.T. Wareham
All rights reserved

---

Week 1, Week 2, Week 3, Week 4, Week 5, Week 6, Week 7, (In-class Exam #1 Notes),
Week 8, Week 9, (In-class Exam #2 Notes),
Week 10, Week 11, Week 12, Week 13, (end of diary)

Tuesday, September 6 (Lecture #1) (FS)

• Introduction to CS 690A/B: Content and Logistics (Slides)

Thursday, September 8 (Lecture #2) (FS)

• Giving Talks for Fun and Enlightenment (Slides)
  • Example talks (Talk #1 slides, Talk #2 slides)

Tuesday, September 13 (Lecture #3) (FS)

• Giving Talks for Fun and Enlightenment (Cont'd) (Slides)
• Example Talks:
  • Talk #0 (non-specialist audience / 50 minutes)
  • Talk #2 (non-specialist audience / 20 minutes)
  • Talk #3 (specialist audience / 25 minutes)
  • Talk #4 (specialist audience / 16 minutes)

Tuesday, September 20 (Lecture #4) (FS)

• Typesetting Documents: Fun with LaTeX
  • Introduction: What is LaTeX?
    • TeX is a document typesetting system that was created by Donald Knuth in the late 1970s to "simplify" the creation of his multi-volume series The Art of Computer Programming.
    • LaTeX ("Lamport TeX") is a simplified document typesetting system layered on top of TeX that was created by Leslie Lamport in the early 1980s.
    • TeX and LaTeX do typesetting using text markup commands (unlike "What You See Is What You Get" (WYSIWYG) document typesetting systems like MS Word).
    • LaTeX is the standard system used in scientific publishing for conference and journal papers as well as books.
  • Basic LaTeX Document File Format (Sections 2, C.2, and C.5, LL)
    • By convention, all LaTeX document files have extension .tex, e.g., blah.tex.
    • LaTeX file structure:

      [document-start command]
      [preamble]
      \begin{document}
      [document body]
      \end{document}
      	      

    • The document-start command is a single line of the form \documentstyle[OPT]{TYP} or \documentclass[OPT]{TYP}, where OPT is a comma-separated list of typesetting options and TYP is a one-word document type. For the moment, we will focus on document-options list 12pt and document-type article.
    • The preamble contains various commands adjusting and/or augmenting the default typesetting settings defined by the document-type.
    • The document body contains all text, tables, figures, bibliography, etc that appear as the typeset document. All typesetting commands start with a left-slash (\); otherwise, all characters in the document body are treated as plain text to by typeset.
  • Sectioning Commands and Footnotes (Sections 2.2.1, 2.2.3, C.3.3, and C.4, LL)
    • There are four basic levels of section commands denoted by \section{TITLE}, \subsection{TITLE}, \subsubsection{TITLE}, and \subsubsubsection{TITLE}. These are automatically numbered. If section numbers are not wanted, place a star before the left curly brace in the command, e.g., \section*{TITLE}.
    • After command \appendix, all section-commands create appendices and their appendix-subsections.
    • A footnote with text FBODY that is marked by an automatically-numbered superscript is created using command \footnote{FBODY}.
  • Converting LaTeX Document Files to PDFs (Take I)
    • There are two ways to convert a LaTeX document file to a PDF file:
      • Convert the LaTeX file blah.tex to a DVI file via the command latex blah and convert the DVI file to a PDF via dvipdf blah.
      • Convert the LaTeX file blah.tex to a PDF directly via the command pdflatex blah.
  • Example: A sample Latex document v1.0 [example1.tex, example1.pdf, example1.script]
  • Text and Fonts (Sections 3.1, 6.7, and C.15, LL)
    • Each (possibly multi-line) block of text separated by one or more blank lines is treated as a paragraph. Don't worry about making paragraph-text margins even -- LaTeX does that for you automatically (though not always correctly; we'll talk more about how to fix such screwups later).
    • To override indenting at the beginning of a paragraph, use command \noindent.
    • To change the font or text-size of a block of text, enclose that block in curly braces and put the appropriate commands just inside the left curly brace.
      • There are seven font-sizes you can access easily -- \footnotesize, \small, \normalsize, \large, \Large, \LARGE, and \huge.
      • There are five font-types you can access easily -- \rm (Roman), \em (italics), \bf (bold face), \sc (small caps), and \tt (teletype).
      • To simultaneously change font-type and size, put the appropriate font-type command after the size command, e.g., {\large \bf ...}.
    • To insert blank horizontal or vertical space, use the commands \hspace*{AMT} and \vspace*{AMT}, respectively, where AMT is some number followed by a distance unit, e.g., 0.78in, 5mm. To go to the top of the next page, use \newpage.
  • Example: A sample Latex document v2.0 [example2.tex, example2.pdf, example2.script]

Tuesday, September 27 (Lecture #5) (FS)

• Typesetting Documents: Fun with LaTeX (Cont'd)
  • Text Environments (Sections 2.2.4, 3.4, 6.5, 6.6, C.6, and C.8.3, LL)
    • A text environment ENC is a region of the document enclosed by commands \begin{ENV} and \end{ENV} in which special properties hold.
    • There are four basic types of text environments in LaTeX:
      • display environments: These include quotation (center text in environment in left- and right-indented block), center (center each line of text in the environment, where lines end in backslash newline (\\)), and verbatim (display text as given (including spacing and newlines) in teletype font).
      • list-type environments: These environments enclose lists of text-block items, each of which start with command \item.
        • Get bullet-preceded items with itemize, automatically numbered items with enumerate, and items preceded by arbitrary specified text or symbol X with description (in this case, starting items with a \item[X] command).
        • While an item's text continues until either another \item is encountered or the list-environment is terminated, you may want to enclose that text in curly-braces to be sure you know what is part of a particular item.
        • When itemize and enumerate environments are nested, the initial item-symbol or number changes automatically (in the case of enumerate, to alphabetical and then lower-case Roman numbering); depending on the document-type, this may also involve font-size changes. Depending on what you want, you may need to hand-code using nested description environments.
          • To ensure nested environments are parsed correctly, use curly-braces to delimit items; to ensure readability, consider indenting to indicate nesting (just like one does in computer programs).
      • theorem-type environments: These environments are automatically numbered, have an initial boldface title followed by the number, and the specified text in italics.
        • Depending on your document-type, these may or may not be predefined. For example, in article-type, you have to define these yourself.
        • To define your own theorem-like environments ENC with initial title Env, put command \newtheorem{ENV}{Env} in the preamble, e.g., \newtheorem{lemma}{Lemma}.
        • Each theorem-like environment by default has its own numbering-counter that starts at 1. It is possible for two or more theorem-like environments to share the same counter.
        • Some document-types include a predefined proof environment; however, you may have to define your own (please see example3.tex below for one way of doing this).
  • Example: A sample Latex document v3.0 [example3.tex, example3.pdf, example3.script]
• Typesetting Mathematics (Sections 3.3 and C.7, LL)
  • In-line math is surrounded by the dollar-sign delimiter ($ / $).
  • Separate one-line math is surrounded by the bracket delimiters (\[ / \]) if you don't want an automatically-generated equation number and the equation environment delimiters (\begin{equation} / \end{equation}) if you do.
  • Multi-line equations with each line numbered as a separate equation are created using the eqnarray text environment; the version without equation numbers is created using the eqnarray* text environment.
  • Basic constructs:
    • Superscript: x^y
    • Subscript: x_y
    • Arithmetic: +, -, *, \times, /
    • Relational: =, \neq, <, >, \leq, \geq
    • Logarithm to base B: \log_B EXPR
    • Square root: \sqrt{EXPR}
    • Fraction: \frac{TOP}{BOTTOM}
    • Choice: \left( \begin{array}{c} TOP \\ BOTTOM \end{array} \right)
    • Summation: \sum_{INDLOWER}^{INDUPPER} EXPR
    • Product: \prod_{INDLOWER}^{INDUPPER} EXPR
    • Calligraphic version of symbol X: \cal{X}
      • A \cal{} command can seriously disrupt the interpretation of subsequent material in a math expression; hence, it is often a good idea to break a math expression to put a \cal{} on its own, e.g., rewrite $\cal{R} = \{ x ~ | ~ x > 15\}$ as $\cal{R}$ $= \{ x ~ | ~ x > 15\}$.
  • There are a staggering number of additional math symbols and constructs available; a useful summary of the symbols is given here.
  • When in doubt, indicate precedence and grouping by curly braces; to print curly braces, precede them by a backslash.
  • All math will be typeset in italics; to get embedded text to display correctly, force it into Roman font and enclose with tildes to get proper spacing, e.g., $x = \{ i ~ | ~ i > 0 ~ {\rm and} ~ b(i) = True\}$.
• Example: A sample Latex document v4.0 [example4.tex, example4.pdf, example4.script]
• Typesetting Tables (Sections 3.5 and C.9.1, LL)
  • The overall table-specification is included in the table text environment; within this environment, one specifies a table and caption and where they should be placed.
  • The \begin{table} command takes an optional argument specifying that the table should be placed in the text (if at all possible) here (h), at the top of the page (t), at the bottom of the page (b), or alone on a separate page (p), e.g., \begin{table}[p].
    • This is actually a stated preference rather than an obeyed directive -- LaTeX has various table positioning assumptions that sometimes result in the table being placed somewhere else. We discuss below under "Debugging LaTeX" how to deal with this.
  • The table caption is specified as the argument of the \caption command, e.g., \caption{Some decidedly odd figures.}.
    • The caption can be placed above or below the tabular text environment to obtain captions above or below the table proper.
    • When using documents that automatically create a list of tables using the listoftables command, multi-line captions will be reprinted in their entirely. To avoid this, specify the first line of the caption (the caption title proper) again in an optional argument to caption, e.g., \caption[line 1]{line 1. line 2 ... line n.}.
  • The table itself is specified in the tabular text environment.
    • The column-structure of the table is specified by an argument that consists of a sequence of specifications of how text is placed in each column. The three basic specifications for column text placement are centered (c), left-justified (l). and right-justified (r), e.g., \begin{tabular}{c l l r c}.
    • Each row is specified by a list of the text in each column such that the column-texts are separated by ampersands (&) and the row is terminated by \\.
      • Text spanning multiple columns can be created using command \multicolumn{NUM}{SPEC}{TEXT}, where NUM is the number of columns to be spanned and SPEC specified how TEXT is to be placed within that spanned space.
      • Any vertical bars following the last spanned column must be specified in SPEC (see below).
    • Horizontal bars between rows are created using \hline; to get a double bar, use \hline\hline.
      • In a row with columns 1, 2, ..., n, to obtain a partial horizontal bar starting at the beginning of column x and finishing at the end of column y, use command \cline{x-y}.
    • Vertical bars between columns are created using |-characters in the tabular column-structure argument; to get a double bar, use ||, e.g., \begin{tabular}{ | c || l | l | r || c |}.
    • Column-widths are set automatically to accommodate the widest given column-element. To get even spacing, consider adding a "blank" row in which each column has an appropriate \hspace* command.
    • By default, the table proper is left-justified on the page; to center the table proper, place command \centering immediately before the beginning of the tabular text environment.
  • If one wants more vertical space between the table proper and the caption or around the table as a whole and other document text, this can be done using \vspace* commands placed appropriately within the table text environment.
• Referring to Tables (and Figures and Other Things) (Sections 4.2 and C.11.2, LL)
  • The numbers associated by LaTeX with automatically numbered entities such as sections, appendices, equations, tables, and figures can be captured using the command label{LAB} where LAB is an arbitrary character-string label, e.g., \label{TabResults}, \label{SectIntro}.
    • Place section and appendix label-commands right after the section commands that start those sections and appendices.
    • For equations, tables and figures, place the label-command anywhere within the text environments defining those entities.
  • To print the number associated with a defined label, use command \ref{LAB}, e.g., Table \ref{TabResults}, Section \ref{SectIntro}.
• Converting LaTeX Document Files to PDFs (Take II)
  • Now that we are including references via labels (all of which cannot be resolved by a single pass over a document), LaTeX must be run twice to correctly resolve all such references correctly. If this is not done, ?? will be typeset where all such references are requested.
  • As pdflatex is just a call to LaTex coupled to a call to dvipdf (as far as we are concerned), even though it appears on the first run that a PDF was created correctly, pdfdlatex must be run twice.
  • Certain LaTeX development environments may need to be run twice on a LaTeX file for the same reason.
• Example: A sample Latex document v5.0 (Tables) [example5.tex, example5.pdf, example5.script]

Tuesday, October 4 (Lecture #6) (FS)

• Typesetting Documents: Fun with LaTeX (Cont'd)
  • Typesetting Figures (Sections 3.5 and C.9.1, LL)
    • The overall figure-specification is included in the figure text environment; within this environment, one specifies a figure and caption and where they should be placed.
    • All notes about overall placement on the page, captions, and additional vertical space given above for typesetting tables also applies to figures.
    • There are a variety of ways of specifying a figure diagram and for including it in a LaTeX document; we will only talk here about the simplest and most commonly-used way.
      • Assume that the figure has been created as a file fig.EXT (where EXT is a standard image-file extension, e.g., pdf, jpg, eps) using a diagram-creation program such as xfig,
      • Insert this file into the LaTeX document using command \includegraphics[SPEC]{fig.EXT} where SPEC specifies the height or width of the diagram in the typeset document, e.g., width=10cm, height=3.5in.
        • Command \includegraphics supports a variety of diagram-file types, includes PDF and JPG.
        • Use of this command will require access to the graphicx LaTeX package; this is done by including command \usepackage[pdftex]{graphicx} in the document preamble.
        • Note that documents including figure diagrams in this manner can only be compiled using command pdflatex.
      • As there is no \centering command in the figure text environment, one centers diagrams by enclosing the \includegraphics commands in a center text environment.
    • Figures can also include tables in a figure by embedding tabular text environments appropriately.
  • Example: A sample Latex document v6.0 (Figures) [example6.tex, rs.pdf, elmo.jpg, example6.pdf, example6.script]
  • Writing Letters in LaTeX (Section 5.3, LL)
    • There is a standard letter format that is very nicely encoded using the letter document-type.
    • Letter documents have an additional letter text environment inside the usual document text environment with its own (possibly empty) preamble. The commands in this preamble are not required and may be omitted as necessary.
    • Letter-part commands and their effects:
      • \address{ADDRSen}: (Possibly multi-line) address ADDRSen of sender at upper right top of letter.
      • \begin{letter}{ADDRRec}: (Possibly multi-line) address ADDRRec of receiver at middle left of letter.
        • While \begin{letter} is necessary to start the letter text environment, the argument specifying ADDRRec is optional.
      • \opening{OPEN}: Opening text OPEN appearing to left just before letter body, e.g., "Dear Sirs;".
        • This command also triggers the appearance of today's date, i.e., the date on which the letter document was LaTeXed. at the middle right of the letter.
      • \closing{CLOSE}: Closing text OPEN appearing indented just after letter body, e.g., "Sincerely yours,".
      • \signature{SIG}: Sender signature SIG at bottom of letter, e.g., "Todd Wareham".
    • The first line in the example letter below tweaks LaTeX to ensure a sensible top margin in the face of local printer idiosyncrasies.
  • Example: A sample LaTeX letter document [exampleLetter.tex, exampleLetter.pdf, exampleLetter.script]
  • Writing Memos in LaTeX
    • There's nothing new here, aside from the handy command \hrule which produces a line the the width of the page; however, it is always nice to have an example handy of this bureaucratically critical artifact for modification as necessary.
    • Note explicit date via use of command \today (unlike letters, which get dates via the \opening command).
  • Example: A sample LaTeX memo document [exampleMemo.tex, exampleMemo.pdf, exampleMemo.script]
  • Writing Conference and Journal Papers in LaTeX
    • Each conference and journal will typically have its own specific LaTeX class, which defines the look of that conference and journal's papers. This will be defined by a given class file. If you are lucky, this will be accompanied by a user's guide, an example paper prepared under that class, and the PDF associated with that example.
    • Three major conference and journal paper-types in computer science are Springer, IEEE, and ACM. We will look at these in more detail next semester.
  • Example: A sample Springer conference paper [paperSpringer.tex, paperSpringer.pdf]
  • Example: A sample IEEE conference paper [paperIEEE.tex, paperIEEE.pdf]
  • Example: A sample ACM conference paper [paperACM.tex, paperACM.pdf]
  • Debugging / Prettifying LaTeX Documents
    • Like computer programs, LaTeX documents are prone to bugs that may prevent typesetting; moreover, given some of LaTeX's hardcoded default assumptions, typeset documents may not be what you want or may even incorporate outright errors. Hence, you should always allocate 10-15% of your LaTeX document development time for debugging and prettification.
    • Our goal here is not only to create documents that look as beautiful and professional as possible but to minimize where possible the time and effort required to do this.
    • Tip #1: Don't write your document and then LaTeX it -- rather, LaTeX your document frequently as it is being written.
      • Frequent LaTeXing makes it easier to localize your errors (and moreover ensures that these errors don't occur multiple times).
      • Just as in debugging program code, if a problem seems inexplicable, you may want to simplify your LaTeX code during debugging by commenting out sections of your document; this can be done using the comment symbol (%) at the beginning of each line you want commented out.
    • Tip #2: Do not have text overflowing into margins.
      • LaTex has known text-length problems (especially with inline math mode and font switches) that can result in margin overflows.
      • Wait until text stabilizes to fix these, and fix by splitting up math or font-switched text into pieces that do not cause margin overflows.
      • Badly or mis-hyphenated words can also cause margin overflows; this can be fixed by hyphenating the offending words manually.
      • Use command \linebreak (not \\) to manually force newlines if necessary.
      • If overflows involve tables or figures, redefine table and figure sizes; in the case of tables, this can be done by switching to a lower-size font inside the table.
    • Tip #3: Position tables and figures as near as possible to where they are first cited in the text.
      • LaTeX tries to put tables and figures as close as possible to where they are first cited in the text; however, if several tables or figures appear close together, LaTeX can make tables and figures wander unpredictably, sometimes even jamming them all at the end of a section or document.
      • Wait until text stabilizes to fix these, and fix by shifting table- and figure-code to before paragraphs in which they are first cited.
      • If there are many figures and tables, fix the positions of the earliest occurring first and progress forward through the document, as fixes in an earlier part of the document may screw up later parts.
    • Tip #4: Do not knowingly create orphans.
      • In typesetting, an orphan is a paragraph ending in a line with a single word, a page starting with a single line ending the previous page's last paragraph, or a page containing a single line.
      • Wait until text has stabilized to fix these, and fix by rewriting text to eliminate the orphans.
• Typesetting Literature Citations: Fun with bibitems and BibTeX (Sections 4.3, B, and C.11.3, LL)
  • There are two basic mechanisms in LaTeX for incorporating literature citations in LaTeX: bibitem and BibTeX.
  • bibitem allows manual typesetting of references in the bibliography.
    • Individual references are plaintext items beginning with \bibitem{TAG} commands inside a thebibliography text environment, where TAG is an alphanumeric string used when citing a bibitem-reference (see below).
    • The bibliography style is set by the \bibliographystyle{STY} command where STY is the requested style.
      • The default style is plain (numbered references in order given). There are other styles; for details, see the LaTeX documentation.
    • All listed bibitem-items are printed in the bibliography, even if they are not cited in the text.
  • Example: A sample Latex document v7.0 (bibitem) [example7.tex, example7.pdf, example7.script]
  • BibTeX allows automatic typesetting of references in the bibliography relative to a specified reference-information .bib file and a specified bibliography-style .bst file..
    • In the LaTeX file, the bibliography is created by a \bibliographystyle{STY} command followed by a \bibliography{BIB} command, where STY indicates the bibliography-style encoded in file STY.bst and BIB indicates the reference information encoded in file BIB.bib.
      • Standard bibliography styles like plain are stored with LaTeX files; other bibliography-style files like IEEEtran.bst must be located in the directory where LaTeXing is taking place.
    • A .bib file consists of a set of generically-encoded references.
      • Each reference has the form \ITEMTYPE{TAG, FIELD1, FIELD2, ..., FIELDn}, where each field has the form FIELDTYPE={FIELDVAL} or FIELDTYPE="FIELDVAL".
      • There are a number of standard item-types, e.g., article, book, inproceedings, incollection; additional item-types are typically defined in the .bst file.
      • There are a number of standard field-types, e.g., author, title, year, booktitle, journal, volume, number, pages, editor, publisher address; additional field-types are typically defined in the .bst file.
        • Each item-type has its own set of required (or at least requested) field-types.
        • Depending on the item-type and .bst file, words in titles may be (un)capitalized or multi-word author surnames may be turned into initials incorrectly. To prevent this, enclose words or letters that should always be capitalized and multi-word author surnames in curly braces.
    • Only BibTeX-items cited in the text body are printed in the bibliography. To add other (all) items in the .bib file, use command \nocite{TAG1, TAG2, ..., TAGm} (\nocite{*}).
  • Example: A sample Latex document v8.0 (BibTeX / plain style) [example8a.tex, example8a.bib, example8a.pdf, example8a.script]
  • Example: A sample Latex document v8.0 (BibTeX / IEEE style) [example8b.tex, example8b.bib, IEEEtran.bst, example8b.pdf, example8b.script]
• To cite a reference with associated tag TAG in the text body, use command \cite{TAG}, e.g., \cite{War99}, \cite{AD+12, Cor09, War99}. To associate extra text with a citation, put this text in the optional square-bracketed argument to \cite, e.g., \cite[Lemma 2.1.35]{War99}.
  • Many bibliography styles print reference-numbers for citations in the text body, e.g., [2,3,45]. More exotic types are available but require special .bst files, e.g., Wareham et al (2011) (APA.bst).
• Converting LaTeX Document Files to PDFs (Take III)
  • With bibitem, LaTeX must be run twice to correctly resolve citations in the text body to references in the bibliography. If this is not done, ?? will be typeset where all such citations are requested.
  • With bibtex, LaTeX must be run once to accumulate the wanted citations in the text body to references in the bibliography. BibTeX is then run once to resolve these citations, and LaTeX is run twice more to fully integrate both the citations in the text body and the references in the bibliography into the final document.
    • Certain LaTeX development environments may need to be run three times (with an interpolated BibTeX call) on a LaTeX file for the same reason.

Tuesday, October 11

• No lecture; midterm break

Thursday, October 13

• No lecture; class cancelled

Tuesday, October 18

• Student Presentations I
  • Speakers for today:
    • Ahmed, M. Israk
    • Chen, Zhuang
    • Das, Shemonto
    • de Souza Reinaldo, Jessica T.

Thursday, October 20

• Student Presentations I
  • Speakers for today:
    • Galaiya, Viral
    • Ghorbani, Fatemeh
    • Hajishafiezahramini, Parham
    • Islam, Sadman Saumik

Thursday, October 20

• In-Class Exam #1 Notes
  I've finished making up your first in-class exam. The exam will be closed-book and no ``fact sheets'' will be allowed. It will be 60 minutes long and has a total of 60 marks. There will be two questions worth 30 marks apiece -- the first asks you to show what given pieces of LaTeX code produce and the second asks you to give LaTeX code for producing given typeset texts. Each question has three parts. Topics covered in the questions include:
  • Math typesetting (both in text and offset separately).
  • (Nested) List environments

  You will find the texts and LaTeX codes in the Diary examples and Assignment #1 of use.

  I hope the above helps, and I wish you all the best of luck with this exam.

Tuesday, October 25

• Student Presentations I
  • Speakers for today:
    • Maheri, Mahmoud
    • Mirmojarabian, Mohammadali
    • Mirmojarabian, Mohammadmahdi
    • Mohammadreza, Elaheh

Thursday, October 27

• Student Presentations I
  • Speakers for today:
    • Niazmand, Vahid Reza
    • Noel, Jordan T.
    • Piercey, Caitlin
    • Pourbaghi, Mahdi

Tuesday, November 1

• Student Presentations I
  • Speakers for today:
    • Robles Aguilar, Alfonso
    • Salehin, Mushfiqus
    • Seidl, Marius
    • Wells, Nicholas W.

Thursday, November 3

• Class Exam #1

Sunday, November 6

• In-Class Exam #2 Notes
  I've finished making up your second in-class exam. The exam will be closed-book and no ``fact sheets'' will be allowed. It will be 60 minutes long and has a total of 60 marks. There will be three questions:
  • Bibliography typesetting with bibitem and BixTeX (2 parts) (32 marks)
  • Table typesetting: Given LaTeX code, draw table (1 part) (12 marks)
  • Table typesetting: Given table, give LaTeX code (1 part) (16 marks)

  You will find the texts and LaTeX codes in the Diary examples and Assignment #2 of use.

  I hope the above helps, and I wish you all the best of luck with this exam.

Tuesday, November 8 (Lecture #7) (FS)

• Effective Literature Search: Dealing with Google Scholar et al
  • The central task in literature search is finding the "core" set of papers on a particular topic. This is useful in a number of research-related activities, e.g., finding and validating research topics, writing theses and surveys.
  • The core papers on a topic form one or more sets of papers, each of which has the following relationships:
    • They share a common terminology (keywords).
    • They are written by a particular set of researchers (authors).
    • Modulo the different times at which they are written, they refer to each other in their bibliographies (citation).

    To find a core set of papers, we exploit each and often all of these relationships.

  • Example: Relationships between the core set of papers on a topic:
    
    
    

  • The first step in literature search is locating an initial relevant paper.
    • This is a two-step process: Finding candidate relevant papers and evaluating the relevance of found candidate papers.
    • There are several ways to find candidate relevant papers:
      • Reading the literature
        • If you read widely in Computer Science, you may have run across relevant papers or know where relevant papers are published.
        • Though laudable, this takes a lot of time.
      • Asking an expert
        • An unbiased expert on a topic is often the best source for references to relevant papers.
        • The main problem here is finding such an unbiased expert; asking around your own colleagues and department is a good start.
        • Experts need not be local; indeed, it is heartening how often well-known experts will respond to a sincere and well-prepared e-mail asking for help on their topic of expertise.
        • There are also some wonderful on-line forums, e.g., CS Stack Exchange; by evaluating obtained answers carefully, one may access a "composite expert".
        • Expert advice must still be handled carefully, as you have your own biases, e.g., Warnow / Meacham.
      • Doing keyword search
        • Keyword search is often the best available source for references to relevant papers.
        • Though general search engines are useful, where possible, use academic search engines such as Google Scholar.
        • Use the initial keywords you use yourself to describe your topic, e.g., "computationally difficult"; however, if nothing useful-looking turns up, use synonyms, e.g., "intractable", "NP-hard", and more general rather than more specific synonyms at that, e.g., "(computational) complexity".
        • Consider adding the keywords "survey", "review", and "overview" to your search terms -- surveys are not only very useful in giving you a handle on a new topic but are also often invaluable for later stages of literature search (see below).
        • Example: Keyword search for intractability results in robot motion planning. [Google Scholar]
        • Example: Keyword search for intractability results in component-based software design. [Google Scholar]
        • Example: Keyword search for intractability results in software modularization. [Google Scholar]
    • The best way to evaluate relevance of a found paper is to fully read that paper. However, if done carefully, a skim-read of the paper (focusing on the abstract, introduction, discussions, and conclusions) will often suffice.
      • When using Google Scholar, a paper's abstract and often the paper itself can be obtained by clicking on the name of the paper.
      • The full text of some papers may only be available for payment.
      • The best way to get around this is do searches through a university computer account, as university libraries have often paid for access already.
      • Failing that, try the All X versions link associated with the paper by Google Scholar, or look for a (possibly pre-publication) version of the paper on the personal websites of the paper's authors.

Tuesday, November 15 (Lecture #8) (FS)

• Effective Literature Search: Dealing with Google Scholar et al (Cont'd)
  • Once one has an initial relevant paper X, the next step is to exploit paper-relationships to find other relevant papers in the core.
    • There are several ways to do this:
      • Doing refined keyword search (RKS)
        • Very useful if core consists of multiple author- and/or citation-disjoint paper-sets.
        • Most useful if all papers in the core share the same terminology.
        • Can be done nicely using the keyword box in Google Scholar.
          • Can customize years searched using the links on the left-hand size of the search page.
          • Beware leaving specific date-ranges in place unintentionally, as this may compromise later searches.
        • Though specific keyword searches are more appropriate at this point, you may also find general keyword searches useful.
        • Example: RKS for intractability results in component-based software design (""computational complexity" component selection"). [Google Scholar]
        • Example: RKS for intractability results in robot motion planning (""computational complexity" robot motion planning") [Google Scholar]
        • May be less useful if there are multiple disjoint sets of appropriate terminology.
      • Looking for papers that cite X (Forward Citation Search (FCS))
        • Very useful if core consists of multiple author- and/or keyword-disjoint paper-sets.
        • Can be done nicely using the Cited by X link associated with a paper by Google Scholar.
          • Do such searching methodically and mindfully; it is all too tempting do recursive forward searches and inadvertently lose track of useful found references.
        • Example: FCS relative to Petty, Weisel, and Mielke (2003). [Google Scholar]
        • Example: FCS relative to Cesati and Wareham (1995) [Google Scholar]
        • Most useful if X is older (but not too old (see below)).
        • May be less useful if X is recent, in that there may be less time for people to be aware of X.
        • May be less useful if X is older and has been superceeded in importance by more recent papers.
      • Looking for papers that X cites (Backward Citation Search (BCS))
        • Very useful if core consists of multiple author- and/or keyword-disjoint paper-sets.
        • Is typically done manually relative to a paper's bibliography; however, such bibliographies are occasionally available online with the initial reference, e.g., certain papers published by ACM and Elsevier, references through Citeseer.
        • Example: BCS relative to Petty, Weisel, and Mielke (2003). [Google Scholar]
        • Example: BCS relative to Cesati and Wareham (1995). [PDF] [Google Scholar]
        • Most useful when X is recent and a survey.
        • May be less useful if X is older and has had the references in its bibliography superceeded in importance by more recent papers.
      • Looking for other papers by the same author(s) (Author Name Search (ANS))
        • Very useful if core consists of multiple keyword- and/or citation-disjoint paper-sets.
        • Can be done nicely using the keyword box in Google Scholar.
          • May be problematic if the author name is common, e.g., "Smith", "Chang".
          • Failing that, consider using area-specific author-oriented online services, e.g., DBLP (Computer Science), or author-maintained homepages.
          • As each method above often leaves out some papers by an author, may need to use all three.
        • Example: My papers as listed by Google Scholar, DBLP, and my homepage. [Google Scholar, DBLP, My Home Page]
        • Most useful if author works exclusively on the topic of interest.
        • May be less useful if author is prolific and works on multiple topics.
        • Beware of shifts in author-name due to marriage, e.g., "Keeling" => "Hartley-Keeling", "Hemachandra" => "Hemaspaandra", or indecision, e.g., "Harold Todd Wareham" => "H. Todd Wareham" => "Todd Wareham".
  • Newly-found papers must have their relevance assessed; once their relevance is established, these papers are then used to search for other relevant papers.
  • Search relative to a particular initial paper should probably stop when the newly-found papers are those that you have already found.
  • A secondary but nonetheless important task in literature search is finding the full reference details for a paper.
    • This task arises because (1) conference page limits and certain journal bibliography styles force authors to shorten references and (2) people are lazy (including some authors regarding their own papers (!)).
    • Though bibliographic standards have declined over the last several decades, it is still useful in your own work to have full bibliographic references because such references enhance the look of your work as well as your professional reputation.
    • The methods given above for finding papers by keyword and author name often work well here.
      • If the paper has been located using Google Scholar, the cite tab associated with the paper gives its bibitem and BibTeX information.
      • As some of these entries have been compiled by uninformed manual or automatic techniques, beware incomplete and/or misleading entries (see the Cygan et al example below).
    • Failing that, one can fall back on going back (via Google or manual library search) to the paper itself in the Tables-of-Contents of the conference, journal, or book in which the paper appeared.
    • Example: Finding the full reference for Mueller et al (2009) "Similarity as Tractable Transformation." [Google Scholar]
    • Example: Finding the full reference for Wareham, Evans, and van Rooij (2011) [Google Scholar]
    • Example: Finding the full reference for Cygan et al (2015) "Parameterized Algorithms". [Google Scholar]
  • More tools are becoming available on-line all the time to aid in literature search (some of undoubtably well-meaning but questionable legal status (*)), e.g.,
    • Science Citation Index (SCI) (Wikipedia entry)
    • Web of Science (Wikipedia entry)
    • Scholarpedia
    • Academia
    • List of academic databases and search engines (Wikipedia entry
    • Sci-hub (*)

    Many such tools are based on technical and business models taken from other (possibly less academicly relevant) applications, e.g., generic search engines (Google Scholar), social media (Academia.edu), and hence individually incorporate only certain aspects of literature search. There are also a variety of business models, e.g., freely available, subscription.

  • There may be opportunities to create a literature-comprehensive freely-available tool that incorporates all forms of used literature search described above, e.g., a fusion of the keyword and forward citation search capabilities of Google Scholar with the backward citation search capabilities of Citeseer and the author name search capabilities of DBLP (with reference bookmarking / collection capabilities and the self-addition / maintenance capabilities of Wikipedia thrown in). Given the burgeoning size of the world's research literature and the utility of this research in academia, government, and industry (and possibly to the general public as well), such a tool could be the basis of a viable business, given the right business model.
• This brings us to the end of CS 690A. We've talked about various techniques underlying the research process -- what about research itself?
• Starting Research: Some Initial Thoughts
  • Selecting and validating topics is a crucial part of both thesis and general research.
  • Recall the three necessary properties of a good research topic:
    
    • Finding a topic that has not been done before is a central part of doing original research, and is crucial to BSch, MSc, and PhD theses as well as academic research in general.
      • The central role of originality is a large part of why plagiarism is so despised in scientific research.
    • Finding a topic that is important is not so crucial at the BSch or MSc levels (where one is arguably learning techniques and how to apply them as well as the manner in which research is conducted), but it is crucial at the PhD level as well as in academic research in general. The latter is so because it is important research which allows publication in recognized venues and the formulation of quality funding proposals which are highly likely to be funded, both of which are important in building an academic career of your choosing (and not merely one that is available).
    • Finding a topic that you can work on productively is arguably the most critical aspect, because without this, there are no research results and hence none of the benefits described above that accrue from them.
  • Assessing the originality and importance of a topic is typically done by performing a thorough literature search and consulting with experts in the topic area; assessing whether a topic is one that you can work on productively requires (often brutal) honesty about one's own abilities.
  • Failure to do any of these assessments fully can result in much wasted time and effort.
  • Example: The 2001 SAC Incident (Failure wrt Originality)
  • Example: The 2007 ICDT Incident (Failure wrt Importance)
  • Example: Things I Didn't Do for My MSc and PhD I: the combinatorics of reticulate evolutionary trees and the parameterized complexity of evolutionary tree inference (Failure wrt Doability)
  • When we return in CS 690B, we'll talk about this a lot more. For now, think about what topic you'd like to do for your CS 690B course project, i.e., a stripped-down research proposal.

Thursday, December 1

• Class Exam #2

References

• Lamport, L. (1994) LaTeX: A Document Preparation System: User's Guide and Reference Manual (Second Edition). Addison-Wesley. (Abbreviated above as LL)

Created: June 22, 2022
Last Modified: November 14, 2022