1.

​Introduction
2.​
3.​
4.​What is an algorithm?
○​ An algorithm is a method for solving a problem, such as sorting or
searching.
5.​Can you explain what a data structure is?
○​ A data structure is a method to store information efficiently, such as trees
or linked lists.

Course Specifics
3.​Who is responsible for the Algorithms course?
○​ Morgan Ericsson is the course responsible and examiner.
4.​How are students expected to stay updated on course material?
○​ Students are expected to stay up to date with materials posted on Moodle
and the Slack channel.

Concepts and Implementations

5.​What are some everyday applications of algorithms and data
structures?
○​ Algorithms and data structures are used in networking, web search, AI
and machine learning, physics simulations, video compression, and
security and encryption.
6.​What is the importance of studying data structures for a
programmer?
○​ Good programmers focus on data structures and their relationships
because they significantly affect the performance and scalability of
software.

Detailed Technical Questions

7.​Can you describe the union-find data structure and its operations?
○​ The union-find data structure supports two operations: union(a, b),
which connects two elements, and connected(a, b), which checks if
two elements are connected.
8.​Explain the concept of path compression in the union-find data
structure.
○​ Path compression is a technique used to flatten the structure of the tree
whenever find is called so that all nodes directly point to the root. This
speeds up future operations.
9.​What is the difference between quick-find and quick-union
approaches?
○​ Quick-find checks connectivity quickly but union operations are slow
because it needs to update the id of all elements. Quick-union improves
on this by linking root elements, making unions faster but potentially
slowing down finds if the tree becomes too tall.
10.​ Discuss the weighted quick union approach.
○​ In weighted quick union, the size of each tree is tracked, and the smaller
tree is always attached to the larger tree during union operations. This
approach helps keep the tree flatter, improving the performance of find
operations.

Application and Example

11.​ Can you walk through a specific example where algorithms might
be applied?
○​ Consider a problem where we need to determine if there is a path that
connects two specific nodes in a network. Using the union-find data
structure, we can efficiently manage and query connectivity between any
two nodes.

************************************************************************************

Algorithm analysis
Basic Understanding of Algorithm Analysis
1.​What is the purpose of algorithm analysis?
○​ To determine the efficiency of an algorithm in terms of time and space
used, which helps in predicting the performance and scalability of the
algorithm.
2.​What does the term 'growth' refer to in the context of algorithms?
○​ Growth refers to how the running time or space requirements of an
algorithm increase as the size of the input data increases.

Deep Dive into Specific Concepts

3.​Explain Big O notation and provide an example.
○​ Big O notation describes the upper limit of the time complexity of an
algorithm, providing a worst-case scenario. For example, if an algorithm
is O(n²), it means the time it takes to complete could be proportional to
the square of the input size in the worst case.
4.​What is meant by linear growth in algorithms?
○​ Linear growth occurs when the performance of an algorithm increases
linearly with the input size. For instance, if an algorithm takes 5 minutes
to process 10 items, it would take 50 minutes to process 100 items,
assuming a linear relationship.

Application and Examples

5.​Can you describe a scenario where the algorithm's time complexity
is O(n log n)?
○​ An example of O(n log n) complexity is the merge sort algorithm, where
the list is divided into halves, each sorted recursively, and then merged.
This division and merging process leads to a complexity of O(n log n).
6.​How would you use a plot to explain the performance of an
algorithm?
○​ By plotting the running time of an algorithm against the size of the input
data, one can visually understand how the running time increases, which
can illustrate concepts like linear, quadratic, or exponential growth.
Technical Scenario-Based Questions
7.​If an algorithm has a time complexity of O(2^n), what does that
imply about its scalability?
○​ A time complexity of O(2^n) implies exponential growth, meaning the
algorithm becomes impractically slow even for relatively small input sizes
due to the doubling effect of the input size on the running time.
8.​Discuss the impact of algorithm efficiency on software performance
with an example.
○​ Efficient algorithms, such as quicksort over bubble sort, significantly
enhance software performance, especially evident in large-scale data
processing, where the lesser number of operations leads to faster
processing and less resource consumption.

****************************************************************************

Lists, Stacks & Queues

Stacks, and Queues:

Basic Understanding
1.​What is an Abstract Data Type (ADT)?
○​ An ADT is a model for a data structure that defines the type by its
behavior from the user's perspective, focusing on the operations it
supports rather than its implementation.
2.​Can you explain the difference between an ADT and a concrete data
structure?
○​ An ADT is a theoretical concept that defines a data type purely by what
operations can be performed on it, without specifying how these
operations are implemented. A concrete data structure, on the other
hand, provides a specific implementation of an ADT in a particular
programming language.

Specific Data Structures

