CP164 Study Guide - Final Guide: Priority Queue, Object-Oriented Programming, Information Hiding
Notes - ADTs
Definitions
Modularity
A module packages a collection of entities and controls how those entities can be
used. A program is modular if it is divided into well-designed modules. In CP104 we
concentrated on dividing programs into functions that performed specific tasks. We
also tried to make these functions as generic as possible. In CP164 we will continue
this, but make data modular as well through the use of abstract data types.
Information Hiding
Refers to hiding the internal mechanisms of a module from external programmers
so that private information cannot be accessed or modified.
Interface
The part of a module that is visible to an external programmer.
Encapsulation
The grouping of a data entity and its associated methods together in a module.
Abstract Data Type (ADT)
A data entity plus a set of methods on that entity.
Example: the Priority Queue ADT refers to a data entity called a priority queue together
with its associated methods.
ADTs are similar to classes in object-oriented programming languages. Both ideas feature
the encapsulation of data and methods, but classes can be implemented only on object-
oriented programming languages. ADTs can be implemented in most procedural
programming languages.
We will implement ADTs using Python classes.
Example ADT: Priority Queue
A collection of prioritized items.
An emergency waiting room is a real-world example of a priority queue. Patients go
through triage (the process of determining the priority of patients' treatments based on the
severity of their condition) before being seen by a doctor. Those with the worst conditions
get highest priority. If two or more patients have equally bad conditions the patients are
seen in the order in which they arrived at the emergency waiting room.
Items are removed from a priority queue in order of their priority, highest priority first.
New items may be added to a priority queue at any time. Items of equal priority are
removed in order of their addition to the priority queue.
Document Summary
A module packages a collection of entities and controls how those entities can be used. A program is modular if it is divided into well-designed modules. In cp104 we concentrated on dividing programs into functions that performed specific tasks. We also tried to make these functions as generic as possible. In cp164 we will continue this, but make data modular as well through the use of abstract data types. Refers to hiding the internal mechanisms of a module from external programmers so that private information cannot be accessed or modified. The part of a module that is visible to an external programmer. The grouping of a data entity and its associated methods together in a module. A data entity plus a set of methods on that entity. Example: the priority queue adt refers to a data entity called a priority queue together with its associated methods. Adts are similar to classes in object-oriented programming languages.
