jinghuaswsx / introduction_to_algorithms

Some Implementation or Solutions to Exercises

All stuff contained is user-implemented algorithms depicted in the book Introduction to Algorithms, and most of which can be considered as candidates for solutions to exercises

For any other solutions to exercise, please see at http://sdrv.ms/17TUmTY

##Chapter 5: Probabilistic Analysis and Randomized Algorithms

• RandomEx. ch5.1 exer 2 implement a generator RANDOM[a,b] by only using RANDOM[0,1]

• PermutingBySorting. randomize an array via generating and sorting priorities associating with elements in the array.

• PermuteInPlace. randomize an array in place.

• RandomSample. produce a m-subset from S={1,2,3,..,n}.

• RandSearch. ch5 Problem 5-2 an interesting search algorithm.

##Chapter 6: Heapsort

• MaxHeapify. keep heap conforming to max-heap property.

• MaxHeapify_Iter. iterative implementation.

• BuildHeap. build a max-heap on an array.

• Heapsort heapsort algorithm.

##Chapter 7: Quicksort

• Quicksort and Partition naive implementation for quicksort and its inherent partition routine.

• RandomPartition randomized version.

• QSortWithInsertion an optimizatio implementation that binds insertion sort and quicksort.

##Chapter 8: Sorting in Linear Time

• CountingSort counting sort implementation.

• RadixSort and UnderlyingSort a radix sort implementation for 32-bit non-negative integers.

• BucketSort bucket sort implementation.

• InPlaceCountingSort and _InPlaceCountingSort a general in-place counting sort implementation (also need O(k) extra storage) and a special variant of O(1) in-place counting sort.

##Chapter 9: Medians and Order Statistics

• FindMaxandMin find both max and min at same time using least comparisons

• RandomizedSelecton and RandomizedSelectonIter k-th smallest problem implementation

##Chapter 10: Elementary Data Structures

• class Deque a quick-and-simple deque implementation

• a set of operations based on singly linked list

• class XORQueue a queue based on xor-linked-list.