Data Structures and Algorithms

An abstract data type (ADT) is defined by its behavior (operations) rather than its implementation. This separation of concerns is the core principle of ADTs.

A data structure is a logical model or a way of organizing data in a computer so that it can be used efficiently. It is not an algorithm itself, but rather the structure that algorithms operate upon.

In a linear data structure, the elements form a sequential arrangement where each element is connected to its previous and next element. Examples include arrays, linked lists, stacks, and queues.

A tree is a non-linear data structure that represents hierarchical relationships between elements, such as a root node with child nodes.

Searching is the process of finding the location of a specific element within a data structure.

An array is a data structure consisting of a collection of elements, each identified by at least one array index or key, all of the same data type.

Merging is the process of combining two or more sorted sequences into a single sorted sequence.

In the context of linked lists and many other data structures, the individual unit containing data is called a node.

In a singly (linear) linked list, each node contains two parts: the data (information) and the pointer (address) to the next node.

The second part of a node in a singly linked list is the pointer field, which stores the address of the next node in the sequence.

One-dimensional arrays require only one index to access an element (like arr[5]). Two-dimensional arrays need two indices (arr[3][2]), and multidimensional arrays need even more. The term 'One-dimenstrional' has a typo but is clearly intended.

Depth-First Search (DFS) is a classic algorithm that traverses tree or graph structures by going as deep as possible before backtracking, which is naturally implemented using recursion.

Breadth-First Search (BFS) must store all nodes at the current depth level in the queue, which leads to exponential memory usage as the search tree grows. Depth-First Search (DFS) only needs to store the current path, making it more memory-efficient.

A* is a classic informed search algorithm that uses a heuristic function to guide a Best-First Search, balancing the cost from the start and the estimated cost to the goal.

The AO* algorithm is designed to search AND-OR graphs, which are used for problem reduction, where a complex problem is broken down into smaller, simpler subproblems.