CS 361: Data Structures and Algorithms

Prof. Cristopher Moore, moore@cs.unm.edu
Fall 2006

This course will cover the basic ideas behind many of the most 
efficient algorithms, data structures which allow us to maintain data and
access it quickly, basic ideas from probability, and algorithms for
graphs and other problems.  We will learn how to design an algorithm,
prove that it works, and analyze its efficiency.  Along the way,
we'll find that computer science is much more than programming; it has
great mathematical beauty and depth.

We will cover:

  BASIC ALGORITHMIC IDEAS
  Recursion: the Towers of Hanoi and inductive proofs
  Invariants: bubblesort and proving that an algorithm works 
  Divide and conquer: mergesort
  Using randomness: quicksort
  
  DATA STRUCTURES
  Priority queues and heaps
  Search trees, binary and otherwise
  Balanced trees: AVL trees and 2-3 trees
  [optional: Skip lists]
  
  HASH TABLES AND PROBABILITY
  The Birthday Problem and hash collisions
  Coupon collecting
  Chaining and balls-in-bins problems
  
  GRAPH ALGORITHMS
  Union-Find
  Programming project: percolation
  
Plus some possible advanced topics:
  
  SEARCH ALGORITHMS FOR HARD PROBLEMS
  Davis-Putnam and backtracking search
  Random walks and Walk-SAT
  
  CRYPTOGRAPHY
  Modular arithmetic review
  Diffie-Helman secret sharing and Skype
  RSA encryption
  
  GOOGLE
  Searching the Web with Eigenvectors

Grading 

Grading will consist of 1/4 exams (the final and one midterm), 1/4 
programming projects, and 1/2 homeworks.  A clear trend of
improvement will also be taken into account in your final grade, for
instance if you have trouble with the midterm but do better on the
final.

Policies

I encourage you to form study groups and discuss the homework and
projects; sharing information on what method you tried, whether or not
it worked, and so on is fine.  However, just as you have to write your
own programs in a programming class, at the end of the day you have to
do the calculations and write the proofs yourself, and write them up
with an acknowledgment of who you discussed them with.  Under no
circumstances should you simply copy another student's work, or allow
them to copy yours.

Except in extraordinary circumstances (e.g. a medical excuse or family
problem) last homeworks and projects will be counted off 10% per day late.
If you know that something like that is going to happen in advance,
please contact me and we can make arrangements.  No credit will be given
after the solutions are posted.

Please feel free to contact me at any time at moore@cs.unm.edu with questions!

- Cris Moore