Competitive codes

==>  https://www.topcoder.com/community/competitive-programming/tutorials/an-introduction-to-binary-search-and-red-black-trees/

=>  Maximum Consecutive Gap => Solution , Hindi => Longest Common Subsequece (LCM) => Solution Simple implementation of LCM to find largest palindromic sunsequence => Distinct subsequence => Solution => Dynamic Problems => Solution  -----------xxxxx------ END-----xxxxx

A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets, supporting (though not necessarily efficiently) all the operations. As shown in Figure 10.3, each element of a doubly linked list L is an object with an attribute key and two other pointer attributes: next and pre . The object may also contain other satellite data. Given an element x in the list, x.next points to its successor in the linked list, and x.pre points to its predecessor. If x.pre  = NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If x.next  = NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the first element of the list. If...

Introduction Any number of practical applications in computing require things to be in order. Even before we start computing, the importance of sorting is drilled into us. From group pictures that require the tallest people to stand in the back, to the highest grossing salesman getting the largest Christmas bonus, the need to put things smallest to largest or first to last cannot be underestimated. When we query a database, and append an ORDER BY clause, we are sorting. When we look for an entry in the phone book, we are dealing with a list that has already been sorted. (And imagine if it weren’t!) If you need to search through an array efficiently using a binary search, it is necessary to first sort the array. When a problem statement dictates that in the case of a tie we should return the lexicographically first result, well… you get the idea. General Considerations Imagine taking a group of people, giving them each a deck of cards that has been shuffled, and requesting that they sor...

Quick Notes Heapsort’s running time is O( n lg n ). Like insertion sort, but unlike merge sort, heapsort sorts in place. Heapsort also introduces another algorithm design technique: using a data structure, in this case one we call a “heap,” to manage information. Heaps The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. An array A that represents a heap is an object with two attributes: A. length , which (as usual) gives the number of elements in the array, and A .heap-size , which represents how many elements in the heap are stored within array A. That is, although A[1 . . A. length ] may contain numbers, only the elements in A[1 . . A. heap-size ], where 0 ≤ A. heap-size  ≤ A. length , are valid elements of the heap. The root ...

Introducion Input: A sequence of n numbers ( a 1 , a 2   . . . , a n )  Output: A permutation (reordering) ( a' 1 , a' 2 , . . . , a' n ) of the input sequence such that a' 1 < a' 2 <. . . < a' n .  The numbers that we wish to sort are also known as the keys . Although conceptually we are sorting a sequence, the input comes to us in the form of an array with n elements. Sorting a hand of cards using insertion sort. We start with insertion sort, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left. At all times, the cards held in the left hand are s...