Definitions

Question 1

Record

Answer 1

A record is the data structure that stores subitems, often called fields, with a name associated with each subitem.

Question 2

Array

Answer 2

An array is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.

Inserting an item at a specific location in an array requires making room for the item by shifting higher-indexed items.

Question 3

Linked list

Answer 3

A linked list is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.

A linked list stores an ordered list of items. The links in each node define the order in which items are stored.

To insert new item in a linked list, a list node for the new item is first created. Item B’s next pointer is assigned to point to item C. Item A’s next pointer is updated to point to item B. No shifting of other items is required, which is an advantage of using linked lists.

Question 4

Binary tree

Answer 4

A binary tree is a data structure in which each node stores data and has up to two children, known as a left child and a right child.

A binary tree node can have no children, a single left or right child, or both a left and right child.

Question 5

Hash table

Answer 5

A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.

Question 6

Heap

Answer 6

In data structures, a “heap” is a tree-based data structure where the nodes are arranged in a specific order, either with the largest value at the root (max-heap) or the smallest value at the root (min-heap), ensuring that the parent node always has a value greater than or equal to its children, making it particularly useful for implementing priority queues where you need to quickly access the highest or lowest priority element; it’s often implemented as a complete binary tree for efficient operations.

Key points about heaps:
- Heap property:
The core principle of a heap is the “heap property” which dictates the ordering of nodes within the tree, either with the parent node always having a larger value than its children (max-heap) or a smaller value (min-heap).
- Binary heap:
The most common implementation of a heap is a “binary heap” where each node has at most two children.
- Applications:
Heaps are used in algorithms like heapsort (for sorting data), Dijkstra’s algorithm (for finding shortest paths), and priority queues where elements need to be accessed based on their priority

A max-heap is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s children’s keys.

A min-heap is a tree that maintains the simple property that a node’s key is less than or equal to the node’s children’s keys.

Question 7

Graph

Answer 7

A graph is a data structure for representing connections among items, and consists of vertices connected by edges. A vertex represents an item in a graph. An edge represents a connection between two vertices in a graph.

Question 8

Algorithm

Answer 8

An algorithm is a set of commands that must be followed for a computer to perform calculations or other problem-solving operations.

According to its formal definition, an algorithm is a finite set of instructions carried out in a specific order to perform a particular task. It is not the entire program or code; it is simple logic to a problem represented as an informal description in the form of a flowchart or pseudocode.

• Problem: A problem can be defined as a real-world problem or real-world instance problem for which you need to develop a program or set of instructions. An algorithm is a set of instructions.
• Algorithm: An algorithm is defined as a step-by-step process that will be designed for a problem.
• Input: After designing an algorithm, the algorithm is given the necessary and desired inputs.
• Processing unit: The input will be passed to the processing unit, producing the desired output.
• Output: The outcome or result of the program is referred to as the output.

Question 9

Logical vs Physical data flow diagram

Answer 9

Logical DFDs (data flow diagrams) focus on what happens in a particular information flow: what information is being transmitted, what entities are receiving that info, what general processes occur, etc. The processes described in a logical DFD (data flow diagram) are business activities—a logical data flow diagram doesn’t delve into the technical aspects of a process or system, such as how the process is constructed and implemented. So you don’t need to include details like configuration or data storage technology. Non-technical employees should be able to understand these diagrams, making logical DFDs (data flow diagrams) an excellent tool for communicating with project stakeholders.

Physical data flow diagrams focus on how things happen in an information flow. These diagrams specify the software, hardware, files, and people involved in an information flow. A detailed physical data flow diagram can facilitate the development of the code needed to implement a data system.

Question 10

NP-complete

Answer 10

NP-complete problems are a set of problems for which no known efficient algorithm exists. NP-complete problems have the following characteristics:

No efficient algorithm has been found to solve an NP-complete problem.
No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.
If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.
By knowing a problem is NP-complete, instead of trying to find an efficient algorithm to solve the problem, a programmer can focus on finding an algorithm to efficiently find a good, but non-optimal, solution

Question 11

Algorithm efficiency

Answer 11

Algorithm efficiency is most commonly measured by the algorithm runtime, and an efficient algorithm is one whose runtime increases no more than polynomially with respect to the input size.

In contrast, an algorithm with an exponential runtime is not efficient.

Question 12

