Study Guide for Exam 3

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!

The set of topics for Exam 3 is cumulative, i.e. you are required to know all the topics from the earlier exams and assignments.

COMP 200 & COMP 130

• Data types
  • Graph representations
    • Defining our own
    • networkx
  • Priority queue representations
    • Items unordered vs. ordered
  • Encapsulated/abstract data types
    • Using them, as in networkx and priority queues
• Graph concepts
  • Nodes/vertices & edges
  • Edges labeled with weights/distances
  • Directed & undirected
  • In-/Out-degree
  • Complete
  • Connected
  • Path & path length
• Graph searching algorithms
  • DFS, BFS, Dijkstra
• Recursion
  • Linear recursion's similarity/equivalence to looping
• Probability
  • Conditional probability
  • Bayes' Theorem
• Big-O notation

COMP 130

• Python sets
• Passing, returning and using functions as variables (functions as first-class entities)
• Classes in Python
  • Inheritance and polymorphism
  • Defining a class
  • Constructor
  • Methods
  • Attributes
  • Instantiating and using a class
• Restricted access containers
  • Stacks
  • Queues
  • Priority queues
  •  Use in DFS and BFS algorithms
• Heaps
  • Definition
  • Use in priority queues
• Recursion
  • Delegation
  • Encapsulation
• Bayesian Inference
• Google PageRank