3.​What operations are typically supported by a stack and what is its
LIFO property?
○​ A stack supports operations such as push, pop, and top. The LIFO (Last
In, First Out) property means that the last element added to the stack will
be the first one to be removed.
4.​Describe how a queue operates and its FIFO property.
○​ A queue supports operations like enqueue (add to back) and dequeue
(remove from front). The FIFO (First In, First Out) property ensures that
the first element added to the queue is the first one to be removed.

Implementation and Usage

5.​How would you implement a simple list using an array? Discuss the
methods you would include.
○​ A simple list can be implemented using an array to store elements.
Methods might include init for initialization, append for adding
elements, delete to remove elements, and empty to check if the list is
empty.
6.​Discuss a scenario where you would use a stack versus using a
queue.
○​ Stacks are preferable when you need to access data in a reverse order
from which it was added, such as when parsing expressions or managing
function calls in recursion. Queues are useful for managing tasks in
sequential order, like processing requests on a server or breadth-first
search in graphs.

Advanced Concepts
7.​What is the significance of resizing an array in the context of
implementing a list?
○​ Resizing is crucial when the initial array fills up, as it allows the list to
accommodate more elements. It usually involves creating a new, larger
array and copying existing elements to it, which can be computationally
expensive.
8.​Can you explain how dynamic arrays work, using Python's list or
Java's ArrayList as an example?
○​ Dynamic arrays automatically resize as elements are added. In Python,
lists grow by allocating a larger array when the current capacity is
exceeded, copying the old elements to the new array. This process
usually involves doubling the array size, which amortizes the cost of
resizing over multiple append operations.

******************************************************************************

Trees

Basic Understanding
1.​What is a tree in the context of data structures?
○​ A tree is a collection of nodes with one distinguished node called the root.
Each node can have zero or more child nodes, and all child nodes can
have their own subtree.
2.​Define a binary tree.
○​ A binary tree is a tree where each node has at most two children, often
referred to as the left and right child.

Detailed Concepts
3.​What are binary search trees (BSTs)?
○​ A binary search tree is a binary tree where each node has a key greater
than all the keys in the node's left subtree and less than those in its right
subtree.
4.​Explain the concept of tree height and how it affects operations in a
tree.
○​ The height of a tree is the length of the longest path from the root to a
leaf. The efficiency of many operations on trees, like search, insert, and
delete, depends on the height of the tree because it determines the
maximum number of comparisons needed.
Specific Tree Types and Operations
5.​What is an AVL tree and how does it differ from a regular binary
search tree?
○​ An AVL tree is a type of self-balancing binary search tree where the
heights of the two child subtrees of any node differ by no more than one.
If at any time the heights differ more than this, rebalancing is done to
restore this property.
6.​Describe a rotation in an AVL tree.
○​ A rotation in an AVL tree is a tree manipulation to restore its height
balance. There are four types of rotations: left, right, left-right, and
right-left, depending on the imbalance's structure.

Advanced Applications
7.​How would you use a tree structure to organize file systems in
operating systems?
○​ Trees are used in file systems to organize files and directories into a
hierarchical structure, where each directory or file is a node, and
directories can contain other files or directories as children.
8.​Can you implement a function to insert a node in a binary search
tree?
○​ Yes, the insertion function would involve starting at the root and
recursively comparing the insert key with the current node's key to decide
whether to insert into the left or right subtree, ensuring the properties of
the BST are maintained.

**************************************************************************

Hashing

Basic Understanding
1.​What is hashing and why is it used in data structures?
○​ Hashing is a technique used to uniquely identify a specific item from a
collection of items. It's primarily used to speed up data retrieval by
reducing the average lookup time.

Detailed Concepts
2.​Explain different methods of handling collisions in hashing.
○​ Collisions can be handled using separate chaining, where each bucket of
the hash table contains a linked list of entries that hash to the same
index, or open addressing methods like linear probing and double
hashing where collisions are resolved by finding another open slot within
the hash table.

Technical Details
3.​What is separate chaining and how does it work?
○​ Separate chaining is a collision resolution method in hashing where each
bucket in the hash table is independent, and has a linked list of entries for
handling collisions. When a collision occurs, the new element is added to
the end of the list at that bucket.
4.​Describe linear probing and its efficiency.
○​ Linear probing resolves collisions by placing the new key into the next
available bucket in the hash table. It's efficient if the load factor is low but
can lead to clustering, which impacts performance negatively when the
table gets fuller.

Advanced Applications
5.​What is double hashing and how does it improve on linear probing?
○​ Double hashing uses a second hash function to determine the step size
for probing, reducing the clustering problems seen with linear probing.
This results in better performance distribution across the hash table.
6.​Explain how a perfect hashing function can be designed.
○​ A perfect hashing function would map each possible key to a unique
bucket address in the hash table with no collisions. In practice, designing
 a perfect hash function is challenging and often not feasible for arbitrary
