Free Essay

Algorithms

In: Other Topics

Submitted By dnmboy
Words 1331
Pages 6
18 DE NOVIEMBRE DE 2015

KNUTH-MORRIS-PRATT
3CV2

RAMIREZ AGUILAR ABIGAIL ADORAIM
RODRIGUEZ TORRES GERARDO
NAVA MARTINEZ DANIEL
GUZMÁN MUÑOZ MIGUEL ANGEL
Prof: Daniel Cruz García

Contenido
¿Qué es? ........................................................................................................................................ 2
¿Para qué sirve?............................................................................................................................. 2
¿Cómo se utiliza? ........................................................................................................................... 2
Teoría del algoritmo....................................................................................................................... 4
Definición formal e informal....................................................................................................... 4
Variantes del algoritmo .............................................................................................................. 5
Complejidad del algoritmo ......................................................................................................... 7
Aplicaciones del algoritmo ............................................................................................................. 8
Implementación del algoritmo ....................................................................................................... 9
Código: ...................................................................................................................................... 9
Pantalla de Ejecución ................................................................................................................... 13
Conclusiones................................................................................................................................ 13
Bibliografía .................................................................................................................................. 14

¿Qué es?
El algoritmo Knurris-Morris-Patt es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. El algoritmo originalmente fue elaborado por Donald Knuth y Vaughan Pratt y de modo independiente por
James H. Morris en 1977, pero lo publicaron juntos los tres.
Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se precalcula una tabla de valores), para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.
El algoritmo KMP, trata de localizar la posición de comienzo de una cadena, dentro de otra. Antes que nada con la cadena a localizar se precalcula una tabla de saltos (conocida como tabla de fallos) que después al examinar entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo. [1]

¿Para qué sirve?
El algoritmo de Knutt-Morris-Patt nos sirve principalmente para:


Buscar la existencia de una subcadena dentro de una cadena.



Búsqueda de Patrones.



Búsqueda de un patrón dentro de una cadena de caracteres. [2]

¿Cómo se utiliza?
Una forma de entender correctamente el funcionamiento del algoritmo es seguir paso a paso un ejemplo reseñando en cada punto lo que hace o puede hacer el algoritmo en una situación dada. t ={CTCACTGCCTGCCTAG} y un patrón p = {CTGCCTAG}, y el patrón p se encuentra dentro de t a partir de noveno símbolo. Entonces, como antes, podemos decir que el patrón se encuentra en t con un desplazamiento s = 8.
En el KMP, primero de todo se calcula la next table para el patrón. Para el patrón p = {CTGCCTAG} sería la siguiente:

A la hora de construir la next table, se asigna un valor de -1 a la posición 0 del vector de la next table y un 0 a la posición 1. El valor -1 en la posición 0 es una señal cualquiera que nos sirve para comenzar la comparación con el siguiente nucleótido de la secuencia en caso que se produzca un mismatch entre la posición 0 del vector patrón y un símbolo de la secuencia. En la posición 1 del vector de la next table se tendría que comparar el prefijo de la posición 1, formado exclusivamente por la posición 0, con el patrón antes de la posición 1. Como el prefijo, aunque es coincidente, siempre será máximo, asignaremos directamente el valor 0 a la posición 1.
Continuamos con la posición 2 del vector patrón, donde se mira el número máximo de nucleótidos coincidentes con el patrón antes de esa posición. En este caso es sencillo, ya que sólo hemos de mirar si la posición 1 (T) es igual que la posición 0 (C) del vector patrón.
Como no son iguales, el valor del vector de la next table para la posición 2 será 0. Si pasamos a la posición 3, hemos de comparar si el prefijo formado por las posiciones 1 y 2 o el formado únicamente por la 2 coinciden con el patrón des de su inicio, es decir, si el prefijo constituido por las posiciones 1 y 2 es igual a las posiciones 0 y 1 o si la posición 2 es igual que la posición 0 del patrón. En este caso, no se produce ninguna coincidencia, de manera que el valor de la next table para la posición 3 es 0. Si miramos la posición 4, tendremos que comparar los prefijos formados por las posiciones 1, 2 y 3, por las posiciones 2 y 3 o por la posición 3 con el patrón que les precede. Aquí vemos que la posición 3 es igual a la posición 0 del vector patrón, así que el valor del vector de la next table para la posición 4 es igual a 1 (el prefijo mayor en la posición 4 que coincide con el patrón está formado por un nucleótido).
Si ahora nos centramos en la posición 5, ocurre lo mismo que con la posición 4, y el prefijo mayor que coincide con el patrón es de un nucleótido, de manera que el valor de la next table para la posición 5 es 1. Cuando miramos la posición 6, tenemos diferentes prefijos: los formados por las posiciones 1, 2, 3, 4 y 5, por 2, 3, 4 y 5, por 3, 4 y 5, por 4 y 5 y por 5. En este caso, el prefijo formado por las posiciones 4 y 5 coinciden con las posiciones 0 y 1 del vector patrón, y pondremos un 2 (2 nucleótidos coincidentes) en la posición 6 del vector de la next table. Para finalizar con la next table de este patrón, miramos la última posición, la 7. Ninguno de los prefijos para esta posición coincide con el patrón. Así pues, el vector de la next table tendrá un valor de 0 en la posición 7. [3]

