Algorithms And Complexity Assignment Question 1: 10 Mark.

Algorithms And Complexity Assignmentquestion 1 10 Mark Important Fea

Algorithms and Complexity Assignment Question 1 (10 mark) Important features of Object-Oriented programming are encapsulation, abstraction, inheritance and polymorphism. Describe an example where you have seen abstraction used in a program. Provide details.

Question 2 (10 mark) Given an n-element sequence S, you have an algorithm B that chooses (the next integer greater than nlogn) [nlogn]elements at random and executes an O(n³)-time calculating for each. What is the worst-case running time of B?

Question 3 (10 mark) A program to generate all the permutations of a set is run on a computer that writes the output to a file at a rate of 1300 permutations per second. How long will it take the computer to generate all the permutations of a set with 7 (distinct) elements?

Question 4 (10 mark) Write in pseudo code a recursive algorithm for finding the maximum element in a sequence, R, of p³ elements. What is your running time and space usage?

Question 5 (10 mark) Memoization and Dynamic programming are both methods used in recursive algorithms for what purpose? Explain how this is achieved.

Question 6 (10 mark) def Arithmetic (n) for i in range (1 ,n ): for j in range ( i ,( i +5)/3): a=ni - 2. j return a What is the big O complexity of Arithmetic? Show working. In question 6, in changing the assignments, i sometimes has the function iterate over a range where the parameters of the range may not be integers. If you have that error, replace range ( x, y) with range (x, floor(y)) where floor(y) is the integer n st. y-1

Question 7 (10 mark) What are the two manipulation functions required for a Queue ADT based on a Linked List. Give the pseudo code to implement these on the base structure.

Question 8 (30 marks) . 1) Write a definition for a general Graph and write in words Euler’s generalised theorem on the complete traversal of a graph, which is called an Eulerian cycle. If you remove the condition of the start and end point being the same, you have an Eulerian path 2) Draw a graph with 5 vertices that has: an Euler cycle; an Euler path but not an Euler cycle; neither of these. 3) Write in pseudo code an algorithm to traverse a graph and verify if the graph has an Eulerian cycle or path. First consider how you will represent the edges and vertices in your code and show this. Note: The Euler's theorem referred to in question 8 is the theorem relating to the Konigsberg bridge, and it is a generalised theorem on the complete traversal of a graph can be achieved if the number of edges on a vertex is always even then I asked for three types of graphs, where each graph has one of the properties given, you cannot do all in one.

Paper For Above instruction

This paper addresses a set of questions related to fundamental concepts in algorithms, object-oriented programming, graph theory, and data structures. Each question is explored with detailed explanations, pseudo code, and relevant examples to demonstrate a comprehensive understanding of the topics.

Question 1: Abstraction in Object-Oriented Programming

Abstraction is a core principle of Object-Oriented Programming (OOP) that involves hiding complex implementation details and exposing only essential features of an object. This allows developers to work with simplified interfaces, improving modularity and code manageability.

An example of abstraction can be seen in the design of a banking system. Consider a class Account that provides methods such as deposit(), withdraw(), and getBalance(). Internally, the class manages details like account number, transaction history, and security checks. These internal details are hidden from external users, who only interact through the defined interface, thereby abstracting away the complex underlying processes.

This abstraction enables the developer to change internal mechanisms, such as adding multi-factor authentication or improving security protocols, without affecting external code that interacts with the Account class. Such encapsulation of complexities exemplifies the power and utility of abstraction in OOP.

Question 2: Worst-Case Running Time of Algorithm B

Given an n-element sequence S and an algorithm B that selects approximately n^{log n} elements at random, executing an O(n³) calculation for each, the total worst-case runtime can be calculated as follows:

The number of elements selected: n^{log n}

Time per element: O(n³)

Thus, the total worst-case running time:

Runtime = n^{log n} * O(n³) = O(n^{log n + 3})

As n grows large, the dominant term is n^{log n} * n³ = O(n^{log n + 3}). This indicates that the runtime increases polynomially multiplied by a super-polynomial factor, reflecting a very high complexity for large input sizes.

Question 3: Time to Generate all Permutations of 7 Elements

The number of permutations of a set with 7 distinct elements is 7! = 5040.

The computer writes at a rate of 1300 permutations per second, so the total time T required is:

T = 5040 / 1300 ≈ 3.88 seconds

Thus, it would take approximately 3.88 seconds for the computer to generate all permutations of a 7-element set, assuming optimal performance and no I/O delays.

Question 4: Recursive Algorithm for Finding Maximum Element

Here is the pseudo code for a recursive function to find the maximum element in sequence R of p³ elements:

function findMax(R, start, end):
if start == end:
return R[start]
mid = (start + end) // 2
leftMax = findMax(R, start, mid)
rightMax = findMax(R, mid + 1, end)
return max(leftMax, rightMax)

Assuming the sequence R is indexed from 0 to p³-1. The time complexity is O(n), since each element is examined once, and the space complexity is O(log n) due to the call stack depth of the recursive function.

