CMSC 132: Object-Oriented Programming II

Practice flashcards based on lecture notes for CMSC 132: Object-Oriented Programming II.

Set ADT

An abstract data type representing a collection of unique elements without duplicates or specific order.

Map ADT

An abstract data type consisting of key-value pairs, with unique keys for efficient value retrieval.

Insertion (add)

A Set operation that adds an element if it is not already present.

Deletion (remove)

A Set operation that removes an element if it exists.

Search (contains)

A Set operation that checks whether a specific element is present.

Union

A Set operation that returns a new set containing all elements from both sets.

Intersection

A Set operation that returns a new set with elements common to both sets.

Difference

A Set operation that returns a new set with elements in the first set that are not in the second.

Naive Implementations of Sets

Sets implemented using arrays result in O(n) operations for insertion, search, and removal.

Hash Table

A data structure that uses a hash function to efficiently map keys to values.

Collision

An event that occurs when two keys hash to the same index in a hash table.

Load Factor (λ)

The ratio of the number of entries in a hash table to its size; impacts performance.

Rehashing

The process of resizing and reorganizing a hash table when its load factor becomes too high.

TreeMap

A Map implementation that stores keys in sorted order using a Red-Black Tree.

Binary Search Tree (BST)

A binary tree where each node's left children are less than the node, and right children are greater.

Quick Sort

A divide-and-conquer sorting algorithm with an average time complexity of O(n log n).

Merge Sort

A stable divide-and-conquer sorting algorithm that runs in O(n log n) time.

Binary Tree Traversal

The method of visiting all the nodes in a binary tree in a systematic manner: pre-order, in-order, post-order.

Leaf Node

A node in a tree that has no children.

Root Node

The topmost node in a tree with no parent.

Height of a Tree

The number of edges in the longest path from the root to a leaf node.

Depth of a Node

The number of edges from the root to the node.

AVL Tree

A self-balancing binary search tree that maintains balance to ensure O(log n) operations.