Teoría del algoritmo
Definición formal e informal
Dada una cadena P y un texto T se puede aprender de los errores en la secuencia para realizar menos ciclos de comparación.
Por ejemplo:
Buscando “nano” en el texto “banananobano” de la manera tradicional, donde se buscan coincidencias a partir de cada índice en T[ ].

0 1 2 3 4 5 6 7 8 9 10 11
T: b a n a n a n o b a n o i=0: X i=1: i=2: i=3: i=4: i=5: i=6: i=7: i=8: i=9: i=10:

X n a
X

n

X

n

a
X

n

o

n

X
X
X n X
X

Definiendo un traslape, para poder “aprender de los errores” y utilizarlos.
0 1 2 3 4 5 6 7 8 9 10 11
T: b a n a n a n o b a n o i=0: X i=1: i=2: i=4: i=7: i=8: i=9: i=10: X n a

n n X a n

o
X
X n X
X

Variantes del algoritmo
KMP, version 1: i=0; o=0; while (i 0 && patron[i] != patron[traslape[i + 1] - 1]) traslape[i + 1] = traslape[traslape[i + 1] - 1] + 1;
}
return traslape;

Complejidad del algoritmo
Tomando como referencia el siguiente ejecución
Operaciones basicas void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; if (x[i] == x[j]) kmpNext[i] = kmpNext[j]; else kmpNext[i] = j;
}
} void KMP(char *x, int m, char *y, int n) { int i, j, kmpNext[XSIZE];
/* Preprocessing */ preKmp(x, m, kmpNext);
/* Searching */ i = j = 0; while (j < n) { while (i > -1 && x[i] != y[j]) i = kmpNext[i]; i++; j++; if (i >= m) {
OUTPUT(j - i); i = kmpNext[i];
}
}
}

Note que el número total de veces que el ciclo interior es ejecutado es menor o igual al número de veces que se puede decrementar j, dado que f(j) Patron a buscar tabla -> tabla Fucion fallo
*/

/************************* Tabla KMP **************************/

