Updated complementary exercises for CLRS 20110701

Things I have finished:
-(DONE) Chapter2: Watch the MIT video on Chapter2
-(DONE) Chapter3: Read TAOCP on Big Oh.
-(DONE) Chapter3: -Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject.
-(DONE) Insertion sort: C, perl, python
-(DONE) Insertion sort: sentinel version of straight insertion sort
-(DONE) Insertion sort: binary search (now a separate item)
-(DONE) Insertion sort: binary insertion sort (now a separate item)
-(DONE) Selection sort: recursive version of insertion sort
-(DONE) Selection sort: C, perl, python
-(DONE) Merge sort: C, perl
-(DONE) Merge sort: Read sedgewick Chapter 8
-(DONE) Linear search: C, MIXAL
-(DONE) Binary search: C
-(DONE) Binary Insertion sort: C
-(DONE) Maximum Subarray Problem : C

Chapter 2 General:
-Write up the summary of the videe on Chapter 2
-Read all the solution sets after I finished the videos.
-work out cost analysis similar to P.26 on selection sort, linear
 search and merge sort (tedious).
-Think how to draw the recursion tree for the insertion sort algorithm.
-Work out all proofs for the following algorithms
  -insertion sort
  -selection sort
  -bubble sort
  -binary insertion sort
  -merge sort
  -linear search
  -binary search
-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion
 calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is
 based on merge.  Think them through.

Chapter 3 General
-Finish all exercises of Sedgewick Chapter 2.
-Finish all exercises below Level 25 of TAOCP Section 1.1 and 1.2
-Read CMath Chapter 2, 3 and 9.  Finished all easy exercises.
-Alternative definitions of the asymptotic notion.
-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort: (C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.
   -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP.
-insertion sort with linked list
-How does the idea of insert leads to merge sort?
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort: (C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.)
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:  (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)

Bubble sort: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-shaker sort
-TAOCP 5.2.2


Merge sort: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-timsort
-performance, worst case, average case
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version
-in place mergesort.
-no extra memory implementation (state of art?)
-variations of merge sort.
-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises.
-where can I find problems which apply merging?
  -Implement CLRS 2.3-7 using merging
  -like to calculate number of inversions.

Linear search: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think.

Binary search: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-At least 100 problems which applies binary search.
   -TopCoder's exercises on binary search.
   -Implement CLRS 2.3-7.
   -Shene Chapter 4.
-After reading Gries, make sure you prove your own binary search is correct.
-TAOCP 6.2 and exercises.
-Chapter 4 and 5 of Programming Pearl exercises.
-Sedgewick 12.4
-Fibonacci search
-Range search
-Variations of binary search.
-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting.
-Thinking: can we combine the idea of distribution in binary search?
-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can.
-Try to do exercises in TAOCP 5.1.

Maximum Subarray Problem:
-perl, python, C++, java, lisp, ASM
-(* hightly recommended) Finish all exercises in Programming Pearl Chapter 8.
-Thinking: How do you extend maximum subarray problem?

Updated complementary exercises for CLRS 20110609

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. (done)

-Write up the summary of the video. 

-Read all the solution sets after I finished the videos. 

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious).

-Think how to draw the recursion tree for the insertion sort algorithm. 

-Work out all proofs for the following algorithms

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

Chapter 3 General

-TAOCP? Knuth must have talk about Big Oh at a certain point.  (done)

-There is no difference between CLRS and TAOCP (done)

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject. (done)

-Finish all exercises of Sedgewick Chapter 2.

-Finish all exercises below Level 25 of TAOCP Section 1.1 and 1.2 

-Read CMath Chapter 2, 3 and 9.  Finished all easy exercises.

-Alternative definitions of the asymptotic notion.
-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.
   -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP. 

-insertion sort with linked list
-How does the idea of insert leads to merge sort?

-C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercises. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can. 
-Try to do exercises in TAOCP 5.1.

Updated complementary exercises for CLRS 20110605

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. (done)

-Write up the summary of the video. 

-Read all the solution sets after I finished the videos. 

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious).

-Think how to draw the recursion tree for the insertion sort algorithm. 

-Work out all proofs for the following algorithms

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

Chapter 3 General

-TAOCP? Knuth must have talk about Big Oh at a certain point.  (done)

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject.
-Alternative definitions of the asymptotic notion. 

-Finish all exercises of Sedgewick Chapter 2.

-Finish all exercises below Level 25 of TAOCP Section 1.1 and 1.2 

-CMath Chapter 9, all warm up and beginner exercises. 

-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.    -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP. 

-insertion sort with linked list
-How does the idea of insert leads to merge sort?

-C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercises. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can. 
-Try to do exercises in TAOCP 5.1. 


Appendix A:
-Read CMath Chapter 1 and 2. Finished warmup and beginner exercises.

Updated complementary exercises for CLRS 20110529

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. (done)

-Write up the summary of the video. 

-Read all the solution sets after I finished the videos. 

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious).

-Think how to draw the recursion tree for the insertion sort algorithm. 

