Viva CS702 Advanced Algorithms Analysis and Design (Lecture1-30)
Q. What is Model of Computation?
• We supposed our model to be an abstraction of a standard generic single-processor machine, called a random access machine RAM, an idealized machine infinitely large random-access memory, instructions execute sequentially
• Every instruction is in fact a basic operation on two values in machine’s memory which takes unit time
Q. What are the drawbacks in Model of Computation?
We assumed each basic operation takes constant time i.e. adding, multiplying; comparing etc. of two numbers of any lengths in constants time but it’s not true.
Q. What is the sequence of Mathematical Tools?
A Sequence of Mathematical Tools
1. Sets 5. Relation
2. Sequences 6. Functions
3. Order pairs 7. Operators over above structures
4. Cross Product
Q. What are the Logic and Proving Techniques?
1. Propositional Logic 2. Predicate Logic
a. Truth Tables d. Contradiction
b. Logical Equivalences e. Rule of Inference
c. Counter Example
Q. What is the Mathematical Way of Expressing Induction?
• Basis step.
Show that proposition P(1) is true.
• Inductive step.
Show that for every positive integer n, the implication P(n) ⟶ P(n+1) is true.
P(n) for a fixed n is called inductive hypothesis.
• [P(1) ∧ ∀ n, (P(n) ⟶ P(n+1))] ⟶ ∀n, P(n)
Q. Define Well Ordering Principle?
Every nonempty set of positive integers contains a least element
Q. What is Fibonacci sequence?
The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it. Starting with 0 and 1, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so forth. Written as a rule, the expression is Xn = Xn-1 + Xn-2.
Q.What is Asymptotic Notations?
Asymptotic Notations are languages that allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases. This is also known as an algorithm’s growth rate.
Q.What is Big-Oh Notation (O)?
Intuitively: Set of all functions whose rate of growth is the same as or lower than that of g(n).
Q.What is Big-Omega Notation (𝛀)?
Intuitively: Set of all functions whose rate of growth is the same as or higher than that of g(n).
Q.What is Theeta Notation (𝚯)?
Intuitively: Set of all functions that have same rate of growth as g(n).
Q.What are the Relations over Asymptotic Notations?
• All the relations, 𝚯, 𝛀, O, are reflexive
• Small o and small omega are not reflexive relations
• 𝚯 is symmetric.
• Big O, big omega 𝛀, little o, and little omega 𝜔, do not satisfy the symmetry property.
• All complexity measuring notations 𝚯, 𝛀, O, 𝜔 and o satisfy the transitive property.
Q.What is algorithm?
A computer algorithm is a detailed step-by-step method for solving a problem by using a computer.
An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.
An Algorithm is well defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output.
More generally, an Algorithm is any well defined computational procedure that takes collection of elements as input and produces a collection of elements as output.
Popular Algorithms, Factors of Dependence
• Most basic and popular algorithms are
– Sorting algorithms – Searching algorithms
Q.Which algorithm is best?
• Mainly, it depends upon various factors, for example in case of sorting
– The number of items to be sorted
– The extent to which the items are already sorted
– Possible restrictions on the item values
– The kind of storage device to be used etc.
Q.What is Brute Force approach?
In brute force we go through all possible solution and find out the best one.
A very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.
• Checking primarily
• Sorting sequence of numbers
• Knapsack problem
• Closest pair in 2-D, 3-D and n-D
• Finding maximal points in n-D
Q.What are important Designing Techniques / 8 Designing Techniques
1- Brute Force
– Straightforward, naive approach
– Mostly expensive
– Divide into smaller sub-problems
3- Iterative Improvement:
– Improve one change at a time
– Decrease instance size
5- Transform-and-Conquer: – Modify problem first and then solve it
6- Space and Time Tradeoffs: – Use more space now to save time later
7- Greedy Approach
– Locally optimal decisions cannot change once made.
– Easy to implement
– The solution is expected to be optimal
– Every problem may not have greedy solution
8- Dynamic Programming
– Decompose into sub-problems like divide and conquer
– Sub-problems are dependant
– Record results of smaller sub-problems
– Re-use it for further occurrence
– Mostly reduces complexity exponential to polynomial
Q.What are the drawbacks in Model of Computation
First poor assumption
• We assumed that each basic operation takes constant time, i.e. model allows
– Adding – Multiplying – Comparing etc.
• Two number of any length in constant time
• Addition of two numbers takes a unit time!
– Not good because numbers may be arbitrarily
• Addition and multiplication both take unit time!
– Again very bad assumption
Q. How many distinct subsets does a finite set on n elements have?
There are 2n subsets.
Q. What is Rule of Inference?
A rule of inference is a general pattern that allows us to draw some new conclusion from a set of given statements. If we know P then we can conclude Q.
Q. What is Mathematical Induction?
• Mathematical induction is a powerful, yet straight-forward method of proving statements whose domain is a subset of the set of integers.
Q. What are applications of Fibonacci Sequences?
• Are used in trend analysis
• By some pseudorandom number generators
• The number of petals is a Fibonacci number.
• Many plants show the Fibonacci numbers in the arrangements of the leaves around the stems.
• Seen in arrangement of seeds on flower heads
Q. What is Recursion?
The idea behind recursion
• A problem can be broken down into sub-problems and find a way to solve these sub-problems
• Then build up to a solution to the entire problem.
• Recursion is a wonderful technique for dealing with many problems where problems and sub-problems have same mechanism to solve it.
• Recursive algorithms break down problem in pieces which is either already know the answer, or can be solved applying same algorithm to each piece
• And finally combine the results of these sub-problems to find the final solution
• More concisely, a recursive function or definition is defined in terms of itself.
• Recursion is a computer algorithm that calls itself in a step having a termination condition.
Q. What are merits and demerits of Recursion?
• Recursive solutions are much easier to conceive of and code than their iterative counterparts.
• Every problem is not solvable using this approach
Q. What is Complexity?
The level in difficulty in solving mathematically posed problems as measured by
– The time (time complexity)
– Number of steps or arithmetic operations (computational complexity)
– Memory space required (space complexity)
Q. What is Greedy Algorithm?
An algorithm making the locally optimal choice at each stage with the hope of finding a global optimum solution. OR
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
Q. Where Greedy Algorithms do not work?
Find longest monotonically increasing subsequence
Q. What are the steps Designing Greedy Algorithms
1. Determine the suboptimal structure of the problem.
2. Develop a recursive solution.
3. Prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice.
4. Show that all but one of the sub-problems induced by having made the greedy choice are empty.
5. Develop a recursive algorithm that implements the greedy strategy.
6. Convert this recursive algorithm to an iterative one.
Q. What are the steps of Divide and Conquer
Step 1:• If the problem size is small, solve this problem directly
• Otherwise, split the original problem into 2 or more sub-problems with almost equal sizes.
Step 2: • Recursively solves these sub-problems by applying this algorithm.
Step 3: • Merge the solutions of the sub- problems into a solution of the original problem.
Examples of Divide and Conquer: Binary Search, Quick Sort and Merge sort.
Q. What is Dynamic Programming?
Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions
Q. What is big-O notation?
Use to check how much time an algorithm will take in the worst case scenario.
Q. What is Time Complexity?
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms.
Q. What is Space Complexity?
How much space in the memory an algorithm takes to perform a specific function.
Q. Difference between Divide and Conquer and Dynamic Programming
Dynamic programming: it is like divide and conquer method, solves problems by combining the solutions to sub-problems.
Divide and Conquer Algorithms:
• Partition the problem into independent sub-problem
• Solve the sub-problem recursively and
• Combine their solutions to solve the original problem
• Decompose into sub-problems like divide and conquer
– Sub-problems are dependant
• is applicable when the sub-problems are not independent.
• Dynamic programming is typically applied to optimization problems.
Q. What is Knapsack?
An algorithm in which we select the objects with more value and less weight. We have to select under the given weight limit.
Q. What is 0-1 Knapsack problem?
Each item must be put entirely in the knapsack or not included at all that is why the problem is called 0-1 knapsack problem.
Q. What is a Subsequence?
In mathematics, a subsequence of some sequence is a new sequence which is formed from original one by deleting some elements without disturbing the relative positions of the remaining elements.
Q. What is Longest Common Subsequence (LCS)?
This LCS problem can be solved using brute force approach as well but using dynamic programming it will be solved more efficiently.
Q. What is a Binary Search Tree (BST)?
A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left sub-tree and smaller than the keys in all nodes in that node’s right sub-tree.
Q. What are the limitations of Dynamic Programming
• Dynamic programming can be applied to any problem that observes the principle of optimality.
• Generally, it means that partial solutions can be optimally extended with regard to the state after the partial solution instead of the partial solution itself.
• The biggest limitation using dynamic programming is number of partial solutions we must keep track of
Q. What is Backtracking algorithm?
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems.
Q. Which sorting algorithm is Divide and Conquer?
Both Merge Sort and Quick Sort employ a common algorithmic paradigm based on recursion. This paradigm, divide-and-conquer, breaks a problem into sub problems that are similar to the original problem, recursively solves the sub problems, and finally combines the solutions to the sub problems to solve the original problem.
Q. What is Plane Sweep Algorithm?
It is an algorithmic paradigm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space.
Q. What is Merge Sort?
Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms. Merge sort first divides the array into equal halves and then combines them in a sorted manner.
Q. What is Divide and Conquer Algorithm?
A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
Q. What is Spanning Tree?
A spanning tree for a graph G is a sub-graph of G that contains every vertex of G and is a tree.
Q. Why BFS and DFS are used?
BFS and DFS are graph search algorithms that can be used for a variety of different purposes. One common application of the two search techniques is to identify all nodes that are reachable from a given starting node. … DFS is often used as a subroutine in more complex algorithms.