Analysis of Algorithms and Data Structures Assignment

This assignment solution addresses various concepts in data structures and algorithms. It begins by analyzing a sorting algorithm's functionality, identifying it as a descending-order sorting method, and discussing its time complexity. The solution then defines the impact of iterations and data size on algorithm performance. It explores topological sorting, time complexities of different methods, and distinctions between internal and external sorting, as well as stable and in-place sorting. The characteristics of queue operations (enqueue and dequeue) are outlined. The assignment also analyzes a code snippet involving permutations, calculates inversion counts in a list, and differentiates between Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms. Finally, it classifies the time complexities of different algorithms (quadratic, logarithmic, linear, and exponential).

Question One:
The code performs a sorting operation.
It does this using a nested loop that iteratively compares each of the values in the
original list with the rest and shifts the lesser value to the left. The outer iteration is
repeated until all elements in the list have been compared with each other. The inner
iteration goes on until a larger value is found then an assignment is done before
proceeding to the next iteration.
The result is a list sorted in descending order.
Question Two:
Iterations: The number of iterations(loops) done around the data. The more iterations
made, the slower the algorithm will appear to be
Size of n: The size/value of n also greatly affects the effectiveness of the data. The
large this value is, the slower the algorithm will appear to be
Question Three:
Topological sorting is the linear ordering of the vertices in a graph in such a way that
for each directed edge ab from vertex a to b, a always precedes b in ordering
Question Four:
methodA has time complexity of O(n)
methodB has time complexity of O(nLog(n))
methodC has time complexity of O(nLog(n))
Question Five:
Missing
Question Six:
a. Internal sorting, this is where data has to be sorted in the main memory always
which implies faster access. Here the complete sorting happens in the main memory
while in external sorting sorting happens outside the main memory.

b. An algorithm is referred to as stable when the two objects that has equal keys is in
the same order in the output as they are in the input while its unstable if they are
unequal
c. n-place update does the sorting by working in the allocated memory additional
memory in sorting algorithms require more memory in sorting process.
Question Seven:
The main methods or operations which are characterize of queues are
1. enqueue() − this method checks whether the queue is full or not, if full; print an
overflow error, else; increment the end of the queue with one more item
2. dequeue() − The method also checks if the queue is empty. if its empty; print an
underflow error and exit the program else; access the element at the beginning of
the queue

Question Eight:
A
Question Nine:
The code is a never recursive loop that takes a predefined text and appends to it the
word algoritmer infinitely, with each output being a differently arranged order of the
same word (algoritmer)
The code only iterates when the predefined text has a length of greater than one.
To generate the different order of the word algoritmer, the algorithm uses three
variables to switch adjacent characters, in each iteration, the current letter is
substituted with the next one to the right and the letters in previous and next position
get passed as the predefined text in the recursive call.
The code has a time complexity of O(n ^n)

Question Ten:
With “time” as the given word, the algorithm will append all possible permutations of
the word “time”
Question Eleven:
Inversion count Inversion List state
0 - [9, 76, 31, 12, 29, 55]
1 [9, 76] [76, 9, 31, 12, 29, 55]
2 [9,31] [76, 31, 9, 12, 29, 55]
3 [9, 12] [76, 31, 12, 9, 29, 55]
4 [9, 29] [76, 31, 12, 29, 9, 55]
5 [9, 55] [76, 31, 12, 29, 55, 9]
6 [12, 29] [76, 31, 29, 12, 55, 9]
7 [12,55] [76, 31, 29, 55, 12, 9]
8 [29, 55] [76, 31, 55, 29, 12, 9]
9 [31, 55] [76, 55, 31, 29, 12, 9]
Total inversions = 9
Question Twelve
Breadth First Search(BFS) is a search techniques that relies on traversing through
the vertex for finding the shortest path in a graph.
Depth First Search (DFS) is a search technique that relies on traversing through the
edges to reach destination.
There are several difference between BFS and DFS and one of them is on the data
structures. BFS uses the Queue data structure while DFS uses the Stack data
structure
Question Thirteen:
Algorithm A: Quadratic
Algorithm B: Logarithmic
Algorithm C:Linear
Algorithm D: Exponential