Question 5: Memoization and Dynamic Programming

Both memoization and dynamic programming are techniques used to optimize recursive algorithms by avoiding redundant calculations.

Memoization involves storing the results of expensive function calls when the same inputs occur multiple times. When a recursive function is invoked with the same parameters, the stored result is reused instead of recomputing, thereby reducing the exponential blow-up in recursive calls.

Dynamic programming, on the other hand, builds up solutions to smaller subproblems iteratively, storing these solutions in a table. It proceeds in a bottom-up manner, ensuring each subproblem is solved only once, which is especially effective for problems with overlapping subproblems and optimal substructure (e.g., Fibonacci sequence, shortest paths).

In summary, both methods enhance efficiency by storing intermediate results, with memoization using top-down recursion combined with caching, and dynamic programming employing a systematic bottom-up approach.

Question 6: Complexity of Arithmetic Function

The given code considers nested loops with varying ranges. For each i from 1 to n, the inner loop runs from i to (i + 5)/3 (floored).

Assuming the use of floor, the inner loop's number of iterations for each i is approximately:

iterations ≈ ((i + 5)/3) - i + 1 = ((i + 5) - 3i)/3 + 1 = (-2i + 5)/3 + 1

which simplifies for large i to roughly -2i/3 + constant.

Given that, the inner loop runs over decreasing values as i increases, but since for large i, the negative term dominates, the total work is dominated by the early iterations.

The total complexity is therefore approximately O(n). More precise analysis shows that overall, the time complexity is O(n), given the decreasing nature of inner loop iterations.

Question 7: Manipulation Functions for Queue ADT Based on Linked List

The two primary manipulation functions for a Queue are enqueue (to add elements at the rear) and dequeue (to remove elements from the front).

function enqueue(Q, x):
newNode = Node(x)
if Q.rear == null:
Q.front = newNode
Q.rear = newNode
else:
Q.rear.next = newNode
Q.rear = newNode
function dequeue(Q):
if Q.front == null:
return null  // Queue is empty
temp = Q.front
Q.front = Q.front.next
if Q.front == null:
Q.rear = null
return temp.value

These functions ensure First-In-First-Out (FIFO) behavior of the queue, with constant time complexity, O(1), for both operations.

Question 8: Graph Definitions, Euler's Theorem, and Algorithm

Definitions and Theorem

A graph G = (V, E) consists of a set of vertices V and edges E. Edges can be directed or undirected, and the graph may be weighted. An Eulerian cycle (or Eulerian circuit) is a cycle that traverses each edge exactly once and starts and ends at the same vertex. An Eulerian path is a trail that visits every edge exactly once but does not necessarily start and end on the same vertex.

Euler’s theorem on Eulerian cycles states that a connected, undirected graph has an Eulerian cycle if and only if every vertex has an even degree. For Eulerian paths, the graph must be connected with exactly zero or two vertices of odd degree.

Graphs Illustrating Different Properties

• Graph with an Euler cycle: All vertices have even degree and the graph is connected.
• Graph with an Euler path but not a cycle: Exactly two vertices have odd degree, and the graph is connected.
• Graph with neither: More than two vertices have an odd degree or the graph is disconnected.

Pseudo Code for Verifying Eulerian Properties

function isEulerian(G):
degreeCount = array of size |V| initialized to 0
for each vertex v in V:
degreeCount[v] = degree of v
oddVertices = count of vertices with odd degree in degreeCount
if not connected(G):
return "Not Eulerian"
if oddVertices == 0:
return "Eulerian cycle exists"
else if oddVertices == 2:
return "Eulerian path exists"
else:
return "Neither Eulerian cycle nor path"
function connected(G):
startVertex = any vertex with a non-zero degree
visited = set()
DFS(G, startVertex, visited)
for each vertex v in V:
if degree[v] > 0 and v not in visited:
return false
return true
function DFS(G, v, visited):
visited.add(v)
for neighbor u of v:
if u not in visited:
DFS(G, u, visited)

This algorithm checks graph connectivity and degree conditions to determine Eulerian properties, ensuring proper traversal and classification of the graph.

Conclusion

This comprehensive analysis elucidates critical concepts in algorithms and data structures. From understanding abstraction's role in object-oriented design to assessing graph properties related to Eulerian paths and cycles, the explanation combines theoretical foundations with practical pseudo code implementations. Such knowledge is essential for designing efficient algorithms and understanding their complexities in real-world applications.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.
• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
• Tarjan, R. (1983). Data Structures and Network Algorithms. SIAM.
• Harary, F. (1969). Graph Theory. Addison-Wesley.
• West, D. B. (2001). Introduction to Graph Theory. Prentice Hall.
• Hubbard, J. (2010). Eulerian Path and Circuit. In MathWorld. Wolfram Research.
• Johnson, D. B. (1973). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 20(1), 1-13.
• Skiena, S. S. (2008). The Algorithm Design Manual. Springer.