Algorithms are The Heart Of Computer Science, And The Subject Has Countless Practical Applications As Well As Intellectual Depth. This Specialization Is An Introduction To Algorithms For Learners With At Least A Little Programming Experience.
1.Define the concept of an algorithm.
An algorithm is any well-defined computational procedure that takes some value (or set of values) as inputand produces some value (or set of values) as output. In short, it can be seen as a sequence ofcomputational steps that transform the input into the output.
2.What are the arguments present in pattern matching algorithms?
These are the following arguments which are present in pattern matching Algorithms.1) Subject,2) Pattern3) Cursor4) MATCH_STR5) REPLACE_STR6) REPLACE_FLAG
3.Explain the function SUB in algorithmic notation?
In the algorithmic notation rather than using special marker symbols, generally people use the cursor positionplus a substring length to isolate a substring. The name of the function is SUB.SUB returns a value the sub string of SUBJECT that is specified by the parameters i and j and an assumedvalue of j.
4.In Algorithmic context how would you define book keeping operations?
Usually when a user wants to estimate time he isolates the specific function and brands it as active operation.The other operations in the algorithm, the assignments, the manipulations of the index and the accessing of avalue in the vector, occur no more often than the addition of vector values. These operations are collectivelycalled as ?book keeping operations?
5.Define and describe an iterative process with general steps of flow chart?
There are four parts in the iterative process they areInitialization: -The decision parameter is used to determine when to exit from the loop.Decision: -The decision parameter is used to determine whether to remain in the loop or not.Computation: - The required computation is performed in this part.Update: - The decision parameter is updated and a transfer to the next iteration results.
6.State recursion and its different types?
Recursion is the name given to the technique of defining a set or a process in terms of itself. There areessentially two types of recursion. The first type concerns recursively defined function and the second typeof recursion is the recursive use of a procedure.
7.Define and state the importance of sub algorithm in computation and its relation ship with main algorithm?
A sub algorithm is an independent component of an algorithm and for this reason is defined separatelyfrom the main algorithm. The purpose of a sub algorithm is to perform some computation when required,under control of the main algorithm. This computation may be performed on zero or more parameterspassed by the calling routine.
8.Name any three skills which are very important in order to work with generating functions.
The three most important skills which are used extensively while working with generating functions are1)Manipulate summation expressions and their indices.2)Solve algebraic equations and manipulate algebraic expressions, including partial functiondecompositions.3)Identify sequences with their generating functions
9.What is the general strategy for Markov Algorithm?
The general strategy in a Markov Algorithm is to take as input a string x and, through a number of steps inthe algorithm, transform x to an output string y. this transformation process is generally performed incomputers for text editing or program compilation.
10.Define string in an algorithmic notation and an example to support it?
In the algorithmic notation, a string is expressed as any sequence of characters enclosed in single quotemarks.
11.How to find median of a BST?
Find the no. of elements on the left side.If it is n-1 the root is the median.If it is more than n-1, then it has already been found in the left subtree.Else it should be in the right subtree
12.What is Diffie-Hellman?
It is a method by which a key can be securely shared by two users without any actual exchange.
13.What is the goal of the shortest distance algorithm?
The goal is completely fill the distance array so that for each vertex v, the value of distance[v] is theweight of the shortest path from start to v.
14.Explain the depth of recursion?
This is another recursion procedure which is the number of times the procedure is called recursively in theprocess of enlarging a given argument or arguments. Usually this quantity is not obvious except in the caseof extremely simple recursive functions, such as FACTORIAL (N), for which the depth is N.
15.Explain about the algorithm ORD_WORDS?
This algorithm constructs the vectors TITLE, KEYWORD and T_INDEX.
16.Which are the sorting algorithms categories?
Sorting algorithms can be divided into five categories:a) insertion sortsb) exchange sortsc) selection sortsd) merge sortse) distribution sorts
17.17.Define a brute-force algorithm. Give a short example.
A brute force algorithm is a type of algorithm that proceeds in a simple and obvious way, but requires ahuge number of steps to complete. As an example, if you want to find out the factors of a given number N,using this sort of algorithm will require to get one by one all the possible number combinations.
18.What is a greedy algorithm? Give examples of problems solved using greedy algorithms.
A greedy algorithm is any algorithm that makes the local optimal choice at each stage with the hope offinding the global optimum. A classical problem which can be solved using a greedy strategy is thetraveling salesman problem. Another problems that can be solved using greedy algorithms are the graphcoloring problem and all the NP-complete problems.
19.What is a backtracking algorithm? Provide several examples.
It is an algorithm that considers systematically all possible outcomes for each decision. Examples ofbacktracking algorithms are the eight queens problem or generating permutations of a given sequence.
20.What is the difference between a backtracking algorithm and a brute-force one?
Due to the fact that a backtracking algorithm takes all the possible outcomes for a decision, it is similarfrom this point of view with the brute force algorithm. The difference consists in the fact that sometimes abacktracking algorithm can detect that an exhaustive search is unnecessary and, therefore, it can performmuch better.
21.Describe divide and conquer paradigm.
When a problem is solved using a divide and conquer algorithm, it is subdivided into one or more subproblems which are all similar to the original problem in such a way that each of the sub problems can besolved independently. In the end, the solutions to the sub problems are combined in order to obtain thesolution to the original problem.
22.Describe on short an insertion sorting algorithm.
An algorithm that sorts by insertion takes the initial, unsorted sequence and computes a series of sortedsequences using the following rules:a) the first sequence in the series is the empty sequenceb) given a sequence S(i) in the series, for 0<=i<="" p="" style="box-sizing: border-box;">
23.Which are the advantages provided by insertion sort?
Insertion sort provides several advantages:a) simple implementationb) efficient for small data setsc) adaptive - efficient for data sets that are already substantially sorted: the time complexity is O(n + d),where d is the number of inversionsd) more efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sortor bubble sort; the best case (nearly sorted input) is O(n)e) stable - does not change the relative order of elements with equal keysf) in-place - only requires a constant amount O( 1) of additional memory spaceg) online - can sort a list as it receives it
24.Shortly describe the quicksort algorithm.
In quicksort, the steps performed are the following:a) pick an element, called a pivot, from the listb) reorder the list so that all elements with values less than the pivot come before the pivot, while allelements with values greater than the pivot come after it (equal values can go either way)c) recursively sort the sub-list of lesser elements and the sub-list of greater elements.
25.What is the difference between selection and insertion sorting?
In insertion sorting elements are added to the sorted sequence in an arbitrary order. In selection sorting, theelements are added to the sorted sequence in order so they are always added at one end.
26.What is merge sorting?
Merging is the sorting algorithm which combines two or more sorted sequences into a single sortedsequence. It is a divide and conquer algorithm, an O(n log n) comparison-based sorting algorithm. Mostimplementations produce a stable sort, meaning that the implementation preserves the input order of equalelements in the sorted output.
27.Which are the main steps of a merge sorting algorithm?
Sorting by merging is a recursive, divide-and-conquer strategy. The basic steps to perform are thefollowing:a) divide the sequence into two sequences of lengthb) recursively sort each of the two subsequencesc) merge the sorted subsequences to obtain the final result
28.Provide a short description of binary search algorithm.
Binary search algorithm always chooses the middle of the remaining search space, discarding one half orthe other, again depending on the comparison between the key value found at the estimated position andthe key value sought. The remaining search space is reduced to the part before or after the estimatedposition.
29.What is the linear search algorithm?
Linear search is a method for finding a particular value in a list which consists of checking every one of itselements, one at a time and in sequence, until the desired one is found. It is the simplest search algorithm, aspecial case of brute-force search. Its worst case cost is proportional to the number of elements in the list;and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list hasmore than a few elements, other methods (such as binary search or hashing) may be much more efficient.
30.What is best-first search algorithm?
It is a search algorithm that considers the estimated best partial solution next. This is typicallyimplemented with priority queues.
31.What is Huffman coding?
In computer science and information theory, Huffman coding is an entropy encoding algorithm used forlossless data compression. The term refers to the use of a variable-length code table for encoding a sourcesymbol (such as a character in a file) where the variable-length code table has been derived in a particularway based on the estimated probability of occurrence for each possible value of the source symbol.
32.What are the method available in form submitting?
GET and POST