ICS2605: Abstract Data Types & Recursion Key Concepts

Abstract Data Type (ADT)

A data type defined by its data (components, properties, relationships) and operations, independent of implementation.

Data

Information used to represent knowledge about the world.

Operations

Actions that manipulate data to reason about or solve problems.

Stage: Specification

Defines what data and operations are needed, from the user's perspective.

Stage: Implementation

Describes how data and operations are realized in code.

Stage: Application

Use of ADTs to solve real problems.

Characteristics of ADTs

Encapsulation of data + operations, abstraction from implementation, well-defined interfaces.

Primitive Data Structures

Basic data types provided by a programming language (e.g., int, char, float).

Non-Primitive Data Structures

More complex structures built from primitives (e.g., arrays, lists, stacks).

Linear Data Structures

Data organized sequentially (e.g., arrays, linked lists, stacks, queues).

Non-Linear Data Structures

Data organized hierarchically or in networks (e.g., trees, graphs).

Static Data Structures

Fixed memory size, determined at compile time (e.g., arrays).

Dynamic Data Structures

Memory allocated at runtime, can grow or shrink (e.g., linked lists).

Stack

A linear data structure following LIFO (last-in, first-out) order.

Queue

A linear data structure following FIFO (first-in, first-out) order.

Deque

Double-ended queue where insertion/deletion allowed at both ends.

Priority Queue

A queue where each element has a priority, and removal is based on priority.

Linked List

A dynamic linear structure where elements (nodes) contain data and pointers to next nodes.

Tree

A non-linear hierarchical structure with nodes connected by edges; has a single root.

Binary Tree

A tree where each node has at most two children (left and right).

Graph

A non-linear structure of vertices and edges that may be directed or undirected.

ADT Operations: Creation

Build a new instance of a data structure.

ADT Operations: Insertion

Add an element to the structure.

ADT Operations: Deletion

Remove an element.

ADT Operations: Traversal

Access each element systematically.

ADT Operations: Searching

Locate an element.

ADT Operations: Sorting

Arrange elements in order.

Aspects of Good Algorithm

Has input, Has output, Definite, Effective, Finite, Correct, General, Efficient

Iteration

An execution of a loop’s body

Recursion

Solves problems in terms of smaller instances or parts.

Elements of Recursion

Basis: Direct Solution to smallest parts.; 0 is a natural number.

Recursive Step: Solves a big problem in terms of solutions to smaller parts.; n is a natural number if n-1 is a natural number.