# Algorithms: Question Set – 16

#### Write an algorithm to reverse a string

- Step1: start
- Step2: Take two variable i and j
- Step3: do length (string)-1, to set J at last position
- Step4: do string [0], to set i on the first character.
- Step5: string [i] is interchanged with string[j]
- Step6: Increment i by 1
- Step7: Increment j by 1
- Step8: if i>j then go to step3

#### What are the differences between stack and Queue?

- Both the Stack and the Queue are examples of non-primitive data structures that are used for storing data components and are modelled after their counterparts in the real world.
- Let’s have a look at some of the most important distinctions based on the following criteria.
- Working principle
- The significant difference between stack and queue is that stack uses LIFO (Last in First Out) method to access and add data elements whereas Queue uses FIFO (First in first out) method to obtain data member.

- Structure
- In Stack, the same end is used to store and delete elements, but in Queue, one end is used for insertion, i.e., rear end and another end is used for deletion of elements.

- Number of pointers used
- Stack uses one pointer whereas Queue uses two pointers (in the simple case).

- Operations performed
- Stack operates as Push and pop while Queue operates as Enqueue and dequeuer.

- Variants
- Stack does not have variants while Queue has variants like a circular queue, Priority queue, doubly ended Queue.

- Implementation
- The stack is simpler while Queue is comparatively complex.

#### What is the difference between the Singly Linked List and Doubly Linked List data structure?

- The capacity to traverse is what distinguishes a singly linked list from a doubly linked list as the primary differentiator between the two.
- You are unable to traverse backwards in a singly linked list because each node in the list can only point in the direction of the following node, and there is no pointer to the node that came before.
- On the other hand, if you use a doubly linked list, you will be able to navigate in either direction within any linked list. This is because the doubly linked list keeps track of two pointers that point towards the next and previous nodes.

#### Mention what are the three laws of recursion algorithm?

All recursive algorithm must follow three laws:

- It should have a base case
- A recursive algorithm must call itself
- A recursive algorithm must change its state and move towards the base case

#### What is a Hash Table?

- A hash table is a data structure that may store values to keys of any type. Hash tables are sometimes known as “hashes.”
- The Hash table is an index into an array that is constructed with the help of a Hash function.
- The elements are stored using indexes as the primary mechanism. We use a hash function to determine which bucket each possible element belongs to and then assign it to that bucket.
- Given that a single bucket might be associated with more than one key at a time, it only makes sense that each key’s associated value is kept in a list within the bucket to which it is assigned. Choosing the correct hashing function can have a significant effect on performance.

#### How Breadth First Search (BFS) works?

- The algorithm known as BFS, or Breadth First Search, is used to traverse graphs.
- It begins its exploration of the graph at the root node and continues outward to each of the nodes that are adjacent.
- It chooses the node that is geographically closest to it and then proceeds to investigate all of the other nodes.
- The algorithm repeats the same steps for each of the nodes that are physically nearest to it until it reaches the desired end state.
- Step1: Set status=1 (ready state)
- Step2: Queue the starting node A and set its status=2, i.e. (waiting state)
- Step3: Repeat steps 4 and 5 until the queue is empty.
- Step4: Dequeue a node N and process it and set its status=3, i.e. (processed state)
- Step5: Queue all the neighbors of N that are in the ready state (status=1) and set their status =2 (waiting state)
- Step6: Exit

#### Explain what is a recursive algorithm?

- A recursive algorithm is a method for solving difficult problems that involves breaking a problem down into progressively more manageable sub-problems until the original problem is reduced to the point where it can be solved without much difficulty.
- In most cases, this is accomplished by a function calling itself.

#### What is Dijkstra’s shortest path algorithm?

- The Dijkstra algorithm is an algorithm that finds the shortest path from a beginning node to a target node in a weighted graph.
- It does this by comparing the weights of the nodes in the network.
- The algorithm constructs a tree consisting of the shortest paths that may be taken from the starting vertex and the source vertex to any of the other nodes in the graph.
- Imagine you want to get from your house to your office in the least amount of time possible. Since you are aware that some roadways include heavy traffic and might be difficult to navigate, this indicates that these edges contain a significant amount of weight.
- When using Dijkstra’s algorithm, the shortest path tree that the algorithm finds will make an effort to steer clear of edges that have bigger weights.