Unit 3 - Previous Questions

Decrease and Conquer

Write an algorithm for Insertion Sort.
Apply the algorithm to sort the following lists:
1. 189, 145, 168, 190, 129, 134, 117
2. 89, 45, 68, 90, 29, 32, 17
3. 89, 26, 47, 12, 54, 32

Write two differences between DFS and BFS.
Starting at vertex A, traverse the graph using both BFS and DFS. List the order of visited vertices. (2023 Sep, Fig 4)
Starting at vertex a, traverse the graph using DFS and construct the DFS tree. Indicate the order vertices are reached and become dead ends. (2020 Sep, Fig 19)
For the given graph: Write the adjacency matrix and adjacency list. Starting at vertex a and resolving ties alphabetically, traverse using DFS, numbering the order of visits. (2022 Sep, Fig 8)
Give the pseudocode for DFS. Apply it to the given graph starting at vertex a, and construct the DFS tree. Give the order in which the vertices are reached and became dead ends. (2021 Feb, Fig 19)
For the directed graph with edge set {(a,b), (b,c), (a,c), (c,d), (c,e), (e,f), (f,a), (f,g), (h,k), (k,l)}: has to be traversed using DFS. Draw the graph. Show the stack and DFS tree. list the properties of this graph, revealed after the traversal.
Identify the suitable traversal technique when data needs to be accessed from one node to all others. Justify your answer.
Write the algorithm which uses stack as data structure and apply it to the given network. (2020 Jan, Fig 12)

Define Topological Sorting: Explain the process of linearly ordering the vertices of a directed acyclic graph (DAG).
Define Topological Order: Describe the resulting sequence of vertices from a topological sort.
State the minimum condition for a valid topological sort: The graph must be a Directed Acyclic Graph (DAG).
A student can study Design and Analysis of Algorithms (DAA) with pre-knowledge of Data Structures (DS) and Discrete Mathematics (DM). Database Management Systems (DBMS) and DAA further help the student to learn Data Analytics (DA).
- Task 1: Construct a directed graph to represent these prerequisite dependencies. (Construct the graph and determine the topological order for the scenario.)
- Task 2: Find a valid topological order for studying the subjects.
Apply the DFS-based algorithm to solve the Topological Sorting problem of given graph. (2021 Oct, 2021 Sep, Fig 12 & Fig 14)
Apply the Source Removal algorithm to solve the topological sorting problem. (2023 Sep, Fig 5)
Topological sorting. (2020 Sep, Fig 20)

Explain any two methods for generating permutations with an example.
Discuss the Minimal Change Method and Johnson-Trotter Algorithm for generating permutaions with examples.
Write the Johnson-Trotter Algorithm to generate permutations and solve for {1, 2, 3}.

What is Presorting?
How can presorting help solve the Element Uniqueness Problem? Write an algorithm and analyze its time efficiency.
Write an algorithm to find the mode of a dataset using presorting and discuss time complexity. (i) When the list is not sorted
(ii) When the list is pre-sorted
Compare the time efficiency of both approaches.

Define a Heap and its types.
Write the Bottom-Up algorithm to construct a heap.
Apply the Bottom-Up algorithm to the following lists:
1. 4, 12, 9, 8, 7, 10 (include pictorial representation)
2. 1, 8, 6, 5, 3, 7, 4 (pictorial representation at each step)
3. 14, 22, 19, 18, 17, 10 (pictorial representation at each step)
Design an algorithm for Heap Sort and solve using the list: 1, 8, 6, 5, 3, 7, 4, 9.
Sort the list 3, 2, 4, 1, 6, 5 in ascending order using Heap Sort with array representation. Provide pictorial steps.
Apply Heap Sort to sort the list: 23, 34, 12, 10, 5, 18, 20, 25.