Algorithm Design & Data Structures Flashcards

What is the primary purpose of an algorithm?

Answer: To solve problems using a defined sequence of steps

The primary purpose of an algorithm is to solve problems by providing a defined, finite sequence of unambiguous steps or instructions. It acts as a blueprint for computation, taking an input, performing a series of operations, and producing a desired output. Algorithms are fundamental to all computer programming.

Which data structure is most suitable for implementing a LIFO (Last In, First Out) principle?

Answer: Stack

A Stack is a linear data structure that strictly follows the Last In, First Out (LIFO) principle. This means the last element added to the stack is always the first one to be removed. Operations like `push` (adding an element) and `pop` (removing an element) occur only at one end, known as the 'top' of the stack.

What is a binary search algorithm?

Answer: It divides the list into two and searches through one half

A binary search algorithm is an efficient method for finding an element within a sorted list or array. It works by repeatedly dividing the search interval in half. If the middle element is not the target, the algorithm determines whether to continue searching in the left or right half, effectively eliminating half of the remaining elements in each step.

What is the time complexity of an algorithm that performs a linear search in an unsorted array?

Answer: O(n)

The time complexity of a linear search in an unsorted array is O(n), which stands for 'Order of n'. In the worst-case scenario, the algorithm might have to check every single element in the array until the target is found or the end is reached. Therefore, the time taken grows linearly with the number of elements 'n'.

Which of the following is a non-linear data structure?

Answer: Binary Tree

A Binary Tree is a non-linear data structure where each node has at most two children, typically referred to as the left child and the right child. Unlike linear structures like arrays, linked lists, and stacks, which arrange data sequentially, a binary tree organizes data hierarchically in a branching fashion.

What is the space complexity of a recursive algorithm?

Answer: O(n)

The space complexity of a recursive algorithm is typically O(n), where 'n' often represents the depth of the recursion. This is because each recursive call adds a new frame to the call stack to store local variables, parameters, and the return address. In the worst case, the stack space can grow proportionally to the input size or recursion depth.

Which of the following is an example of a divide-and-conquer algorithm?

Answer: Merge Sort

Merge Sort is a classic example of a divide-and-conquer algorithm. It works by recursively dividing an unsorted list into 'n' sublists, each containing one element (the 'divide' step). Then, it repeatedly merges sublists to produce new sorted sublists until there is only one sorted list remaining (the 'conquer' step).

What is the primary use case of a hash table?

Answer: Direct access to data using a key

A hash table's fundamental strength lies in its ability to map keys to values, allowing for nearly instantaneous retrieval of data. By using a hash function, it computes an index directly from a given key, enabling O(1) average-case time complexity for operations like insertion, deletion, and lookup. This direct access capability makes it ideal for applications requiring fast data retrieval based on unique identifiers.

What does O(log n) time complexity represent?

Answer: Logarithmic growth

O(log n) time complexity signifies logarithmic growth, meaning the execution time or space requirements of an algorithm increase very slowly as the input size (n) grows. For example, doubling the input size only adds a constant amount of work, not doubles it. This efficiency is characteristic of algorithms that repeatedly divide the problem into smaller subproblems, such as binary search or operations on balanced binary trees.