void tabla_kmp(char W[] , signed int tabla[])
{
signed int pos = 2 ; // posicion actual donde esta tabla de fallo int cnd = 0 ; // indice del patron

tabla[0] = -1 ; tabla[1] = 0 ; //comienzo del analisis

while( pos 0 ) //se hace la verificacion que el indice sea mayor a 0
{
cnd = cnd + tabla[cnd] ; // se aumenta el indice con el numero que esta en la tabla
}

cout…...

Similar Documents

Free Essay

Sorting Algorithms

...REVIEW ON SORTING ALGORITHMS A comparative study on two sorting algorithms By Pooja Adhikari A Term Paper Submitted to the Faculty of Dr. Gene Boggess Mississippi State University In the Department of Computer Science & Engineering Mississippi State, Mississippi 04 20072 ABSTRACT Any number of practical applications in computing requires things to be in order. The performance of any computation depends upon the performance of sorting algorithms. Like all complicated problems, there are many solutions that can achieve the same results. One sort algorithm can do sorting of data faster than another. A lot of sorting algorithms has been developed to enhance the performance in terms of computational complexity, memory and other factors. This paper choose two of the sorting algorithms among them selection sort and shell sort and compares the various performance factor among them. 1. INTRODUCTION Sorting is the rearrangement of things in a list into their correct lexicographic order. A number of sorting algorithms have been developed like include heap sort , merge sort, quick sort, selection sort all of which are comparison based sort .There is another class of sorting algorithms which are non comparison based sort. This paper gives the brief introduction about sorting algorithms [2] where it discuss about the class of sorting algorithms and their running times. It mainly analyses the performance between two...

Words: 841 - Pages: 4

Free Essay

Genetic Algorithms

...Genetic Algorithm Approach to Solve the Shortest Path Problem for Road Maps Sachith Abeysundara*, Baladasan Giritharan+, Saluka Kodithuwakku◊ *Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka Email: sachith@email.com Telephone: (+94) 81 2374652 + Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka Email: bgiri@pdn.ac.lk ◊ Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka Email: salukak@pdn.ac.lk Telephone: (+94) 81 2394260 Abstract—This paper presents a new genetic algorithm approach to solve the shortest path problem for road maps. This is based on the analogy of finding the shortest possible distance between two towns or cities in a graph or a map with potential connection, which means that the path distances are always positive. Typically this is represented by a graph with each node representing a city and each edge being a path between two cities and there exist some traditional algorithms that produce solutions for the problem. A new method is found to solve the shortest path problem using GAs. The algorithm has been tested for a road map containing more than 125 cities and the experimental results guarantee to provide acceptably good solutions for the given search space. HE shortest path problem is typical in the world of combinatorial systems. This research will attempt to apply a Genetic algorithm to......

Words: 2513 - Pages: 11

Free Essay

Advanced Algorithms

...Approximation Algorithms Springer Berlin Heidelberg NewYork Barcelona Hong Kong London Milan Paris Singapore Tokyo To my parents Preface Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872–1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed conjecture that P = NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of approximation algorithms as it stands today. It is reasonable to expect the picture to change with time. The book is divided into three parts. In Part I we cover a combinatorial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected – nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly categorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving......

Words: 140657 - Pages: 563

Free Essay

Genetic Algorithm

...Classification Using Genetic Algorithm N. Suguna1, and Dr. K. Thanushkodi2 1 Professor in Computer Science and Engg, Akshaya College of Engineering and Technology, Coimbatore, Tamil Nadu, India. 2 Director, Akshaya College of Engineering and Technology, Coimbatore, Tamil Nadu, India.   Abstract k-Nearest Neighbor (KNN) is one of the most popular algorithms for pattern recognition. Many researchers have found that the KNN algorithm accomplishes very good performance in their experiments on different data sets. The traditional KNN text classification algorithm has three limitations: (i) calculation complexity due to the usage of all the training samples for classification, (ii) the performance is solely dependent on the training set, and (iii) there is no weight difference between samples. To overcome these limitations, an improved version of KNN is proposed in this paper. Genetic Algorithm (GA) is combined with KNN to improve its classification performance. Instead of considering all the training samples and taking k-neighbors, the GA is employed to take k-neighbors straightaway and then calculate the distance to classify the test samples. Before classification, initially the reduced feature set is received from a novel method based on Rough set theory hybrid with Bee Colony Optimization (BCO) as we have discussed in our earlier work. The performance is compared with the traditional KNN, CART and SVM classifiers. Keywords: k-Nearest Neighbor, Genetic Algorithm,......

Words: 3528 - Pages: 15

Free Essay

Planning Algorithm

...Module 9 Planning Version 2 CSE IIT,Kharagpur Lesson 25 Planning algorithm - II Version 2 CSE IIT,Kharagpur 9.4.5 Partial-Order Planning Total-Order vs. Partial-Order Planners Any planner that maintains a partial solution as a totally ordered list of steps found so far is called a total-order planner, or a linear planner. Alternatively, if we only represent partial-order constraints on steps, then we have a partial-order planner, which is also called a non-linear planner. In this case, we specify a set of temporal constraints between pairs of steps of the form S1 < S2 meaning that step S1 comes before, but not necessarily immediately before, step S2. We also show this temporal constraint in graph form as S1 +++++++++> S2 STRIPS is a total-order planner, as are situation-space progression and regression planners Partial-order planners exhibit the property of least commitment because constraints ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps. Representing a Partial-Order Plan A partial-order plan will be represented as a graph that describes the temporal constraints between plan steps selected so far. That is, each node will represent a single step in the plan (i.e., an instance of one of the operators), and an arc will designate a temporal......

Words: 3041 - Pages: 13

Free Essay

Algorithms Notes

...DAG Topological Sort O(V+E) -performed on directed acyclic graph Linear ordering of all its vertices such that if G contains an edge (u,v) then u appears before v in the order. 1. call DFS(G) to compute finishing times v.f for each vertex v 2. as each vertex is finished insert it onto the front of a linked list 3. return the linked list of vertices 4. Lecture 5 (01/28) Posted on: Monday, January 28, 2013 Topics: Strongly Connected Components, Activity Selection Reading: CLRS (22.5, 16.1), KT (4.1) Scheduling Probelem Set of n activities which can be served only one at a time, each with start time s and finish time f Selecct a maximum-size subset of mutually compatible activities (meaning no overlap) GREEDY ALGORITHM Note that putting the job with the earliest finish time allows for the most amount of jobs to follow, because it allows the machine to have the most possible time to get to other jobs Take job with lowest finish time, then reduce set to all job that don’t overlap, then choose lowest finishing time, recursively. * Lecture 6 (01/30) Posted on: Wednesday, January 30, 2013 Topics: Activity Selection, Coloring Interval Graphs, Scheduling Reading: CLRS (16.1, 16.2), KT (4.1, 4.2) * Lecture 07 (02/04) Posted on: Wednesday, February 6, 2013 Topics: Minimizing Maximum Lateness, Sorting (Insertion Sort, Merge Sort, Quick Sort) Reading: CLRS (Chp 2, 7.1, 7.2), KT (4.2) Insertion sort Starting from the second element as key......

Words: 5019 - Pages: 21

Free Essay

Algorithms

...Algorithms Assignment 1 Kent Vuong Table of Contents Question 1 3 Machine Code (First Generation or 1GL) 3 Assembler (Second Generation or 2GL) 3 Procedural (Third Generation or 3GL) 3 Non-Procedural (Fourth Generation or 4GL) 4 Object Orientated 4 Describe the purpose and functions of an OS with the following terms 4 Scheduling 4 Managing Concurrency 4 Managing Memory 4 Managing Devices 5 File Systems 5 Describe the purpose of each of the following utility software programs. 5 File Compression 5 Defragmenter 5 Anti-Virus 5 Anti-Malware 5 What is application software, give three examples 5 What are the software licensing requirements for the following types of software 6 Freeware 6 Open Source 6 Shareware 6 Question 1 Machine Code (First Generation or 1GL) Machine Code is the Language that the Computer understands and reads, following the precise instructions, which is sometimes the problem with computers and the relaxed non-procedural human brain. The MIPS architecture provides a specific example for a machine code whose instructions are always 32 bits long. The general type of instruction is given by the op (operation) field, the highest 6 bits. J-type (jump) and I-type (immediate) instructions are fully specified by op. R-type (register) instructions include an additional field function to determine the exact operation. Assembler (Second Generation or 2GL) Assembler is a program which makes object codes by encoding...

Words: 1019 - Pages: 5

Free Essay

Euclid's Algorithm

...Assignment #2 A. Algorithm to calculate Easter day for the year 2013: X = 2013 1. Divide X by 19 to obtain a quotient (which will be ignored) and a remainder A. 2013/19 = quotient 105 and remainder 18. A = 18 2. Divide X by 100 to obtain a quotient B and a remainder C. 2013/100 = quotient 20 and remainder 13. B =20; C = 13. 3. Divide B by 4 to obtain a quotient D and a remainder E 20/4 = quotient 5 and remainder 0. D = 5; E = 0. 4. Divide (8*B + 13) by 25 to obtain a quotient G and remainder (which will be ignored). (8*20 + 13)/25 = quotient 6 and remainder 23 G = 6. 5. Divide (19*A+B-D-G+15) by 30 to obtain a quotient which will be ignored and a remainder L. (19*18+20-5–6+15)/30 = quotient 12 and remainder 6 H = 6. 6. Divide (A+11*H) by 310 to obtain a quotient M and a remainder (which will be ignored). (18+11*6)/310 = quotient 0 and remainder 174. M = 0 7. Divide C by 4 to obtain a quotient J and a remainder K. 13/4 => quotient 3; remainder 1 J = 3 and K = 1 8. Divide (2*E + 2*J - K – H + M + 32) by 7 to obtain a quotient (which will be ignored) and a remainder L. (2*0 + 2*3 – 1 – 6 + 0 + 32)/7 = quotient 4 and remainder 3. L = 3. 9. Divide (H - M + L + 90) by 25 to obtain a quotient N and a remainder (which will be ignored). (6 – 0 + 3 + 90)/25 = quotient 3 and remainder 24. N = 3. 10. Divide (H – M + L + N + 19)/32 to obtain a quotient (which will be ignored and a remainder P. (6 – 0 +3+3+19)/32 =......

Words: 477 - Pages: 2

Free Essay

382 Algorithms

...CSC 382, Analysis of Algorithms Group Project For this project you need to make groups of 3-6 people and choose one of the following topics. Most of these topics require you to write a short paper and present it in class (20 points). For those you have the option to just submit a paper and not present for only 10 points. A list of topics: 1. Linear Programming 2. Approximation Algorithms 3. Max-Flow Min-Cut 4. Cryptography: Asymmetric Encryption 5. Complexity Theory 6. Programming Project: Implementing Algorithms, Comparing Running times (10 points, no presentation) For some topics you can find information in the course textbooks (and other textbooks). For the rest, you must research on your own - but I am willing to give suggestions if I have any. You may suggest another topic as well, but I need to approve it. Requirements Each paper is expected to be 3-5 pages long (single-spaced and at 11pt) and it should include references to your sources (which should be more than just Wikipedia). As long as the paper is complete and well-written, the length requirements should not be too important. However, more than 5 pages would be an overkill and less than 3 might not let you give the necessary information and explanations. As for the actual contents of the paper, you should address your classmates, who will receive a copy of the paper in class and before your presentation. You should explain the topic you have selected and give an appropriate 1 2 example. The specifics may differ...

Words: 796 - Pages: 4

Free Essay

Gnetic Algorithms

...Genetic Algorithms Basic Genetic Algorithm – Flow Chart 1. Initial Population 1. Initial Population ON ON | | GENERATE RANDOM POPULATION (POSSIBLE SOLUTIONS) | 2. Fitness Evaluation 2. Fitness Evaluation 3. Selection 3. Selection | | EVALUATE THE FITNESS OF EACH (BASED ON THE FITNESS FUNCTION) | | | CHOOSE PARENT FACTORS (BETTER FITNESS = BETTER CHANCE) | 4. Crossover 4. Crossover 5. Mutation 5. Mutation | | CROSSOVER THE PARENT TRAITS TO FORM NEW CHILDREN. (PROBABILITY) | | | MUTATION PROBABILITY APPLIED (MAINTAINS GENETIC DIVERSITY) | Acceptable? Acceptable? | | IF OPTIMIZATION CONDITIONS ARE NOT MET(REPEAT STEPS 2-5) * OR | Yes Yes End Process End Process | | IF THE MAXIMUM GENERATIONS ARE MET (TERMINATE) * OR | | | IF SATISFACTORY FITNESS LEVEL IS REACHED (END THE PROCESS) | KEY TERMS * INDIVIDUAL Any possible solution to the problem at hand, usually expressed in binary code * POPULATION Group of all individuals * CHROMOSOME Blueprint for an individual usually expressed in binary code. (Ex: 011011) * GENE An individual value in a chromosome, usually expressed as a “1” or “0” * PARENTS An original “individual” solution in the GA process that has passed the fitness function * CHILDREN A new solution to the problem formed through crossover and mutation from the parent solutions * SEARCH SPACE All possible solutions to the......

Words: 261 - Pages: 2

Free Essay

Kolmogorov Algorithm

...CSC 435 DESIGN AND ANALYSIS OF ALGORITHM GROUP THREE(3) ASSIGNMENT THE KOLMOGOROV COMPLEXITY ALGORITHM Computer Science: FMS/0704/11 FMS/0707/11 FMS/0720/11 FMS/0721/11 FMS/0728/11 Computing-with-Accounting: FMS/0818/11 FMS/0643/11 FMS/0749/11 FMS/0722/11 FMS/0729/11 FMS/0741/11 FMS/0829/11 FMS/0784/11 FMS/0812/11 FMS/0652/11 Kolmogorov complexity In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity) of an object, such as a piece of text, is a measure of the computability resources needed to specify the object. It is named after Andrey Kolmogorov, who first published on the subject in 1963. For example, consider the following two strings of 32 lowercase letters and digits: abababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7 The first string has a short English-language description, namely "ab 16 times", which consists of 11 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has 32 characters. More formally, the complexity of a string is the length of the shortest possible description of the string in some fixed universal description language (the sensitivity of complexity relative to the choice of description language is discussed below)...

