Week 11

Trees – continued (chapt. 10, very high level)

• Heaps
  • Binary tree with 2 rules
    • Data in a node is >= Data in its children
    • It is a complete binary tree
  • Priority queue example
    • Implement as an array
    • Insertion
      • Insert at the bottom in first open space
      • Swap with parent until in right place
      • Could also put at top and swap downward
    • Deletion
      • Delete at the top because it’s the highest priority
      • Move ‘last’ item in complete binary tree to top
      • Swap down with children until in right place
• B-Trees
  • Complete rules in text:
  • More complicated
  • Objective is finding data fast
  • Used in database construction
    • Worst case times for add, remove and search are O(d) where d= depth of tree

General Objects

• Graphs
• Definitions
  • nodes/verticies, edges, paths, loops
  • directed, undirected
  • network (costs associated with each edge)
  • inheritance, inheritance hierarchy,
• Implementation
  • Adjacency lists
  • Adjacency matrix
• Traversal
  • depth-first
  • breath-first
  • potential problem - looping
• Circular lists
  • End points to the front
  • Need only one pointer, rear
• Lists of queues, queues of stacks, etc.
• ·Give switching system example
• System
• Bays
• Shelves
• Packs with states
• Hamburger joint
  • Multiple registers
  • Multiple displays
• Hospital
  • Patients
  • Rooms
  • Wards
  • Doctors
  • Administrators
• Have them pick an application and discuss

File I/O

·        Reading and writing from a file

·        Use

FileReader fileIn           = new FileReader(<filename>);

BufferedReader input  = new BufferedReader(fileIn);

Then:

// to read the next integer

int n = input.readInt();   

// to read a string

String line = input.readLine();

// to throw away the rest of an input line and go to the next line

input.readLine();