Week 11 - Complexity of Heapsort Algorithm （episode3）

Firstly, I would like end this problem episodes. It is continued from last 2 weeks where I was at representing size of trees in regions of the Heap. The size of left subtree equals the sum of region 1's and region 3's which is 2^d - 1 where d represents the depth of heap.

Let n = 2^d + k, where 0 <= k < 2^d. The left subtree contains 2^(d-1) + j nodes and 0 <= j < 2^(d-1). If i = k - j. 0 <= i <= 2^(d-1), then n = 2^d + j + i and:

Size of left subtree / n = 2^(d-1) + j / 2^d + j + c <= 2^(d-1) + j / 2^d + j = f(j)

Let a = 2^(d-1). Then, f(j) = (a + j) / (2a + j)

f(0) = (a + 0) / (2a + 0) = 1/2

f(a) = 2a/3a = 2/3

f'(j) = a/(2a+j)^2 >= 0

So f is an increasing function that takes on a maximum at the left endpoint, and the max is 2/3. 

Then state result as a theorem:

If a heap A has size n, its subtrees have size less than or equal to 2n/3.

Applying this theorem to Equation of Heapify which is shown in episode 1, then

T*(n) = T(2n/3) + Θ(1).

Build Heap.

the complexity of BuildHeap appears to be  Θ(n lgn) - n calls tto Heapify at a cost of Θ(lgn) per call, but this result can be improved to Θ(n). 

Putting the results together with Equation of Heap sort in episode 1. Then the run-time complexity for HeapSort is,

T(n) = T*(n) + sum of T*(k) from 1 to (n-1) + Θ(n-1)

= Θ(n) + sum of lg k from 1 to (n-1) + Θ(n-1)

=  Θ(n lgn)

Week 10 - Complexity of HeapSort Algorithm (episode 2)

Before I continue on episodes of "Complexity of heap sort algorithm", I'd like to do a little review about topics which we mention in recently lecture. Finite state machine, finite state automata or any nouns of finite state, is the most related topic to us right now. It has been mentioned in all my second year computer science courses. I also want to make a note for DFSA which is very important in csc236. It has been quizzed today before I got right track on solving and devising that diagram.

Here we go!!! Continue on the episode:

Week 9 - Complexity of HeapSort Algorithm (episode 1)

As we talks about time complexity in lecture, we have mentioned Merge and binary search. In order to follow up "Complexity", I would like to do more on the other kinds of sort. Heap sort is the first sorting algorithm I have learned in csc108 from last year which may be more impressive to most of you and me.

So, basically, there are two step algorithm in Heap sort. The first step is to build up a heap out of an array. Then the second step is to begin with removing the smallest element from the heap then put it into an array.

Here is the function I write for the Heap sort. I'd like to solve this complexity precisely in next episode.


def Heapify(A, i, n):
    l = Left( i )
    r = Right( i )
    if l A[ i ]:
        largest = l
    else:
        largest = i
    if r A[ largest ]:
        largest = r
    if largest != i:
        A[ i ], A[ largest ] = A[ largest ], A[ i ]
        Heapify(A, largest, n)


def BuildHeap(A):
    n = len(A) - 1
    for i in range( n/2 ,0 ,-1 ):
        Heapify(A, i, n)


def HeapSort(A):
    BuildHeap(A)
    HeapSize = len(A) - 1
    for i in range( HeapSize, 1 , -1 ):
        A[ 1 ],A[ i ] = A[ i ],A[ 1 ]
        HeapSize = HeapSize-1
        Heapify( A,1,HeapSize )

week 8 - Summing up as Assignment 2 and Midterm 2

As I was reviewing for the second midterm for csc236, I was also recalling the whole schedule of this course. Assignments and midterms come up periodically which may be a kinda annoying in my view due to I have very heavy load for fall. However, my opinion makes a turn this time. Summarizing what I learn in a period enhances my point of views on specific topics and memory. Then I sum up my notes in a new way. 

Practice is the best way to keep knowledge being impressive on your mind. Therefore, I rewrite my notes in the way like: 

# Left                                                                                        # Right

Summary                                                                              Corresponding Problems

      of

   Notes

                                                        # Bottom

                                         Learn from problems and key points

                                                        Proof structure

It is a pretty busy week for me so I would like to share one of problem episodes next time and go further. It is an interesting problem but not easy.

Week 7 - days of recurrences

Happy Halloween !!! The day was really ruined by storm, wasn't it? :(

The first topic came up from last week was recursively defined functions. It is not on the midterm but I am a fan of that because it involves relative more algebra calculations instead of more analyzing. Basically, it is a kind of questions which gives you a defined, recursive function, then it asks you to prove a statement depends on the given recursive function by unwinding and induction step.
However, a question came up my mind when I was focusing on the lecture. "Which are not proper definition of functions?" By observation, the examples given in lecture and tutorial are all proper. I summarized about it somehow but also looked up from online textbook. Mostly, my summary matched book's.

1. the induction step has to define value of a function properly for all n.
2. no term to make function circular
3. define f(n) in terms of the value of f at smaller statement

* it is such a good way to summarize the points of views by self-observation which makes me analyze more than learn from read.

Also, more importantly, divid and conquer recurrences and Master theorem has been taught in the lecture. Once the lecture mentioned about the time complexity, Big O stuff that I learned from CSC165 came up my mind. Since lectures was running fast and I was kinda lost, I reviewed textbook which was really helpful. I realized the reason that I didn't do well in CSC165 at this part was that I wasn't fully understand the time complexity and just followed the steps of proof. I dig more about understanding and reasoning this year not only by textbook but also web sources. Practice makes me not only think fast but deeply.

I'd like to share some interesting problems that I collect from other sources next time after I finish my A2. 

Week 6 - Feedback from term test 1

Even a couple of midterms and assignments did bring lots of pressure, I was still well prepared for the term test 1 which included MI, CI, WI and SI. After I went through the course information sheet, quiz is possible to switch its weight with term test's which did make me not that stressful.

Basically, I organized all of stuff that I learned in lectures, tutorials and even previous test resources into a list. I listed them by essentiality because I had to share the time with other courses' task. The material I listed at the top or relatively top has priority for me to go through. (Since I did a terrible job on CSC165, I paid more time on proof)

The list I made with descriptions:

1. Lecture sample question

  # I redo them without back to notes then highlight my incorrect and missing steps. It might kinda hard to start due to I had to recall them from my faint memory without reviewing, but I insisted it is a great way to know which parts of course I needed to focus on and paid more attention even it really takes time.

2. Review my lecture notes

 # I went through my notes partly. Then, I rewrote the structural, format and step each of all inductions I  learned nicely.

3. Tutorial question practice

 # I wrote down the answer step by step instead of leaving them once I got an idea to prove. Practice more, gain more.

4. Discussion board

 # See if anyone had same problems as I met.

5. Previous test

 # Go through some previous test question and think for solutions but not write them down.

Week 5 - First impressions on CSC236

Hi fellows,

It's my first blog or more like an academic platform which could record and organize nicely with customizing so I am quite exciting. Because everyone's blog location are available to see, people are sharing things I may know or don't know and it becomes a way to communicate and get linked with same field information. So, as a Computer science student, I am interested in it and glad to enrol in the fields.

As for the first 4 weeks of the course,  Simple Induction (or MI), Complete Induction, Well-Ordering Induction and Structural Induction are being practiced. During proof steps, they have their own steps and structures which help more on proving. Personally, I like Complete Induction most.

Here is my solution for A1 part-4, which is quite different with the posted solution on course website. I do like to share this complete induction and hope you guys could give me some advice whether on this proof or not :)