Words: 3373 - Pages: 14

Free Essay

Algorithm

...Design and Analysis of Computer Algorithm Assignment 2 Name: Boyu Zhang UTD-ID: 2021226566 Email:bxz140830@utdallas.edu Contents Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Problem 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Problem 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 Problem1 This problem can solution by Dial’s algorithm in the lesson six. We can set up W+2 buckets with the labels of 0, 1, …, W, . Then we carry out the following steps: (a). Initial the buckets with node S be in the bucket 0 and all other nodes be in the bucket . (b). then select the node with the minimum temporary distance label. For the first time, it should be the source node S in the bucket 0. (c). Update the buckets information. Then some node should be moved from the bucket  to the corresponding distance bucket. (d). Remove the selected node from the bucket. Then repeat step 2 and 3 until there is no non-empty bucket.......

Words: 726 - Pages: 3

Free Essay

Vwap Algorithm

...Competitive Algorithms for VWAP and Limit Order Trading Sham M. Kakade Michael Kearns Computer and Information Science University of Pennsylvania Computer and Information Science University of Pennsylvania kakade@linc.cis.upenn.edu mkearns@cis.upenn.edu Yishay Mansour Luis E. Ortiz Computer Science Tel Aviv University Computer and Information Science University of Pennsylvania mansour@post.tau.ac.il leortiz@linc.cis.upenn.edu ABSTRACT We introduce new online models for two important aspects of modern financial markets: Volume Weighted Average Price trading and limit order books. We provide an extensive study of competitive algorithms in these models and relate them to earlier online algorithms for stock trading. Categories and Subject Descriptors F.2 [Analysis of Algorithms and Problem Complexity]: Miscellaneous; J.4 [Social and Behavioral Sciences]: Economics General Terms Algorithms, Economics Keywords Online Trading, Competitive Analysis, VWAP 1. INTRODUCTION While popular images of Wall Street often depict swashbuckling traders boldly making large gambles on just their market intuitions, the vast majority of trading is actually considerably more technical and constrained. The constraints often derive from a complex combination of business, regulatory and institutional issues, and result in certain kinds of “standard” trading strategies or criteria that invite algorithmic analysis. One of the most......

