Algorithms: Question Set – 19

Algorithms: Question Set – 19

What is Sorting Network?

  • A numerical model of a network of wires and comparator modules that is used to sort a series of numbers is called a sorting network.
  • This model is used to sort the numbers. Every comparator has two wires that it connects together and sorts the values by sending the value that is lower to one wire and the value that is higher to the other wire.
  • The primary distinction between sorting networks and comparison sorting algorithms is that, with a sorting network, the series of comparisons is predetermined in advance, whereas with comparison sorting algorithms, the series of comparisons is determined by the outcome of the comparisons that came before it.
  • Because of this independence of comparison series, parallel execution of the methods can benefit greatly from having this property.
  • Types of sorting networks:
    • Comparison network
    • Bitonic sorting network
    • Merging network

What is prim’s algorithm?

Prim’s algorithm is a technique that is used to find the minimum spanning the tree of a weighted linked graph. It is a greedy technique, but it is also an efficient one.

What is the use of Dijkstra’s algorithm?

  • For the purpose of solving the single-source shortest-paths method, the Dijkstra procedure is utilized.
  • This method requires finding the shortest path from a given vertex, referred to as the source, in a weighted linked graph to all of the graph’s other vertices.
  • The process of finding the single-source shortest paths requires the submission of a family of paths, each of which leads from the source to a different vertex in the graph, despite the fact that some directions may share edges.

What is Floyd’s algorithm?

Floyd’s algorithm is a function that is used to solve the problem of finding all of the pairs with the shortest paths. The algorithm developed by Floyd is applicable to both directed and undirected weighted graphs; however, neither of these types of graphs contain cycles with a negative length.

What is Dijkstra’s Algorithm?

The single-source shortest path method is solved by Dijkstra’s algorithm. It finds the shortest paths from a given vertex (the source) to another vertex of a weighted graph or digraph. The implementation of a correct solution for a graph with non-negative weights is provided by Dijkstra’s algorithm.

What are the huffman trees?

A Huffman tree is a type of binary tree that includes a set of predefined weights and shortens the length of the weighted path that travels from the root to the leaves of the tree. The Huffman code is the most important use of Huffman trees.

What do you mean by Huffman code?

A Huffman code is an optimal prefix tree variable-length encoding technique that assigns bit strings to characters based on the frequency with which they appear in a given text. This technique is used to create Huffman codes.

List the advantage of Huffman’s encoding?

Huffman’s encoding is one of the essential file compression techniques.

  • It is easy
  • It is flexibility
  • It implements optimal and minimum length encoding

What is dynamic Huffman coding?

When using dynamic Huffman coding, the coding tree is updated whenever a new character is read from the source text. This ensures that the coding is as accurate as possible. Utilizing dynamic Huffman n-coding allowed us to get around the drawbacks of using the simplest version.

What is the state-space tree?

  • Constructing a tree that represents the decisions that have been made allows the processing of backtracking to be finished.
  • The term for this structure is “state-space tree.” It begins with a description of the situation that exists before any attempt is made to find a solution.
  • The decisions that were made for the first part of the solution are detailed in the nodes of the tree’s first level; similarly, the nodes of the tree’s second level detail the decisions that were made for the second part of the solution, and so on.
  • putting n different people in charge of n different tasks in order to keep the overall cost of the assignment to a minimum.
  • The instance of the problem is particularised as an n-by-n cost matrix C. This allows the problem to be described as choosing one element from each row of the matrix in such a way that no two selected items are in the same column and the sum is as small as it can possibly be.