UGRD-CS6202 Algorithms and Complexity Prelim to Finals Perfect PDF

Preview

Summary

Characteristics to meet the measurement of an algorithm. The function defined by the maximum number of steps taken on any instance of size a. worst caseThe function defined by the minimum number of steps taken on any instance of size a. best caseLists of common computing times of algorithms in order...

Description

Characteristics to meet the measurement of an algorithm. The function defined by the maximum number of steps taken on any instance of size a. worst case The function defined by the minimum number of steps taken on any instance of size a. best case Lists of common computing times of algorithms in order of performance : It occurs when the runtime grows in proportion with the size of the input data set. n is the size of the input data set. O(n) - Linear Runtime It denotes an algorithm whose runtime is directly proportional to the square of the size of the input data set. O(n2 ) - Quadratic Runtime The runtime of the algorithm depends on running a logarithm operation n times. O(n log n) - Linearithmic runtime The runtime it takes for the algorithm to run will plateau no matter the size of the input data set. O(log n) - Logarithmic runtime Algorithm analysis is an important part of computational complexities that provides the theoretical estimates for the resources needed by an algorithm to solve any computational task. True The process of determining a formula for total time required towards the execution of the algorithm. time complexity An algorithm is a finite set of instructions, those if followed, accomplishes a particular task. True The complexity of an algorithm can be divided into two types. The blank complexity and the blank complexity. time, space It computes the amount of time and spaces required by an algorithm for an input of size No. Complexity of an Algorithm

Types of complexity: worst-case complexity, average‑‑case complexity blank is a metric used to find algorithm complexity and signifies the relationship between the input to the algorithm and the steps required to execute the algorithm. Big-O notation The criteria of an algorithm : Each instruction is clear and unambiguous. Definiteness Each instruction must be very basic, so the purpose of those instructions must be very clear to us. Effectiveness Zero or more inputs are externally supplied to the algorithm. Input At least one output is produced by an algorithm. Output In an algorithm, it will be terminated after a finite number of steps for all different cases. Finiteness It runs the same time, regardless of the given input data set. O(1) - Constant Runtime Since the scratch tapes receive the same number of records, this is a ______________ balanced multiway merge Merging refers to the operation or technique of arranging and rearranging sets of data in some specific order. False It is used to arrange N elements in ascending order, and have to begin with 0th element and compare it with the first element. If the 0th element is found greater than the 1st element, then the swapping operation will be performed is called bubble sort Categories of an algorithm:

When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, External Sorting If all the data that is to be sorted can be adjusted at a time in the main memory, t Internal Sorting blank is a sorting technique and has an algorithm that has a reasonably proficient space-time complexity - O(n log n) and is quite trivial to apply. merge sort Which of the following is a stable sorting algorithm? Merge sort How Quick Sorting Works? Following are the steps involved in quick sort algorithm: After selecting an element as pivot, which is the last index of the array in our case, we divide the array for the first time. In quick sort, we call this partitioning. It is not simple breaking down of array into 2 subarrays, but in case of partitioning, the array elements are so positioned that all the elements smaller than the blank will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it. And the pivot element will be at its final sorted position. The elements to the left and right, may not be sorted. Then we pick subarrays, elements on the left of pivot and elements on the right of pivot, and we perform blank on them by choosing a pivot in the subarrays. pivot, partitioning The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version? 2 A collection of records called a blank where every record has one or more fields. list In external sorting, the number of runs that can be merged in every pass are called ___________. degree of merging The complexity of sorting algorithm calculates the running time of a function in which 'n' number of items are to be sorted. False

Heap is a special tree-based data structure, that satisfies the following special heap properties: if the parent nodes are smaller than their child nodes, heap is called ____________. min-Heap If the parent nodes are greater than their child nodes, heap is called ___________ max-heap Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general? Selection sort Procedure of sorting the algorithms for larger records that does not fit in the main memory and are stored on disk is classified as ____________ external sorting Which of the following is not a non-comparison sort? Shell sort Quick Sort is also based on the concept of blank , just like merge sort. Divide and Conquer What is the worst case complexity of bubble sort? O(n2) Finding A Safe Edge: Every 2 disjoint subsets of vertices must be connected by at least _____. one edge A cut (S,V-S) is a partition of vertices into ________ sets S and V-S. disjoint Edge (u,v)ÎE crosses cut (S, V-S) if one __________ is in S and the other is in V-S. endpoint An edge is a light edge crossing a cut iff its weight is minimum over all edges_______ the cut. crossing Child node in a binary tree on the left is termed as blank and node in the right is termed as the blank .

left child node, right child node is a more efficient search algorithm which relies on the elements in the list being sorted. Binary Search A binary tree is a special type of tree in which every node or vertex has either no child node or one child node or two child nodes. True Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character. Huffman's algorithm A blank which is also called as proper binary tree or 2-tree is a tree in which all the node other than the leaves has exact two children. full binary tree blank is the most basic kind of search method. It involves checking each element of the list in turn, until the desired element is found. Linear search False A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. True A full binary tree which is also called as blank or 2-tree is a tree in which all the node other than the blank has exact two children. proper binary tree, leaves Searching algorithms that perform this task: It requires a sorted input list, and checks for the value in the middle of the list, repeatedly discarding the half of the list which contains values which are definitely either all larger or all smaller than the desired value. binary search It simply checks the values in sequence until the desired value is found. linear search In the figure below, the blank node 8 has two children 3 and 10; then this two child node again acts as a blank node for 1 and 6 for left parent node 3 and 14 for right parent node 10. Similarly, 6 and 14 has a blank node. root, parent, child

