
Algorithms FAQs Part 1.
The following are the list of most important FAQs of Algorithms and Data Structures used in most of the programming languages. To improve your
coding skills every programmer has to know the how to implement Algorithms and Data structures in his application.
1. What is an algorithm?
The process of providing solution to a problem is a sequence of steps is called an algorithm.
2. What are the properties of an algorithm?
An algorithm must possess the following properties:
a. It should get input data.
b. It should produce output.
c. The algorithm should terminate.
d. Algorithm should be clear to understand.
e. It should be easy to perform.
3. What are the types of algorithms?
Algorithms are of two types: iterative and recursive algorithms.
4. Define iterative algorithms.
Algorithms which use loops and conditions to solve the problem are called iterative algorithms.
5. Define recursive algorithms.
Algorithms which perform the recursive steps in a divide and conquer method are called recursive algorithms.
6. What is an array?
An array is a sequential collection of same kind of data elements.
7. What is a data structure?
A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.
8. Name the areas of application of data structures.
The following are the areas of application of data structures:
a. Compiler design
b. Operating system
c. Statistical analysis package
d. DBMS
e. Numerical analysis
f. Simulation
g. Artificial Intelligence
h. Graphics
9. What are the major data structures used in the following areas: Network data model, Hierarchical data model, and RDBMS?
The major data structures used in the above areas are:
Network data model – Graph
Hierarchical data model – Trees
RDBMS – Array
10. What are the types of data structures?
Data structures are of two types: Linear and non linear data structures.
11. What is a linear data structure?
If the elements of a data structure are stored sequentially, then it is a linear data structure.
12. What is non linear data structure?
If the elements of a data structure are not stored in sequential order, then it is a non linear data structure.
13. What are the types of array operations?
The following are the operations which can be performed on an array:
Insertion, Deletion, Search, Sorting, Merging, Reversing and Traversal.
14. What is a matrix?
An array of two dimensions is called a matrix.
15. What are the types of matrix operations?
The following are the types of matrix operations:
Addition, multiplication, transposition, finding determinant of square matrix, subtraction, checking whether it is singular matrix or not etc.
16. What is the condition to be checked for the multiplication of two matrices?
If matrices are to be multiplied, the number of columns of first matrix should be equal to the number of rows of second matrix.
17. Write the syntax for multiplication of matrices?Syntax:
for (=0; < value;++)
{
for (=0; < value;++)
{
for (=0; < value;++)
{
arr[var1][var2] += arr[var1][var3] * arr[var3][arr2];
}
}
}
18. What is a string?
A sequential array of characters is called a string.
19. What is use terminating null character?
Null character is used to check the end of string.
20. What is an empty string?
A string with zero character is called an empty string.
21. What are the operations that can be performed on a string?
The following are the operations that can be performed on a string:
finding the length of string, copying string, string comparison, string concatenation, finding substrings etc.
22. What is Brute Force algorithm?
Algorithm used to search the contents by comparing each element of array is called Brute Force algorithm.
23. What are the limitations of arrays?
The following are the limitations of arrays:
Arrays are of fixed size.
Data elements are stored in continuous memory locations which may not be available always.
Adding and removing of elements is problematic because of shifting the locations.
24. How can you overcome the limitations of arrays?
Limitations of arrays can be solved by using the linked list.
25. What is a linked list?
Linked list is a data structure which store same kind of data elements but not in continuous memory locations and size is not fixed. The linked lists are related logically.
26. What is the difference between an array and a linked list?
The size of an array is fixed whereas size of linked list is variable. In array the data elements are stored in continuous memory locations but in linked list it is non continuous memory locations. Addition, removal of data is easy in linked list whereas in arrays it is complicated.
27. What is a node?
The data element of a linked list is called a node.
28. What does node consist of?
Node consists of two fields:
data field to store the element and link field to store the address of the next node.
29. Write the syntax of node creation?
Syntax:
struct node
{
data type ;
node *ptr; //pointer for link node
}temp;
30. Write the syntax for pointing to next node?Syntax:
node->link=node1;
32. What is a data structure? What are the types of data structures? Briefly explain them
The scheme of organizing related information is known as ‘data structure’. The types of data structure are:
Lists: A group of similar items with connectivity to the previous or/and next data items.
Arrays: A set of homogeneous values
Records: A set of fields, where each field consists of data belongs to one data type.
Trees: A data structure where the data is organized in a hierarchical structure. This type of data structure follows the sorted order of insertion, deletion and modification of data items.
Tables: Data is persisted in the form of rows and columns. These are similar to records, where the result or manipulation of data is reflected for the whole table.
33. Define a linear and non linear data structure.
Linear data structure: A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Ex: Arrays, Linked Lists
Non-Linear data structure: Every data item is attached to several other data items in a way that is specific for reflecting relationships. The data items are not arranged in a sequential structure. Ex: Trees, Graphs
34. Define in brief an array. What are the types of array operations?
An array is a set of homogeneous elements. Every element is referred by an index.
Arrays are used for storing the data until the application expires in the main memory of the computer system. So that, the elements can be accessed at any time. The operations are:
– Adding elements
– Sorting elements
– Searching elements
– Re-arranging the elements
– Performing matrix operations
– Pre-fix and post-fix operations
35. What is a matrix? Explain its uses with an example
A matrix is a representation of certain rows and columns, to persist homogeneous data. It can also be called as double-dimensioned array.
Uses:
– To represent class hierarchy using Boolean square matrix
– For data encryption and decryption
– To represent traffic flow and plumbing in a network
– To implement graph theory of node representation
36. Define an algorithm. What are the properties of an algorithm? What are the types of algorithms?
Algorithm: A step by step process to get the solution for a well defined problem.
Properties of an algorithm:
– Should be unambiguous, precise and lucid
– Should provide the correct solutions
– Should have an end point
– The output statements should follow input, process instructions
– The initial statements should be of input statements
– Should have finite number of steps
– Every statement should be definitive
37. Types of algorithms:
– Simple recursive algorithms. Ex: Searching an element in a list
– Backtracking algorithms Ex: Depth-first recursive search in a tree
– Divide and conquer algorithms. Ex: Quick sort and merge sort
– Dynamic programming algorithms. Ex: Generation of Fibonacci series
– Greedy algorithms Ex: Counting currency
– Branch and bound algorithms. Ex: Travelling salesman (visiting each city once and minimize the total distance travelled)
– Brute force algorithms. Ex: Finding the best path for a travelling salesman
– Randomized algorithms. Ex. Using a random number to choose a pivot in quick sort).
38. What is an iterative algorithm?
The process of attempting for solving a problem which finds successive approximations for solution, starting from an initial guess. The result of repeated calculations is a sequence of approximate values for the quantities of interest.
39. What is an recursive algorithm?
Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repetition is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.
40. Explain quick sort and merge sort algorithms.
Quick sort employs the ‘divide and conquer’ concept by dividing the list of elements into two sub elements.
The process is as follows:
1. Select an element, pivot, from the list.
2. Rearrange the elements in the list, so that all elements those are less than the pivot are arranged before the pivot and all elements those are greater than the pivot are arranged after the pivot. Now the pivot is in its position.
3. Sort the both sub lists – sub list of the elements which are less than the pivot and the list of elements which are more than the pivot recursively.
41. Merge Sort: A comparison based sorting algorithm. The input order is preserved in the sorted output.
Merge Sort algorithm is as follows:
1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Otherwise divide the unsorted list into two lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, merge both the lists back into one sorted list.
42. What is Bubble Sort and Quick sort?
Bubble Sort: The simplest sorting algorithm. It involves the sorting the list in a repetitive fashion. It compares two adjacent elements in the list, and swaps them if they are not in the designated order. It continues until there are no swaps needed. This is the signal for the list that is sorted. It is also called as comparison sort as it uses comparisons.
Quick Sort: The best sorting algorithm which implements the ‘divide and conquer’ concept. It first divides the list into two parts by picking an element a ‘pivot’. It then arranges the elements those are smaller than pivot into one sub list and the elements those are greater than pivot into one sub list by keeping the pivot in its original place.
43. What are the difference between a stack and a Queue?
Stack – Represents the collection of elements in Last In First Out order.
Operations includes testing null stack, finding the top element in the stack, removal of top most element and adding elements on the top of the stack.
Queue – Represents the collection of elements in First In First Out order.
Operations include testing null queue, finding the next element, removal of elements and inserting the elements from the queue.
Insertion of elements is at the end of the queue
Deletion of elements is from the beginning of the queue.
44. Can a stack be described as a pointer? Explain.
A stack is represented as a pointer. The reason is that, it has a head pointer which points to the top of the stack. The stack operations are performed using the head pointer. Hence, the stack can be described as a pointer.
45. Explain the terms Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion.
Base case: A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.
Recursive Case: A case which returns to the answer which is closer.
Run-time Stack: A run time stack used for saving the frame stack of a function when every recursion or every call occurs.
Tail Recursion: It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.
46. Is it possible to insert different type of elements in a stack? How?
Different elements can be inserted into a stack. This is possible by implementing union / structure data type. It is efficient to use union rather than structure, as only one item’s memory is used at a time.
47. Explain in brief a linked list.
A linked list is a dynamic data structure. It consists of a sequence of data elements and a reference to the next element in the sequence. Stacks, queues, hash tables, linear equations, prefix and post fix operations. The order of linked items is different that of arrays. The insertion or deletion operations are constant in number.
48. Explain the types of linked lists.
The types of linked lists are:
Singly linked list: It has only head part and corresponding references to the next nodes.
Doubly linked list: A linked list which both has head and tail parts, thus allowing the traversal in bi-directional fashion. Except the first node, the head node refers to the previous node.
Circular linked list: A linked list whose last node has reference to the first node.
49. How would you sort a linked list?
Step 1: Compare the current node in the unsorted list with every element in the rest of the list. If the current element is more than any other element go to step 2 otherwise go to step 3.
Step 2: Position the element with higher value after the position of the current element. Compare the next element. Go to step1 if an element exists, else stop the process.
Step 3: If the list is already in sorted order, insert the current node at the end of the list. Compare the next element, if any and go to step 1 or quit.
50. What is sequential search? What is the average number of comparisons in a sequential search?
Sequential search: Searching an element in an array, the search starts from the first element till the last element.
The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array. If the element is in the 1st position, the number of comparisons will be 1 and if the element is in the last position, the number of comparisons will be N.
51. What are binary search and Fibonacci search?
Binary Search: Binary search is the process of locating an element in a sorted list. The search starts by dividing the list into two parts. The algorithm compares the median value. If the search element is less than the median value, the top list only will be searched, after finding the middle element of that list. The process continues until the element is found or the search in the top list is completed. The same process is continued for the bottom list, until the element is found or the search in the bottom list is completed. If an element is found that must be the median value.
52. Define Fibonacci Search: Fibonacci search is a process of searching a sorted array by utilising divide and conquer algorithm. Fibonacci search examines locations whose addresses have lower dispersion. When the search element has non-uniform access memory storage, the Fibonacci search algorithm reduces the average time needed for accessing a storage location.