Abstract data types (ADTs)

Answer 12

An abstract data type (ADT) is a data type described by predefined user operations, such as “insert data at rear,” without indicating how each operation is implemented. An ADT can be implemented using different underlying data structures. However, a programmer need not have knowledge of the underlying implementation to use an ADT.

Question 13

Abstract Data Types examples

Answer 13

List, Dynamic array, Stack, Queue, Deque, Bag, Set, Priority queue, Dictionary (Map)

Question 14

Stack

Answer 14

A stack is an Abstract Data Type (ADT) in which items are only inserted on or removed from the top of a stack.

Common underlying data structures:
Linked list

Question 15

Queue

Answer 15

A queue is an Abstract Data Type (ADT) in which items are inserted at the end of the queue and removed from the front of the queue.

Common underlying data structures:
Linked list

Question 16

Deque

Answer 16

A deque (pronounced “deck” and short for double-ended queue) is an Abstract Data Type (ADT) in which items can be inserted and removed at both the front and back.

Common underlying data structures:
Linked list

Question 17

Bag

Answer 17

A bag is an Abstract Data Type (ADT) for storing items in which the order does not matter and duplicate items are allowed.

Common underlying data structures:
Array, linked list

Question 18

Set

Answer 18

A set is an Abstract Data Type (ADT) for a collection of distinct items. Duplicate items are not allowed.

Common underlying data structures:
Binary search tree, hash table

Question 19

Priority Queue

Answer 19

A priority queue is a Abstract Data Type (ADT) queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. Duplicate items are allowed.

Common underlying data structures:
Heap

Question 20

Dictionary (map)

Answer 20

A dictionary is an Abstract Data Type (ADT) that associates (or maps) keys with values.

Common underlying data structures:
Hash table, binary search tree

Question 21

Dynamic Array

Answer 21

A dynamic array is an Abstract Data Type (ADT) for holding ordered data and allowing indexed access.

Common underlying data structures:
Array

Question 22

List

Answer 22

A list is an Abstract Data Type (ADT) for holding ordered data. Duplicate items are allowed.

Common underlying data structures:
Array, linked list

Question 23

Heuristics

Answer 23

Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

In practice, solving a problem in the optimal or most accurate way may require more computational resources than are available or feasible. Algorithms implemented for such problems often use a heuristic.

Question 24

Self-adjusting heuristic

Answer 24

A self-adjusting heuristic is an algorithm that modifies a data structure based on how that data structure is used. Ex: Many self-adjusting data structures, such as red-black trees and AVL (Adelson-Velsky and Landis) trees, use a self-adjusting heuristic to keep the tree balanced. Tree balancing organizes data to allow for faster access.

Ex: A self-adjusting heuristic can be used to speed up searches for frequently-searched-for list items by moving a list item to the front of the list when that item is searched for. This heuristic is self-adjusting because the list items are adjusted when a search is performed.

Question 25

Greedy algorithm

Answer 25

A greedy algorithm solves a problem by assuming that the optimal choice at a given moment during the algorithm will also be the optimal choice overall. Greedy algorithms tend to be efficient, but certain types of problems exist where greedy algorithms don't find the best or optimal solution. However, greedy algorithms produce both efficient and optimal solutions for many problems, including the fractional knapsack problem and the activity selection problem.

Question 26

Dynamic programming

Answer 26

Dynamic programming is a problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem. Ex: Fibonacci numbers can be computed with an iterative approach that stores the 2 previous terms, instead of making recursive calls that recompute the same term many times over.

Question 27

Peek(stack)

Answer 27

Returns but does not remove item at top of stack

Question 28

Bounded stack

Answer 28

A bounded stack is a stack with a length that does not exceed a maximum value. The maximum is commonly the initial allocation size. Ex: A bounded stack with allocationSize = 100 cannot exceed a length of 100 items. A bounded stack with a length equal to the maximum length is said to be full. A bounded stack must have an attribute for maximum size and an if statement in the push() method. But the Stack *class* has neither, and so is an unbounded stack.

Question 29

Unbounded stack

Answer 29

An unbounded stack is a stack with no upper limit on length. An unbounded stack's length can increase indefinitely, so the stack's array allocation size must also be able to increase indefinitely.

Question 30

Queue vs Enqueue vs Dequeue

Answer 30

