clrscode's Introduction

clrscode

CLRS ain't gonna solve itself.

PDF Files:

These contain all sorts of algorithms and mathematical solutions to relevant/irrelevant programs/chapters. Most of the algorithms mentioned in the book have been implemented as below and the solutions to the problems which are not algorithms are contained in these pdf files. For the time being, these are written solutions and I will try to convert them into book format using latex if time permits.

Description

Algorithm	Run Time	Where
Linear Search	O(n)	Chapter 2, section 2.1
Insertion Sort	O(n^2)	Chapter 2, section 2.1
Selection Sort	O(n^2)	Chapter 2, section 2.2
Maximum Subarray Problem	O(n^2)	Chapter 4, section 4.1
Maximum Subarray Problem	O(n*logn)	Chapter 4, section 4.1
Maximum Subarray Problem	O(n)	Chapter 4, section 4.1
Max Heapify	O(logn)	Chapter 6, section 6.2
Min Heapify	O(logn)	Chapter 6, section 6.2
Iterative Max Heapify	O(logn)	Chapter 6, section 6.2
Build Max Heap	O(n*logn)	Chapter 6, section 6.3
Partition	O(n)	Chapter 7, section 7.1
Quick Sort	O(n*logn)	Chapter 7, section 7.1
Randomised Quick Sort	O(n*logn)	Chapter 7, section 7.3
Quick Sort with Insertion Sort	O(nk + nlog(n/k))	Chapter 7, section 7.4
Quick Sort with median of 3	O(n*logn)	Chapter 7, section 7.4
Tail Recursive Quick Sort	O(n*logn)	Chapter 7, Problem 7-4
Counting Sort	O(n+k)	Chapter 8, section 8.2
MinMax	(3n/2) comparisons	Chapter 9, section 9.1
Minimum	(n+logn-2) comparisons	Chapter 9, section 9.1
Randomised Select	O(n)	Chapter 9, section 9.2
Deterministic Select	O(n)	Chapter 9, section 9.3
Stack	-	Chapter 10, section 10.1
Double Stack	-	Chapter 10, section 10.1
Queue	-	Chapter 10, section 10.1
DeQueue	-	Chapter 10, section 10.1
Queue using 2 Stacks	-	Chapter 10, section 10.1
Stack using 2 Queues	-	Chapter 10, section 10.1
Rod Cutting	O(n^2)	Chapter 15, section 15.1
Rod Cutting (min cuts)	O(n^2)	Chapter 15, section 15.1
Fibonacci	O(n)	Chapter 15, section 15.1