Held: Monday, 14 September 2015

Back to Outline 07 - Pause for Breath. On to Outline 09 - Hash Tables.

Summary

We begin to consider the ADTs and data strutures that underlie many of the algorithms we write.

Related Pages

Overview

• Abstract data types.
• Data structures.
• The Dictionary ADT.

Administrivia

• New partners for in-class work.
• It is possible that the next two weeks of class will vary a bit from the indicated plan.
• Question: How comfortable are you with tree traversal strategies?
  • Depth-first vs. breadth-first
  • For depth-first: Preorder vs. Inorder vs. Postorder

Upcoming Work

• For Wednesday:
  • Read Skiena 3.1-3.3
  • Part 1: Experimental Analysis
    • Look up the randomized nth-largest divide-and-conquer algorithm. (We may talk about it in class today.)
    • Implement it in C.
    • Write unit tests using assert.
    • Write a program that does lots of repeated tests to evaluate it's running time.
  • Part 2: Proof
    • Find bounds for each of the following using the master theorem.
      • a. T(n) <= 3T(n/3) + O(n^2).
      • b. T(n) <= 3T(n/3) + O(n).
      • c. T(n) <= 3T(n/3) + O(1).
      • d. T(n) <= 3T(n/5) + O(n^2).
      • e. T(n) <= 3T(n/5) + O(n).
      • f. T(n) <= 3T(n/5) + O(1).
      • g. T(n) <= 9T(n/3) + O(n^2).
      • h. T(n) <= 9T(n/3) + O(n).
      • i. T(n) <= 9T(n/3) + O(1).
      • j. T(n) <= T(2n/3) + O(n^2).
      • k. T(n) <= T(2n/3) + O(n).
      • l. T(n) <= T(2n/3) + O(1).
    • Prove the bounds of a-c using induction.

Extra Credit

Academic

• CS Table, Tuesday, Hacking Cars
• CS Extras, Wednesday, Jonathan Wellons '04 from Google
• Convo Thursday at 11 am in JRC 101: Mike Latham

Peer

Abstract Data Types

• What is an abstract data type?
• Why do we use them?
• How do you design them?

Data Structures

• What is a data structure?
• How do we use them?
• How do you design/build them?
• What is the relationship between ADTs and data structures?

Example: Dictionaries

• If you haven't seen dictionaries before, think of them as a generalization of hash tables.
• What do you see as the primary philosophy of dictionaries?
• What do you see as some natural uses of dictionaries?
• What do you see as the necessary methods a dictionary ADT should provide?
• What implementations of dictionaries do you know?