Data Structures and Algorithms: Core Concepts

Question 1

What is the relationship between an algorithm and a program?

Accepted Answer

A program is a formal implementation of an algorithm.

Question 2

What is an Abstract Data Type (ADT)?

Accepted Answer

A group of data structures with shared functionality but different representations.

Question 3

How does a set differ from a list regarding its elements?

Accepted Answer

Sets contain unique, unordered elements; lists are ordered sequences.

Question 4

Which abstract data type is defined by unordered associations between unique keys and values?

Accepted Answer

A map (or dictionary).

Question 5

What is the primary operation focus of a priority queue?

Accepted Answer

Retrieving and removing the element with the highest priority.

Question 6

What defines a graph data structure?

Accepted Answer

Vertices and edges representing binary relations between entities.

Question 7

Why does an array list allow for faster "random access" than a linked list?

Accepted Answer

Elements are stored next to each other in memory.

Question 8

In what specific operation does a linked list typically outperform an array list?

Accepted Answer

Fast insertion and deletion.

Question 9

What is the goal of algorithmic problem-solving compared to traditional mathematical problem-solving?

Accepted Answer

Finding an efficient solution in terms of time or space.

Question 10

In algorithm design, what is a "model"?

Accepted Answer

A simplified, abstract representation of a complex real-world problem.

Question 11

How do machine learning algorithms differ from classical algorithms in problem modeling?

Accepted Answer

They use massive models of phenomena instead of strict formal logic.

Question 12

Define "experimental analysis" of an algorithm's runtime.

Accepted Answer

Recording the actual time a program implementation takes to run.

Question 13

What is a major downside to using experimental analysis to compare algorithm designs?

Accepted Answer

Results vary based on the specific computer's processing power and memory.

Question 14

What is the difference between time complexity and space complexity?

Accepted Answer

Time complexity measures execution time; space complexity measures memory usage.

Question 15

What does Big O notation specifically measure?

Accepted Answer

The worst-case complexity (order of growth) as input size increases.

Question 16

What happens to the execution time of an algorithm with "constant" order of growth as problem size increases?

Accepted Answer

The execution time remains the same.

Question 17

What are the three steps of the Divide and Conquer algorithmic paradigm?

Accepted Answer

Divide (into subproblems), Conquer (solve recursively), and Combine (form solution).

Question 18

What is the fundamental programming tool used to solve subproblems in Divide and Conquer?

Accepted Answer

Recursion.

Question 19

Why is the "combinatorial explosion" a problem for brute-force algorithms?

Accepted Answer

The number of potential solutions grows exponentially, making them unusable.

Question 20

How does a greedy algorithm select the next element for a solution?

Accepted Answer

By repeatedly applying a simple rule to pick the best immediate option.

Question 21

What is the main risk of using a greedy algorithm?

Accepted Answer

It may not find the globally optimal (best) solution.

Question 22

What is the time complexity (Big O) of a sequential search on $N$ elements?

Accepted Answer

O(N).

Question 23

What are the two requirements for binary search to be efficient?

Accepted Answer

A sorted list and constant-time indexed access.

Question 24

What is the time complexity (Big O) of a binary search on $N$ elements?

Accepted Answer

O(log N).

Question 25

How do Merge Sort and Quicksort differ in when they rearrange data?

Accepted Answer

Merge Sort merges after recursion; Quicksort partitions before recursion.