-Work out all proofs for the following algorithms

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

Chapter 3 General

-TAOCP? Knuth must have talk about Big Oh at a certain point.  (done)

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject.
-Alternative definitions of the asymptotic notion. 

-Finish all exercises of Sedgewick Chapter 2.

-Finish all exercises below Level 25 of TAOCP Section 1.1 and 1.2 
-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.
   -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP. 

-insertion sort with linked list
-How does the idea of insert leads to merge sort?

-C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercises. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions: 
-Try to understand TAOCP 5.1 as much as I can. 
-Try to do exercises in TAOCP 5.1. 

Updated complementary exercises for CLRS 20110525(a)

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. 

-Work out all proofs for the following algorithms

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

-Read all the solution sets after I finished the first 3 items.

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious).

Chapter 3 General

-TAOCP? Knuth must have talk about Big Oh at a certain point.  (done)

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject.
-Alternative definitions of the asymptotic notion. 

-Finish all exercises of Sedgewick Chapter 2.

-Finish all exercises below Level 25 of TAOCP Section 1.1 and 1.2
-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.
   -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP. 

-insertion sort with linked list
-How does the idea of insert leads to merge sort?

-C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case 
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version 
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercies. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can. 
-Try to do exercises in TAOCP 5.1. 

Updated complementary exercises for CLRS 20110524

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. 

-Work out all proofs for the following algorithms

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

-Read all the solution sets after I finished the first 3 items.

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious).

Chapter 3 General

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject.
-Alternative definition of the asymptotic notion. 

-Finish all exercises of Sedgewick Chapter 2.
-TAOCP? Knuth must have talk about Big Oh at a certain point. 
-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.
   -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP. 

-insertion sort with linked list
-How does the idea of insert leads to merge sort?

-C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case 
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version 
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercies. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can.

Updated complementary exercises for CLRS 20110521

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. 

-Work out all proofs for the following algorithm

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

-Read all the solution sets after I finished the first 3 items.

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious). 

Chapter 3 General

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject. 

-Finish all exercises of Sedgewick Chapter 2.

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-shell sort, how does the decrement business work?
-library sort
-tree sort(from wikipedia, what is it?)

-linked list

-insertion sort with linked list

-C++,java, lisp, ASM
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercise in 5.2.1
-Sedgewick 6.3
-Sedgewick 6.3 Exercise

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case 
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version 
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-merge sort with k list and a k-list merging. 2.4.1
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercies. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can.

Updated complementary exercises for CLRS 20110520

Chapter 2 General:

-Watch the MIT video if it is only about Ch2. 

-Work out all proofs for the following algorithm

  -insertion sort

  -selection sort

  -bubble sort

  -binary insertion sort

  -merge sort

  -linear search

  -binary search

-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is based on merge.  Think them through.

-Read all the solution sets after I finished the first 3 items.

-work out cost analysis similar to P.26 on selection sort, linear search and merge sort (tedious). 

 

Chapter 3 General

-Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject. 

-Finish all exercises of Sedgewick Chapter 2.

 

Insertion sort:

-C, perl, python (done)

-sentinel version of straight insertion sort (done)

-binary search (done, now a separate item)

-binary insertion sort (done, now a separate item)

-recursive version of insertion sort (done)
-shell sort, how does the decrement business work?
-library sort
-tree sort(from wikipedia, what is it?) 

-C++,java, lisp, ASM
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercise in 5.2.1
-Sedgewick 6.3
-Sedgewick 6.3 Exercise

Selection sort:
-C, perl, python (done)
-C++,java, lisp, ASM
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:

-C (done)

-perl, python, C++, java, lisp, ASM

Bubble sort:

-C (done)

-shaker sort

-perl, python, java, lisp, ASM

-TAOCP 5.2.2

Merge sort:
-C, perl(done)
-python, C++,java, lisp, ASM
-timsort
-performance, worst case, average case 
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version 
-in place mergesort.
-no extra memory implementation (state of art?)

-variations of merge sort. 

-merge sort with k list and a k-list merging. 2.4.1
-TAOCP Exercise in 5.4
-Sedgewick 8 (read - done)
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises. 

-where can I find problems which apply merging? 

  -Implement CLRS 2.3-7 using merging

  -like to calculate number of inversions.

Linear search:

-C, MIXAL (done)
-perl, python, C++,java, lisp, ASM

-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think. 

Binary search: 

-C (done)
-perl, python, C++,java, lisp, ASM

-At least 100 problems which applies binary search.

   -TopCoder's exercises on binary search. 

   -Implement CLRS 2.3-7.

   -Shene Chapter 4. 

-After reading Gries, make sure you prove your own binary search is correct. 

-TAOCP 6.2 and exercies. 

-Chapter 4 and 5 of Programming Pearl exercises. 

-Sedgewick 12.4

-Fibonacci search

-Range search

-Variations of binary search. 

-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting. 

-Thinking: can we combine the idea of distribution in binary search?

-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can.