data sets.

Practical Examples
7.​How can hashing be used to improve search operations in a
database?
○​ Hashing can store data in a way that allows extremely quick retrieval by
using keys to index into a hash table, minimizing the time it takes to find
an item as compared to sequential searching or even binary searches in
sorted lists.
8.​Discuss the impact of load factor on the performance of a hash
table.
○​ The load factor, defined as the number of entries divided by the number
of buckets, directly affects performance. A lower load factor reduces the
likelihood of collisions, thus improving lookup performance, but may
increase memory usage.

+*************************************************************************************

Priority queue ( heap )

Basic Understanding
1.​What is a priority queue?
○​ A priority queue is a type of abstract data structure in which each element
has a priority assigned to it. Elements are added to the queue and
removed according to their priority, usually either the highest or lowest
priority is removed first.
2.​How does a priority queue differ from a regular queue?
○​ Unlike a regular queue, which follows a first-in-first-out (FIFO) order, a
priority queue removes elements based on priority, ensuring that the item
with the highest (or lowest) priority is removed first, regardless of the
order they were added.
Specific Data Structures
3.​What is a heap, and how is it related to priority queues?
○​ A heap is a specialized tree-based data structure that satisfies the heap
property: if P is a parent node of C, then the key (the value) of P is either
greater than or equal to (in a max heap) or less than or equal to (in a min
heap) the key of C. Heaps are commonly used to implement priority
queues because they allow quick retrieval and deletion of the highest (or
lowest) priority item.
4.​Can you explain the operations on a binary heap?
○​ The primary operations include insert, which adds a new item and
maintains the heap structure by potentially "swimming" the element up to
its correct position, and delMax or delMin, which removes the
maximum or minimum element, respectively, and then "sinks" the new
top element to maintain heap properties.

Implementation and Usage

5.​How is a binary heap implemented using an array?
○​ In an array-based implementation of a binary heap, the elements are
stored in a way that represents a nearly complete binary tree. Each
element at index i has children at indices 2*i and 2*i + 1 and a
parent at index i/2, which allows for efficient traversal and maintenance
of the heap properties.
6.​Describe the 'swim' and 'sink' operations in the context of heaps.
○​ The 'swim' operation is used to restore heap order when a new element
is inserted at the end of the heap. It involves comparing the inserted
element with its parent and swapping them if the heap order is violated.
This process continues until the heap order is restored.
○​ The 'sink' operation is used after removing the root element of the heap.
The last element of the heap is moved to the root, and then it is "sunk"
down by swapping it with its highest priority child until the heap order is
restored.

Advanced Concepts
7.​What challenges arise in implementing a priority queue using a
binary search tree?
○​ While binary search trees allow for efficient in-order traversal and can
theoretically provide quick access to the largest and smallest elements,
they can become unbalanced, leading to inefficient operations. Balancing
techniques or different tree structures like AVL or Red-Black trees are
required to maintain efficiency.
8.​Discuss the efficiency of heap operations.
○​ The efficiency of heap operations like insertion and deletion (removal of
the max/min element) is O(log n) due to the need to maintain the heap
structure either through 'swim' or 'sink' operations, which move elements
up or down the tree structure logarithmically relative to the total number
of elements.

**************************************************************************************
*********

Sorting

Basic Understanding
1.​What is a sorting algorithm?
○​ A sorting algorithm is a method used to rearrange a sequence of
elements into a specific order, such as ascending or descending.

Specific Algorithms
2.​Can you explain how the selection sort algorithm works?
○​ Selection sort repeatedly finds the smallest element from the unsorted
section and moves it to the beginning. This is done by swapping the
smallest found element with the element at the current beginning of the
unsorted section until the entire array is sorted.
3.​What is the difference between bubble sort and insertion sort?
○​ Bubble sort repeatedly steps through the list, compares adjacent
elements, and swaps them if they are in the wrong order. Insertion sort
 builds the final sorted array one item at a time, with each new item being
inserted back into the previous sublist such that the sorted sublist is one
item larger with each iteration.

Complexities and Properties

4.​What makes an algorithm stable, and is selection sort stable?
○​ An algorithm is stable if it preserves the relative order of elements with
equal keys. Selection sort is generally not stable because it may swap
distant elements, thus changing their relative order.
5.​Why is merge sort considered a divide and conquer algorithm?
○​ Merge sort divides the array into two halves, recursively sorts the two
halves, and then merges the two sorted halves back together. This
approach is based on the divide and conquer paradigm.

Efficiency and Practical Use