A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue. The queue enqueue operation inserts an item at the end of the queue. The queue dequeue operation removes and returns the item at the front of the queue. Ex: After the operations "Enqueue 7", "Enqueue 14", and "Enqueue 9", "Dequeue" returns 7. A second "Dequeue" returns 14. A queue is referred to as a first-in first-out ADT. A queue can be implemented using a linked list or an array.

Question 31

Trie

Answer 31

A trie (or prefix tree) is a tree representing a set of strings. Each non-root node represents a single character. Each node has at most one child per distinct alphabet character. A terminal node is a node that represents a terminating character, which is the end of a string in the trie. Tries provide efficient storage and quick search for strings, and are often used to implement auto-complete and predictive text input.

Question 32

Double data type

Answer 32

A "double" data type refers to a data type in programming that stores high-precision floating-point numbers, essentially allowing for decimal values with a larger range and more significant digits compared to a standard "float" data type; it is often called "double-precision" because it typically uses double the memory space of a float, usually occupying 8 bytes (64 bits) to store the value. Key points about the double data type: Precision: - Can store numbers with more decimal places than a float, usually around 15-16 significant digits. Range: - Can represent very large and very small numbers compared to other data types. Usage: - Commonly used in scientific calculations, financial applications, and scenarios where high accuracy with decimal values is needed

Question 33

Tuple

Answer 33

In Python, a tuple is an ordered, immutable sequence of elements. This means that once a tuple is created, its contents cannot be changed. Key points about tuples: - Immutable: Unlike lists, you cannot modify the elements of a tuple after it is created. - Ordered: Elements in a tuple maintain their order, just like in lists. - Heterogeneous: Tuples can contain elements of different data types, such as integers, strings, floats, and even other tuples. - Syntax: Tuples are defined by enclosing elements within parentheses () and separating them with commas. Example in Python: my_tuple = (1, "hello", 3.14, True) Common use cases for tuples: - Storing data that should not be changed: Tuples are ideal for storing data that needs to remain constant, like coordinates or database records. - Function return values: Functions can return multiple values as a tuple, allowing for convenient packing and unpacking of data. - Dictionary keys: Tuples can be used as keys in dictionaries because they are hashable (immutable).

Question 34

Garbage Collection

Answer 34

In data structures, "garbage collection" refers to an automated process where a program identifies and reclaims memory space occupied by data structures that are no longer being used, essentially removing "garbage" data and freeing up memory for new allocations, thus preventing memory leaks and simplifying memory management for developers. Key points about garbage collection: - Automatic process: Unlike manual memory management, garbage collection happens automatically without explicit code from the programmer to deallocate memory. - Identifying unreachable objects: The garbage collector determines which data structures are no longer accessible by the program (considered "garbage") by tracking references to objects. - Reclaiming memory: When an object is identified as garbage, the garbage collector reclaims its memory space, allowing it to be used for new data allocations. - Implementation methods: Different garbage collection algorithms exist, including reference counting and tracing algorithms, each with its own advantages and drawbacks. Benefits of garbage collection: - Reduced memory leaks: By automatically reclaiming unused memory, garbage collection significantly decreases the risk of memory leaks, which can lead to program crashes. - Simplified development: Developers don't need to manually manage memory allocation and deallocation, allowing them to focus on the core logic of their application. Important considerations: - Performance overhead: Garbage collection can sometimes introduce a small performance overhead as the garbage collector needs to periodically scan memory for unused objects. - Language support: Most modern programming languages like Java, C#, and Python have built-in garbage collection mechanisms Garbage is determined by identifying objects in a data structure that are no longer reachable from any active reference points, meaning they are not being used by the program and can be safely removed from memory; this is typically done by traversing the data structure starting from "root" objects and marking all reachable objects, with any remaining unmarked objects considered garbage

Question 35

How do you determine the children in a heap list?

Answer 35

For an element at index i, the left child is located at index 2i + 1, and the right child is located at index 2i + 2. i = index value

Question 36

Preorder tree traversal

Answer 36

Preorder tree traversal is a depth-first search algorithm that visits the nodes of a tree in a specific order, starting with the root node, then the left subtree, and finally the right subtree

Question 37

Pop()

Answer 37

A "pop()" function, when used on a list or array, removes the last element from that data structure and returns the value of the removed element; essentially, it takes the element off the end of the list and gives it back to you as the result of the function call