COMPSCI 61B Lecture Notes - Lecture 20: Ackermann Function, Priority Queue, Earth-616
1 Jun 2017
School
Department
Course
Professor
Document Summary
Project has seemed like a more appropriate level of di culty than previous semesters. Project 2: a chance to see how a design evolves. Next couple of weeks: deriving classic solutions to interesting problems, with an emphasis on how set, map, and priority queue adts are implemented. Today: a chance to see how an implementation of an adt can evolve and how di underlying data structures a ect asymptotic runtime (using formal notation) Goal: given a series of pairwise connectedness declarations, determine if two items are connected transitively. Solvable using a simple adt with cool implementation details. Given a series of pairwise integers connectedness declarations, determine if two integers (or items) are connected. Number of method calls m can be huge. Calls to methods may be interspersed (e. g. can"t assume that we stop getting connect calls after a point) Connecting two things: record every single connecting line in some data structure.
