Algorithms: Question Set – 03

Algorithms: Question Set – 03

How does time complexity affect performance in terms of CPU, Memory, disk I/O, network bandwidth, etc.?

The amount of time it takes for an algorithm to run in relation to the magnitude of the data that it receives is referred to as the algorithm’s temporal complexity. It will take a longer amount of time to run if the input is larger. This can have an effect on performance in terms of CPU, memory, disc I/O, and network bandwidth because the longer it takes to run, the more resources it will require. This can have an influence on performance.

What is your understanding of the pre-order traversal of trees?

A method known as pre-order traversal of trees is a form of tree traversal in which the root node of the tree is visited first, then the left subtree, and finally the right subtree in that sequence.

When employing depth-first search, the most effective way to navigate a tree is to begin at the tree’s root node and work your way outward, exploring each branch as thoroughly as you can before proceeding to the next branch.

What do you mean by Amortized Analysis?

An amortised analysis determines the average amount of time needed to complete each operation across all of the worst-case scenarios. The difference between amortised analysis and average-case performance is that amortised analysis does not take probability into account; instead, it guarantees the time required for each operation based on the worst-case scenario.

Enumerate some important types of problems.

  • Sorting
  • Searching
  • Numerical problems
  • Geometric problems
  • Combinatorial Problems
  • Graph Problems
  • String processing Problems

How is an algorithm’s time efficiency measured?

The time efficiency of an algorithm describes how quickly it executes. The time efficiency of an algorithm can be evaluated as a function of the size of the data that it processes by counting the number of times its fundamental operation (its running time) is carried out. The most fundamental operation is the one that consumes the greatest time within the innermost loop of the algorithm.

What is Big ‘Oh’ notation?

A function t(n) is said to be in O(g(n)), denoted t(n) O(g(n)) , if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and some nonnegative integers n0 such that t(n) ≤ cg(n) for all n≥ n0

What are algorithm design techniques?

Techniques for the design of algorithms, often known as strategies or paradigms, are overarching approaches to the algorithmic resolution of issues. These techniques can be used to a wide variety of challenges originating from numerous subfields of computing. General design techniques are:

  • Brute force
  • Divide and conquer
  • Decrease and conquer
  • Transform and conquer
  • Greedy technique
  • Dynamic programming
  • Backtracking
  • Branch and bound