CS209 Topics List for exam 1

I make no claims that this is comprehensive but I tried to make it so.  This can be used as a guide for you to study, but just because something is not on this list, doesn't mean it will not be on the exam.  This is a list of the major things covered in the course that can appear on exam 1.

The exam may contain code that you are to read and interpret (e.g. what will be the output of this program, given certain input), code that you are to write (e.g. add a method to do X) and some conceptual questions regarding the data structures and algorithm analysis.

If I ask you to use the definition of big O, big Omega, or big Theta I will provide the definition.

Computers, calculators, phones, any electronics, are NOT allowed to be used on the exam.

You may use 1 8.5x11" sheet of paper (both sides) that you prepared yourself for reference
during the exam.

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

Algorithm Efficiency
  - know the general idea
  - know that dominant term overrides the rest
  - know that time complexity is more important (for large problem
    sizes) than processing speed (of a particular computer) and why
  - know the relative order of the major funtions, n, n*n, n*n*n, logn,
    1, etc.
  - how to use Big O, Big Theta, Big Omega definitions and what they mean
  - you may be asked to give big O or big Theta running times of 
    algorithms that work on the algorithms we've covered, or 
    based on code given on the exam

Proof by induction

Know the Arithmetic sum which is: Sum of i, from i=1 to n = n*(n+1)/2

Linked Lists
  - definition
  - code for linked lists
  - benefits of adding a tail reference
  - how to insert, delete, search etc. a linked list