Words: 9064 - Pages: 37

Free Essay

Algorithm

...1. Illustrate the operation of Radix_sort on the following list of English words: cow, dog, seq, rug, row, mob, box tab, bar ear, tar, dig, big, tea, now, fox. ANSWER: It is a sorting algorithm that is used to sort numbers. We sort numbers from least significant digit to most significant digit. In the following array of words, three is the maximum number of digits a word has, hence the number of passes will be three. In pass 1, sort the words alphabetically using first letter from the right. For eg, tea has “a” as the last letter, hence it comes first, similarly mob which has “b” as the last letter comes second. In this way the remaining words are sorted. In pass 2, sort the words alphabetically using second letter from the right. For eg, tab has “a” as its middle letter which comes first, then comes bar and so on. In pass 3, sort the words alphabetically using third letter from the right. For eg, bar has “b” as its first letter from left and since no word starts with “a”, bar will appear first. Similarly, big, box, cow and so on. UNSORTED ARRAY | PASS 1 | PASS 2 | PASS 3(SORTED ARRAY) | cow | tea | tab | bar | dog | mob | bar | big | seq | tab | ear | box | rug | rug | tar | cow | row | dog | tea | dig | mob | dig | seq | dog | box | big | dig | ear | tab | seq | big | fox | bar | bar | mob | mob | ear | ear | dog | now | tar | tar | cow | row | dig | cow | row | rug | ...

Words: 1470 - Pages: 6

Free Essay

Introduction to Algorithm

...4. G REEDY A LGORITHMS I ‣ coin changing ‣ interval scheduling ‣ scheduling to minimize lateness ‣ optimal caching Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/~wayne/kleinberg-tardos Last updated on Sep 8, 2013 6:30 AM 4. G REEDY A LGORITHMS I ‣ coin changing ‣ interval scheduling ‣ scheduling to minimize lateness ‣ optimal caching Coin changing Goal. Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. Ex. 34¢. Cashier's algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid. Ex. $2.89. 3 Cashier's algorithm At each iteration, add coin of the largest value that does not take us past the amount to be paid. CASHIERS-ALGORITHM (x, c1, c2, …, cn) ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________...

Words: 3591 - Pages: 15