Build one tree A ; Start from arbitrary root r, at each step, add light edge connecting VA to V- VA (greedy). Prim's algorithm A ______________ can be converted into an extended binary tree by adding new nodes to its leaf nodes and to the nodes that have only one child. T binary tree An optimization problem is the problem of finding the best solution from all feasible solutions True Steps to print codes from Huffman Tree: Traverse the tree formed starting from the blank . Maintain an auxiliary array. While moving to the left child, write 0 to the blank . While moving to the blank , write 1 to the array. Print the array when a leaf node is encountered. root, array, right child Starts with each vertex being its own component. It repeatedly merges two components into one by choosing the light edge that crosses the cut between them. Kruskal's algorithm It maintains a set S of vertices whose final shortest - path weights from the source s have already been determined. That's for all vertices v ∈ S; we have d [v] = δ (s, v). Dijkstra's Algorithm A complete binary tree is a binary tree in which at every level, except possibly the last, has to be filled and all nodes are as far left as possible. True Quick Sort is also based on the concept of blank , just like merge sort. But in quick sort all the heavy lifting (major work) is done while dividing the array into subarrays, while in case of merge sort, all the real work happens during merging the blank . Divide and Conquer, subarrays Pattern Matching works by " blank " through text strings to match patterns that are defined using Pattern Matching Expressions, also known as blank . The behavior for blank characters is overridden by the behavior assigned to the same character(s) under Regular Expression Reference. reading, regular expressions, wildcard String Matching Preliminaries

An instance of the pattern within the text. Target The string that we seek Pattern The longer string in which we are searching for the pattern. Text Components of KMP Algorithm: A pattern encapsulates knowledge about how the pattern matches against the shift of itself. Prefix Function (Π) With string 'S,' pattern 'p' and prefix function 'Π' as inputs, find the occurrence of 'p' in 'S' and returns the number of shifts of 'p' after which occurrences are found. KMP Matcher Computers generate random number for everything from blank to video games and blank . There are two categories of random numbers — “true” random numbers and pseudorandom numbers — and the difference is important for the security of encryption systems. cryptography, gambling PRNGs are suitable for applications where many random numbers are required and where it is useful that the same sequence can be replayed easily. True A good suffix is a suffix that has matched successfully. True Pseudo Random Number Generator (PRNG) refers to an algorithm that uses mathematical formulas to produce sequences of random numbers. True It refers to a programming style that does not include any shortcuts to improve performance, but instead relies on sheer computing power to try all possibilities until the solution to a problem is found. Brute Force Algorithms Characteristics of PRNG :

A given sequence of numbers can be reproduced at a later date if the starting point in the sequence is known. Deterministic It means that the sequence will eventually repeat itself. Periodic PRNG can produce many numbers in a short time and is advantageous for applications that need many numbers. Efficient Pattern matching in computer science is the checking and locating of specific sequences of data of some pattern among raw data or a sequence of tokens. True The __________ takes a 'backward' approach: the pattern string (P) is aligned with the start of the text string (T), and then compare the characters of a pattern from right to left, beginning with the rightmost character. Boyer-Moore algorithm characteristic of PRNG wherein a given sequence of numbers can be reproduced at a later date if the starting point in the sequence is known. deterministic blank is most common and oldest algorithm for generating blank numbers. The generator is defined by the recurrence relation: Linear Congruential Generator, pseudo-randomized Robert Boyer and J Strother Moore established the BM algorithm in blank . 1977 A blank approximation of the function locally sometimes work much better than using the blank value like the rectangular rule does. linear, average By sampling in time, we get a periodic spectrum with the sampling blank fs. The approximation of a blank transform by a DFT is reasonable only if the frequency components of x(t) are concentrated on a blank than the Nyquist frequency fs/2 frequency, Fourier, smaller range In mathematics, a function that results when a given function is multiplied by a socalled blank , and the product is integrated between suitable limits. kernel function

Time Domain: Tells us how properties (air pressure in a sound function, for example) change over time True The rectangular rule can be made more accurate by using blank to replace the rectangles as shown. trapezoids A numerical integration is the approximation of a definite integration by a “weighted” sum of function values at discretized points within the interval of integration. True of an image refers to the rate at which the pixel intensities change. Spatial frequency Property of Transform: Tells us how properties (amplitudes) change over frequencies. frequency domain Tells us how properties (air pressure in a sound function, change over time. time domain In 1807, blank showed that any periodic blank could be represented by a series of sinusoidal blank . Jean Baptiste Joseph Fourier, signal, functions In 1907, Jean Baptiste Joseph Fourier showed that any periodic signal could be represented by a series of sinusoidal False Human ears hear wave-like oscilations, but constant tone. False Directed Acyclic Graphs are called DAGs The degree of a Answer is the number of arcs incident to it node A path from one node to itself is called a cycle A graph need not be a tree but a tree must be a graph.

True A number may be associated with each arc of a graph. Such graph is called blank or network. The number associated with an arc is called the blank . weighted graph, weight A node n is incident to an arc x is one of the two nodes in the ordered pair of nodes constituting x. We also say that x is incident to n. The number of arcs with n as the head. indegree of n The number of arcs with n as the tail outdegree of n The _________ is the number of arcs incident to it. degree of a node A graph consists of s set of nodes or blank and a set of arcs or blank vertices, edges If the pair of nodes that make up the arcs are ordered pair then the graph is a directed graph or dig graph. True Operations used with graphs : Adds an arc from node a to b join (a,b) Removes an arc from a to b if it exists. remove (a, b) Adds an arc from a to b with weight x joinwt (a,b,x) Removes an arc from a to b and sets x to the weight of defunct arc. removewt (a,b,x)...