6.​What is the time complexity of quicksort, and under what conditions
might it perform poorly?
○​ Quicksort has an average time complexity of O(n log n) but degrades to
O(n²) in the worst case when the pivot elements are not well chosen,
such as when the smallest or largest element is consistently chosen as
the pivot.
7.​How does the shell sort improve on simple insertion sort?
○​ Shell sort allows the exchange of items that are far apart, reducing the
total number of moves required. It uses a sequence of intervals to
perform a h-sorting and progressively reduces the interval size to perform
finer insertions, which typically leads to less overall comparisons and
movements compared to simple insertion sort.

Practical Application
8.​Describe a scenario where you might prefer to use radix sort over
comparison-based sorting methods.
○​ Radix sort is preferable when dealing with fixed length data like integers
or strings where the length of the data items (digits or characters) is
 known and uniformly distributed, for example, sorting a large set of
fixed-length phone numbers or the employee IDs within a company.

**************************************************************************************
**********

Graphs

Basic Understanding
1.​What is a graph in the context of computer science?
○​ A graph consists of vertices (nodes) and edges (links between nodes)
and can represent a wide range of real-world structures like networks,
social connections, and web pages.

Specific Algorithms
2.​Can you explain the difference between breadth-first search (BFS)
and depth-first search (DFS) in graph traversal?
○​ BFS explores the graph level by level, starting from the given source
node and exploring all its neighboring nodes at the present depth prior to
moving on to nodes at the next depth level. DFS, on the other hand,
explores as deep as possible along each branch before backtracking.

Detailed Concepts
3.​What are connected components in a graph?
○​ Connected components in a graph are subgraphs in which any two
vertices are connected to each other by paths, and which are connected
to no additional vertices in the supergraph.
4.​Describe how to find all paths between two vertices using DFS.
○​ Using DFS to find all paths between two vertices involves exploring all
possible paths from the source vertex to the destination, marking vertices
as visited along the way to avoid cycles and backtracking after reaching
the destination or a vertex with no unvisited adjacent vertices.

Advanced Applications
5.​Explain Dijkstra’s algorithm for finding the shortest path in a graph.
○​ Dijkstra's algorithm solves the single-source shortest path problem for a
graph with non-negative edge weights, using a priority queue to greedily
select the next vertex with the smallest tentative distance.
6.​Discuss how a graph can be used to represent and solve routing
problems in networks.
○​ Graphs model the connectivity between nodes (e.g., routers or switches)
in a network, where edges can represent available routes and their
weights can represent costs. Algorithms like Dijkstra’s or Bellman-Ford
are used to find optimal routing paths.

Implementation and Usage

7.​How do you implement an adjacency list and an adjacency matrix in
programming? What are the trade-offs between the two?
○​ An adjacency list is implemented using a list of lists (or a dictionary of
lists), where each list at index i represents the vertices connected to
vertex i. An adjacency matrix is a 2D array where the entry at row i and
column j is true if there is an edge from i to j. Adjacency lists are more
space-efficient for sparse graphs, while adjacency matrices provide faster
access for edge existence queries.

**************************************************************************************
****

Design and Complexity

Basic Understanding
1.​What is an exponential time algorithm?
○​ An exponential time algorithm is one where the time complexity increases
exponentially with the input size, often represented as O(2^n), making it
impractical for large inputs.
Detailed Concepts
2.​Explain the concept of computability in the context of algorithms.
○​ Computability refers to the ability of an algorithm to solve a problem
within finite time and resources, often evaluated through models of
computation such as Turing machines.

Advanced Applications
3.​What are the classes P and NP, and how do they differ?
○​ Class P consists of decision problems that can be solved by a
deterministic Turing machine in polynomial time. Class NP includes
decision problems solvable in polynomial time by a nondeterministic
Turing machine. The key difference is the use of nondeterminism, where
NP problems can verify solutions in polynomial time even if finding the
solution might be harder.

Implementation and Usage

4.​Discuss the significance of the knapsack problem in studying
algorithms.
○​ The knapsack problem, particularly in its binary and fractional forms,
exemplifies the challenges in designing algorithms that provide optimal
solutions, demonstrating concepts like the greedy choice and dynamic
programming.

Practical Examples
5.​How can the Fibonacci sequence be efficiently computed using
dynamic programming?
○​ Dynamic programming can efficiently compute Fibonacci numbers using
memoization, which stores previously computed values, or tabulation,
which iteratively builds up solutions to larger problems based on solutions
to smaller problems.

Theory and Definitions

6.​What does it mean for a problem to be NP-complete?
○​ An NP-complete problem is one that is both in NP and as hard as any
problem in NP, meaning any NP problem can be reduced to it in
polynomial time. These problems are considered the most challenging
within NP, assuming P ≠ NP.

Real-World Applications
7.​Can you explain how reductions are used to prove problem
complexities?
○​ Reductions transform one problem into another to demonstrate that
solving one problem (often a known difficult problem) can solve another,
thus proving that the second problem is at least as hard as the first. This
is used to classify problems as NP-hard or NP-complete.