# DSA 2019

## Group A

1. A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commonly called the “front
2. Big-O notation is the language we use for talking about how long an algorithm takes to run (time complexity) or how much memory is used by an algorithm (space complexity). Big-O notation can express the best, worst, and average-case running time of an algorithm.
3. Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.
4. The skip list is a probabilisitc data structure that is built upon the general idea of a linked The skip list uses probability to build subsequent layers of linked lists upon an original linked list. Each additional layer of links contains fewer elements, but no new elements.
5. B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red-Black Trees).
6. The breadth first traversal visits and processes nodes at every level before moving on to the next
7. linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. … In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
8. The main advantage of using binary search is that it does not scan each element in the list. Instead of scanning each element, it performs the searching to the half of the list. So, the binary search takes less time to search an element as compared to a linear searc
9. In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
10. AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

## Q.no 13 ## Q.no 15

The topological sorting for a directed acyclic graph is the linear ordering of vertices. For every edge U-V of a directed graph, the vertex u will come before vertex v in the ordering. Topological sorting is only possible on DAG. Eg: 