COMP 200 Elements of Computer Science &
COMP 130 Elements of Algorithms and Computation
Spring 2012

Study Guide for Exam 2

This is just a list of topics to help guide your studying. The list is not in order of importance, nor should it be considered a complete list of all topics you should know.

Be sure to do ALL the class exercises up to this point!   This guide is NOT a subsitute for studying all the class notes, exercises and assigments!

COMP 200 & COMP 130

Opening and reading files
“Naive” string matching algorithm
Regular expressions
Repetition with * and +
re library functions
Using them to split strings
More data structures
Tuples & their operations
Dictionaries & their operations, including looping over their keys, their values, or their key/value pairs
Nested data structures, such as dictionaries of dictionaries
The differences among strings, lists, dictionaries, tuples
Markov chains
The idea of mapping previous data to the next data, probabilistically
Example nested data structure: a dictionary mapping tuples of strings to dictionaries mapping strings to probabilities
Problem decomposition
Managing complexity of algorithms
Managing complexity of using nested data structures
Choosing data randomly
random library functions
Writing multiple functions that coordinate via global variables
E.g., the car simulation problem

COMP 130

defaultdict
PCA & clustering
Parallel computation via MapReduce
Currying