Wake Up！Davidson！

[IMPORTANT] Davidson's Blog is moved to mszheng.com

2012-02-05T18:03:00.000-08:00

Please notice that my blog is moved,

for further update, please refer to mszheng.com.

此部落格将停止更新，

请关注mszheng.com获取更多信息。

このブログは mszheng.comに移転しましたよ。

ぜひご覧になってください！

Memory Management, Paging

2011-10-13T17:15:00.000-07:00

Page frames or frames: memory is partitioned into equal, fixed-size chunks

Pages: memory of processes are divided into chunks with same size

Pages fit into any free page frame.

Benefits: No external fragmentation. Relatively little internal fragmentation(a part of a page).

For each process, a page table is associated with it. It records the information about which

page is in which page frame.

Virtual Address = Page number + Page offset = vaddr / page size + vaddr % page size

Some calculations:

Suppose a logical address is 32 bits and a page is 8 kbytes

Bits of the logical address are used to address bytes within a page:

8kbytes = 2^10 * 2^3 = 2^13; least significant 13 bits

Number of bytes can be addressed with a logical address:

2^32

Number of logical pages:

2^20

If a PTE is 4 bytes, space required for the page table:

2^20*2*2 = 2*22 bytes, 22 bits to represent

Memory Management, part 2

2011-10-13T16:26:00.000-07:00

Another way to partition memory is Dynamic Partition.

Partitions vary depending on the size of a process. The placement with dynamic allocation

is to allocate exactly the size of a process in the memory.

However, when processes exit, holes might be created between every two processes.

This is called External Fragmentation.

When OS move processes down to eliminate holes, larger free space are created.

This action is called Memory Compaction.

We need to know what is the maximum size of a process at load time. Otherwise, we

must be able to add to its partition, potentially relocating it.

To keep track of memory allocation, we can use Bitmaps.

Placement Heuristics:

Memory compaction is time-consuming. We can reduce compaction if we systematically

allocate memory. The following techniques give us an idea how this can be achieved.

First-fit, allocate the first block large enough, appears to be the BEST choice, leave

external fragmentation at start of memory

Next-fit, allocate the block where previous search ends at, a variation of first-fit,

free space becomes fragmented more rapidly

Best-fit, scans through the blocks and finds the most suitable block in size,

small, unusable fragments

Worst-fit, find the largest block

Quick-fit, keep multiple free lists for common block sizes,

fast allocation, harder to coalesce

Relocation:

a way to change the physical memory reference

Dynamic relocation:

execution-time binding of addresses, hardware translates to physical addresses as instructions are executed.

base address + relative address = physical address <= limit address

Basic problems that cause internal fragmentation and external fragmentation and so on...:

we assume processes are allocated to contiguous block of memory

Solution: Paging

To be continued...

Memory Management

2011-10-12T22:21:00.000-07:00

The Quiz 1 is coming soon I am kind of falling behind the schedule. I decide to spend some times

to go over the concepts that have been covered in the lecture so hopefully I won't "fail" this course the second time.

I've been dealing with the memory management problems all the time when I implementing

the thread sub-system and system call functions.

Why should each process has its own address space? Why do we even come to this abstraction?

First, we want to protect the OS from being modified or trashed or whatever easily because of easy access to physical memory.

Second, we want to run multiple programs at once.

When multiple programs are running, two programs present: protection and relocation.

Address space creates a kind of abstract memory for programs.

It is a set of addresses for processes to address memory.

Each process then owns its private address space, continuous and contiguous.

An important concept to remember is "Address Translation". It is the process of mapping addresses in the programs, mostly referred to the variables or symbolic addresses that

programmers use, into physical addresses.

To deal with memory problems, two strategies are commonly used: swapping and virtual memory.

Swapping means to swap process in and out from memory and to put the inactive process

on the disk. Virtual memory allows program to run even when they are partially in main memory. This is insane technology! I will go over it later since there's quite a few things.

In the lecture, we discussed about the Partition problem. Process will grow as they run.

We must determine whether to partition the memory into fixed-size chunks or dynamically

allocate the memory. We want to allocate extra memory for a process to reduce the overhead

associated with swapping processes that no longer fit in out from the memory.

It is somewhat complicated here. Let's start over again.

When the space is no longer large enough for a process, it will be swapped out and it has

to wait until a lager hole in the memory becomes available. The static/fixed-size allocation

is simpler to implement, but it creates Internal Fragmentation. In this case, memory

is wasted if process in a partition is smaller. For programs that are larger than the partitions,

we have Overlay problems. Then those programs have to get the hell out of the memory. (:<)

Gotta sleep now.

To be continued...

os161 - fork(), part 2

2011-10-10T02:26:00.000-07:00

If a process is running a user program in user mode and needs a system service, such as reading

data from a file, it has to execute a "trap" instruction to transfer control to the OS.

When an interrupt signal occurs, there has to be some reasons for the occurrence.

The information needed to be handled are pushed onto the stack in user space.

The system handler is just a function in os161 that takes a pointer to trapframe as argument.

In os161, we define a structure called trapframe, which describe what is saved on the stack

during entry to the exception handler. The first 4 32-bit arguments are passed in the 4

argument registers a0-a3 by convention. 64-bit arguments are passed in aligned pairs of

registers, either a0/a1 or a2/a3. The system call number is passed in the v0 register.

On success, the return value is passed in the v0 register. a3 is set to 0.

For example, 0 is returned to the child process after fork() succeed.

On failure, error code is passed in v0 and a3 is set to 1.

Upon syscall return, the PC stored in the trapframe (tf_epc) must be incremented by 4 bytes,

which is the length of one instruction. Otherwise the return code restart at the same point.

Look closely inside syscall() in kern/arch/mips/syscall/syscall.c, we shall see how it works.

In the case of fork(), the OS will pass the trapframe pointer and PID into sys_fork.

For the parent process, the syscall function will examine the return value(a PID or error code)

of sys_fork to set the register values. Then the parent process shall proceed.

In sys_fork(), the parent process will allocate some memory in the heap and make a copy

of the trapframe on the stack for the child process. A pointer to this trapframe will be passed into thread_fork().

Later the child will free the memory allocated previously by the parent on the heap.

Then the thread_fork() is called to create the a new thread structure for the child process.

What thread_fork() will do first is to allocate a new stack, get a new PID of the child, do some

address space copy from its parent, and it also copies the working directory.

After the new thread structure is set up, it will initialize the switch frame for the new thread.

But what the hell is a switchframe? This is actually the PCB(process control block) of

a thread. The sf registers of this "switchframe" will hold the arguments from

thread_fork(): a function poiner "entrypoint", the trapframe copied from the address space

of the parent process to the child process's, and some garbage "data2".

Then we call thread_make_runnable() to make the new thread runnable.

The funnction "entrypoint" will be implemented in syscall.c.

The child process will start at this function and free the trapframe passed to it.

It will create its own trapframe on the stack in its address space and sets up the

return values in the registers. It finally increment the program counter by 4 bytes and

calls mips_usermode to warp to user space.

Eventually, we will see fork returns twice:

0 and PID of child process.

This is my understanding so far, after a night without sleep. The next thing I will do is to

implement execv(), which is quite similar to runprogram().

OS161-Writing Fork(), part 1

2011-10-09T19:46:00.000-07:00

In assignment 2, we are asked to implement fork in the system os161.

It has been said that implementing fork() is the most difficult part in this assignment and is very crucial to understand how new process are created.

Despite the very details of the thread subsystem in os161, we will step through the process of the implementation of fork() in order to deepen our understanding of system calls.

fork() does the following things:

- it makes a copy of the invoking process and makes sure that the parent and child processes

each observe the correct return value.

- it returns 0 to the child and a new PID to the parent.

- the core of the fork() system call will invoke "thread_fork()" in kern/thread/thread.c

to create a new kernel thread

The child process should inherit exactly the same state of the parent at the time the parent

had when it made the system call.

By inspecting the code of "runprogram()" in /kern/syscall/runprogram.c, we can get some

insights of how fork() can be implemented.

runprogram() will show us how a program returns user space after a system call.

runprogram() takes a "string" (or char *) program_name and return an integer(EINVAL if error). loadexec() is the core code to load an executable into memory.

loadexec() will

- call kstrdup() to make a new name for the process

- call vfs_open() to load the program / open the file,

- call as_create() to make a new address space ,

- replace the old address spaces of the current thread with the new address spaces,

- call as_activate to make the new address space "seen" by the processor,

- call load_elf() to load the executable indicated by its argument "entrypoint", a virtual address

- call as_define_stack() to set up the user stack region in the address space, which make the

stack pointer point back to USERSTACK, the initial stack pointer for the new process,

- wipe out the old address space,

- change the current thread's name to reflect the new process.

After this, enter_new_process(), in /kern/arch/mips/locore/trap.c,

is called to warp to user mode. This function is used to go to user mode after loading an executable. It creates an ersatz (what the heck is this, figure it out later) trapframe,

sets the program counter to a virtual address,

stores the "argc" into register tf_a0, stores the pointer to arguments

into register tf_a1, and sets the stack pointer. Finally it calls mips_usermode(&tf) to enter

user mode.

Now we will go through the code of fork() step by step.

fork() takes two arguments: a pointer to trapframe an integer (the PID of the parent process).

It will first malloc some spaces in the heap to copy the trapframe, because we might return

to user level and make another system call, which might change the trapframe, before the

child runs. The child will free the copy of the trapframe in the heap. Then we call thread_fork().

Honestly, I have no idea how to implement thread_fork() from scratch. This is super duper hard for me. But...so what? I am going to get the jobs done anyway.

To create a new thread, call thread_create().

We will stick some magic numbers on the bottom end of the stack to catch kernel stack overflow.

Then we need to allocate some memory to the new thread and create a new PID for it.

Then we need to set up various fields associated with the new thread.

For example, we need to copy the virtual address space and current working directory from

its parent.

To be continued...

CSC300 Service Learning: Website for the Global Roots Garden

2011-04-07T16:41:00.000-07:00

I met with our service partner Sara and another classmate Andrew yesterday.
Up to this point, we have built a prototype of the website for the Global Roots Garden.
Andrew and I were both super busy during these two weeks. Fortunately, the website
does not require any fancy function. Web users can listen to the stories of the gardeners
by using the Google reader mp3 player embedded in the web page. Inspired from the website
http://mycitylives.com/, people can view the gardeners' profiles by clicking on a "seed" icon
spread on a image. They then will see the photo of the gardener who is telling the story so that people feel more connected to the story as if they are told by the gardener himself/herself.
I am also responsible for creating a different language version of the website, allowing people from different countries to access.

As a result, our contribution to the community and the neighborhood is positive. We can not see any change or consequence right away since the website is not online and the stories have not been uploaded to the server yet. However, our service partner Sara is quite satisfied with our cooperation. Due to the deadline of this course, our service also comes to an end. I hope this project will help foster the improvement of the cultural diversity within the city.

CSC300 Service Learning: Storytelling

2011-04-05T18:10:00.001-07:00

This should be posted a two weeks ago but I was too busy to write the thing down. I went to the the garden at St.Clair West & Bathurst to help our service partner, Sara, with interviewing a Chinese Woman, from Dongbei province in China. Surprisingly Sara learned Chinese before when she was teaching as a TA in Shanghai Jiao Tong University, in Shanghai.
Since Sara had difficulties fully understanding her words, she asked me to help translate the story and any questions/answers from the Chinese woman. This is very helpful for the story recording because there may be a chance the woman tell the story without understanding Sara's question. We still spent a whole afternoon to make sure the woman's telling the story relevantly. She mentioned her experience of growing food fifty years ago in China. She also told us what is her life like after she moved to Canada. She told us how different was the food grew locally in Toronto from the food she grew in Beijing. Eventually these stories will be visible to the public through the web. I was pleased that I helped collect the story and build the interface for more people to access to the story in this project. It was quite an amazing experience.

CSC300 Service Learning: Second Meeting

2011-03-16T02:26:00.000-07:00

The second meeting was on Wednesday 2pm, March 9. The attendants were Andrew, Mariyam, Sara and I. Prior to the meeting, I had a chance to read part of Sara's paper about the Global Roots Project. She also gave us a few links to the websites that record stories told about specific geographic locations. One similar project is known as the "murmur" project. People listen to the stories and get to know the histories and ancedotes of the local people. The "murmur" project unveiled the private truths and tales that make up the city. Information hidden from eyes and things being forgotten by the new generation are picked up and translated into the form of voices. I think this is something that people nowadays don't usually find in someone's blog or social networking spaces. Hence I'm provided a great opportunity to help improve the situation.

Our objective again is to help Sara with the project The Global Roots Project and get the audio recordings of the gardeners' narratives displayed within the garden and on the internet. More precisely, the Global Roots garden we provide services for is one of the two locations in Toronto that the Stop Community Food Center operates. People from different ethnic communities are given a 20-by-13 ft plot to grow non-local vegetables. There are different events going on each week for them to socialize. The design of the garden and the diversity of the plants tell the story of how people share their cultures. Inspired by the "murmur" project, the Global Roots Project will also record the stories of all the gardeners in all languages. The stories told in other languages other than English will be translated. Although it's suggested to listen to the story throughout the garden, we still need to build a website for the larger public.

During the meeting we discussed the rough idea of the website we are going to build. Andrew and I will be responsible for it. We consider to put a image of the garden with plots. Stories are wrapped in a tag or label or button scattered throughout the image like a geographic location in a map. By clicking the the tag/label/button, people get access to the audio files of the stories.
We still need to design the different level of the website. We also considered the possibilities to have interactive feature such as providing comments or feedback. However, such interaction may require a database in the back-end to store all the information sent by users and add more
complexity to the project.

CSC300 2011 Winter Service Learning, First Meeting

2011-03-03T15:12:00.000-08:00

Today Andrew, Mariyam and I met with our service partner, Sara, at Noir Cafe near The Stop Community Food Center. She briefly introduced The Global Root Project to us and brought us to the Stop Green Barn, located at St. Clair and Christie.

Our main duties associated with this project include building a website that host the oral histories of the gardeners in the neighborhood and creating the audio installation within the garden. The primary goal is to allow people in the community to get more familiar with the history and background of the local green food and urban agriculture. People may hear about the concept but they seldom have the chances to directly access to the stories behind the scenes. People get the source of information directly through listening to a short storytelling audio clip, which is more reliable.

The gardeners being interviewed by our service partner Sara come from all over the world such as Canada, India, China, Kenia, and etc. Most of them is able to speak English. People with different cultural background share their knowledge of food, gardening here.

Test 3 Q3 review - Problem Solving

2008-12-04T20:12:00.000-08:00

Below is the last question in test 3 i did hours ago. I wrote down the proof briefly which may not be that convincible, so i decide to prove it again.

Prove L(1*(0+e)1*(0+e)1*) = L2, the language has at most two zeros.

To prove the equivalence, we actually prove that for any element x , it can be represented by
L(1*(0+e)1*(0+e)1*) or L2. The former one looks a little bit complicated but actually it is possible to simplify it to make the proof much easier and shorter. By applying the distributivity, the transformation is going to be like:
L(1*(0+e)1*(0+e)1*) <=> L((1*0+1*e)(1*0+1*e)1*) , apply identity and annihilator for concatenation here, we get L((0+1*)(0+1*)1*), then apply idempotence of Kleene star, the simplest form is L((0+1*)(0+1*)).
Now, we are really just proving L((0+1*)(0+1*)) = L2.

In first part, we prove L((0+1*)(0+1*)) is a subset of L2.
L2 tells us how we rewrite L((0+1*)(0+1*)), that is to say, the number of zero is crucial.
It's definitely true by just looking at L((0+1*)(0+1*)), but we need demonstrate it with stronger reason. All cases include zero-free, one zero and two zeros. (0+1*) has either one zero or repetition of 1 or e. Then the concatenation of two (0+1*) has two zeros at most which satisfies L2. Then x \in L((0+1*)(0+1*)) implies x \in L2.

In second part, we prove L2 is a subset of L((0+1*)(0+1*)).
In this part, the setting for the typical elemtent x depends on L((0+1*)(0+1*)).
Since there are at most two zeros, i don't think there are too much things to worry about.
We just ensure x can be zero-free or with one zero or with two zeros.
x = (0+1/e/1*)(0+1/e/1*), (0+1*) is satisfying the language L((0+1*)(0+1*)) here.
Hence, the proof is done.

For such questions, once the languages on both sides are well understood, the proof will be just following the formal procedure.

Chapter Seven Review

2008-12-04T10:22:00.000-08:00

#############
Formal Language:
#############
Any set of strings can be empty, finite, or infinite.
Length of string: s, number of symbols in s, ex: "+"=1, "e"=0.

#############
Regular Expressions(Regex):
#############
Basis : empty, empty string, one-symbol character;
Kleene star can be used to restrict the pattern of a regex:
even or odd numbers of some characters;
Idempotence of Kleene star: R** = R*
Distributivity: (A(B+C)) = (AB+AC), ((B+C)A) = (BA + BC)

Proving equality of two languages => Prove mutual inclusion:
1. Analyze the pattern of a language and divide into pieces if possible;
2. Transformations: in general case, expand some terms to make up the equality;
3. Check from both directions, conclusion.

###
FSA
###
Proof procedure, induction:
Basis: x=e, &*(q_e,x)=q_e. P(e) true.
Induction Step: Assume x = x'a, assume P(x'). Analyze the cases.
In all cases, x = x'a and &*(s,x) = &*(q_e,x'a)=&(&*(q_e,x'),a)
according to our induction hypothesis.
Then using the transistions functions, we prove P(x') => P(x), in all cases.

####
NFSA
####
Difference: Each transition takes the machine to a subset of states rather than a unique
state.

Notes:
Every regex has equivalent NFSA.
Every NFSA has equivalent DFSA.

DFSA

2008-11-24T12:17:00.000-08:00

In some degree, the most challenging question in assignment 3 may be the last one.
I once got stuck on combing the two machines representing binary string with odd length and multiple of five respectively. I wasn't sure what were the exact steps using cartesian product. So i considered all the combinations of the cases of the third machine i want to construct.
That is exactly the result of cartesian product. Excluding the initial state, there are 5*2 = 10 states
for x = n mod 5 with odd/even length. These are the state invariants. Then We can see directly from some binary numbers and derive the transitions. Then the desired machine is fulfilled.
The proof of a DFA is straightforward. For me it is kind of a process of verifying each state go to the correct place via a path or an edge. Graphically, each state is a node with inputs and outputs.
Thus the transitions explain the correctness of traversals in a machine.

review of Week 10

2008-11-15T19:19:00.000-08:00

The annoying assignments, exercises, quizzes and term tests seem to be paused except for CSC236. This weekend i have to engage into the second last assignment with my partner. I also have a somehow big project of csc207 to worry about. Insipte of the workload of a computer science student, i now write for my 6%~11% of the final mark.
These two week we saw pretty much things about finite state automata and regular expressions. Regular expression is a descriptive way to express the language. We can design our own language with different alphabet using regular expressions. Through the example in the lecture, such as an alphabet of binary numbers containing even or odd zeros, i learned a logical procedure to analyze the syntax between various languages. The interesting part for me is the algebra on regexes. Without changing the language, one can apply some principles such as: commutativity, distributivity to the regular expressions. This simplifying process allows more variations on a language and it provides some interesting design patterns of a language.
Another thing is the DFA, or DFSA. The first time i saw it was in CSC148 when we were doing the graph algorithm. It seems there is quite a few connection from the DFA to graph algorithm. Machines of DFA accept their unique pattern of strings. We can easily find out whether a string is valid to the machine by traversing between the states. The hard part is how we construct a desired machine for a particular collection of strings. By observing the pattern of some strings, we need to derive some crucial parts of the machine like the state invariants and the transition functions. A graph is usually helpful to verify the state the next character heads is correct, which is to say, we need to carefully set our initial state, final state, states between and all the edges. Such things is really thoughtful.

After Test 2..

2008-11-08T10:19:00.000-08:00

Since there is always a lot of people there in the day section, i wrote the night section test.
I don't know how big the difference between the day section and night section test. They may follow the same patter pretty much. I didn't work out satisfying answers on the test.
About the palindrome, i remembered well that i did the same thing in CSC108 lab. But one thing
to regret is that i forgot the prove structure. I tried using complete induction but i didn't organize the frame well.
Related to the last question in the test, i really got a mess in my mind during the test.
I got frustrated when i could not figure out right away the main purpose of the function downward(n). Things happened and i got all blank in my brain. When i got calm down and refreshed my mind, i tried out some typical examples. Unfortunatley, i didn't realize that the loop invairant was sth like the floor of lgn until hours after the test. Anyway i cannot say i fail the test, at least i failed getting an insight on the subtle things.

More on iteration

2008-10-30T18:24:00.000-07:00

The 3-hour night version lecture is a real torture. For the example counter(m,n), i can't relate the loop invariant directly to the correctness of the program. It's weird that the b value is set to 6.
I tried pick two non-zeros natural numbers for m and n randomly. And the loop has to execute 6 more times to terminate after a and b decrease to 0 since b is assigned to 6 and c has to counter 6 more times. It may be necessary to use the loop invariant c = 7m + n to go to the postcondition, but it seems not to be that straightforward to be understood. Now i realize the importance of code design that make other people's life easier, for people who are learning how to prove loop invariant. Back to the loop invariant, i usually trace algorithm on simple example, like iterates for a few times and see what kind of changes are caused. As to me it's more helpful than just thinking of some fancy relationship between precondition and postcondition.
For more complicated loops, like nested loops, these things have to be done inside out. Prove termination and loop invariant in the very inside, then for any value of the loop outside, prove termination and loop invariant for outside loop. In the selection_sort example, the inside loop is going from index j=i+1 to the end of the list. Selection_sort is basically "selecting" a proper position for an element in the unsorted section of that list. I take a [4,2,3,1] as an example to run the loop. The inside loop actually helps me to evaluate a position by comparing the value of 4 to 2,3 and 1, then the outer loop moves to the next index and this easily sorts the whole list. But the inside loop may have k+1 iteration or may not. Since the value of the number could be equivalent. These "special" cases happened because of the postcondition, which is non-decreasing order here. Then it's not hard to prove the program "moves" and "compares" in some range.

Busy Week 8

2008-10-29T10:16:00.000-07:00

A2 was submitted a few days ago, but i didn't work out the first problem, neither did my partner.
I didn't derive a valid recursive formula for the 3rd problem as well. So i just proved it without a valid formula, which might lose some marks probably.
Luckily the 207 midterm was over this afternoon, i now have more time to review the materials Danny had talked about iterative programs.
It's again easy to start with, and more interesting than the previous sections. Obviously, we will use a lot of simple induction stuff here, for proving correctness of iterative programs. It's tricky to seek for a proper loop invariant, and it always takes times to go through the loop and see how this 'incomplete solution' works. Again, to prove the correctness, we carefully trace the loop and the changes each time it caused. This helps us to fulfill the implication from the ith to the (i+1)th loop.

the end of week 7

2008-10-24T20:52:00.000-07:00

Proving program correctness is always an annoying part, especially dealing with searching items and sorting items in an array or list. There are many conditions to consider for the program(most of them we have seen during this week were recursive programs) correctness.

The proof of correctness may be like: by induction, for size of the input,
prove precondition -> termination&postcondition. It seems the structure of
complete induction is well following recursive structure.

Then we go through the first few lines and if lucky enough we can proceed to the
annoying part of the recursive function. In this case, the recursive step leads us
to examine the whole function again with different input size, a smaller size.
We don't stop checking until we get the expected result - the post condition.
But how to split up the size so that it will look more straightforward and easier to
be checked? For the binary search, the way is to break into the middle of a list.
So there may be various ways and algorithms for various problems to shrink the
searching or sorting range. The next thing is to continue on executing. The case
must be carefully chosen otherwise some unexpected errors may cause the crush
of the program.

The proof is complicated at most of the time so as to ensure all the codes work from the
first line with the initial input. It saves us a lot of time to complement any cases or to fix
up any mistakes afterwards.

Lecture about Program Correctness

2008-10-20T15:55:00.000-07:00

Monday came, Danny didn't come.
A lecturer named Nick presented us a lecture about program correctness.
Nick started by the sentence "My program is correct." He talked about how correct a program
would be from different points of view. He spent some minutes on explaining the definition of conditions, the relationship between precondition and input, postcondition and output.
This helps us to recall what we have learned in CSC165.
Then he gave the very familiar example, binary research, to reinforce the concept on how a program would be correct in each step. One question(maybe just for fun, maybe not) he mentioned during the lecture was 'how do you crush a program', which sounds very illegal.
But at the same time, this is just the way to prove the program correctness backwards.
I believe if one can crush a program easily, then it wouldn't be too hard to prove correctness.
That is where you see right from wrong. So yes, let's enjoy crushing our programs.

Week 6

2008-10-18T21:41:00.000-07:00

This week we focused on analyzing the complexity of mergesort and did some unwinding and proof. The repeating substitution procedure is simple. In most cases, when n>some integer, according to the definition, we can easily get a formula from the right hand side. Since we want the f(n) or g(n) or whatever to decrease to f(0)/g(0)=1, the formula we eventually derive will be like a constant to the power of something plus something else. To make a conjecture, we just carefully define n, which is usually natural numbers with some restrictions. The divide-and-conquer strategy provides us a way of breaking big problems into smaller and smaller parts. Then the size will be small enought for us to directly solve. Well, at least with spliting up and solving one of the subproblems, the base cases, we can always get a few marks.

term test 1

2008-10-10T10:27:00.000-07:00

i used simple induction for all the three questions. Since i guess it would be easier to prove P(n)=>P(n=1) for the predicate in the three questions, except the last question. it seems it would be proper if i used complete induction to prove it. Similar problem i had seen before. since i was writing in a hurry, i just picked the most familiar technique for me to solve, which is simple induction. I was stuck when i was dividing the set into a part that can be applied with IH. The n+1 element took me a lot of time to derive the subsets containing it. I might be wrong on the answer since the induction step wasn't that successful. if there were 5 more minutes maybe i could do the induction step one more time and find out which number of subsets is going wrong.
Luckily the first two questions required less cases to analyze. i think i did well in the recursive one.

review for week 4

2008-10-07T17:43:00.000-07:00

The algorithm complexity part is usually thoughtful-provoking.
I didn't see big differences when i run a program on my laptop or some computers, but i did see the way that much fewer steps generated by applying recursion. Well, iterative functions come more naturally for me though great efficiency recursion has. Everytime i'm analyzing recursive functions, my sight jumps back and forth. Thought it makes my codes neat, it usually takes time for me to solve a problem recursively. We also did a bit of unwinding, estimating the time complexity of binary search and the proof of it.

how wrong would a proof be

2008-09-26T08:13:00.000-07:00

I'm given some ideas of how a induction "traps" is raised by today's lecture. As to me, this happens that i write down the proof before convincing myself that each step follows the previous steps rigorously. We know that there are base case, induction hypothesis and induction step in a formal induction proof. The subtle may be made by missing one of them or by saying something that mismatching the fact. I sometimes make mistakes by making implicit assumption, and the result is that i couldn't reach the conclusion since it is incorrect at the beginning. To understand the statement is also important since the predicate is chosen from the statement. For the last problem on assignment 1, we should carefully remain the property of a ternary tree when we make our assumption. Good luck for the assignment 1.

working on practices

2008-09-16T17:46:00.000-07:00

By reading the textbook, the simple induction and complete induction seem not that confusing. To make sure that i understand the definition and examples, i redid the proof in lecture and in the textbook. It's really important to find the right base case: is this case the very fundamental of the problem? do we need more base cases?
The scratch work helps a lot because it's always convinent to make changes when i look backwards in the problem. All of the mathematical problems we've encountered in this course are solvable. The key is always to know what kind of strategy to use corresponding to the problem and follow it step by step.
For example, we want to find out the possible unit digit that 3^n can have by using simple induction. The method is specified as simple induction. Then we just need to figure out the base case and the induction step. It's easy to find the P(0). Then we have to determine P(n) and let it imply to P(n+1). There are different predicates in different questions. We must make sure we understand how does P(n) work here so that it leads exactly to P(n+1). It's really helpful to correspond our assumption to its inductive case and understand the property. When transforming 3^(n+1) into 3*3^n, slight change is made but huge differnce occurs. We now can see the answers explicitly because 3^n had been extracted. This means we have proved our inductive case correctly.

Week 1 in CSC236

2008-09-15T16:57:00.000-07:00

Since i took CSC165 in the summer, this is my first time to use SLOG.
After reading the SLOG handout, i kinda understand what is it now. Compared with the bulletin board, SLOG is a better platform to post one's opinions, with more details and informations.
It's an exciting thing that we can record what we've learned and what we've doubted. By viewing others' blog we can try to explore a different way to think the same problem. That's a good thing.

The materials in the first week were not too much and not that confusing. So far we took a review about the simple induction and strong induction by dealing with some mathematical statements. They seem quite familiar, but the problems are always tricky.
The proof of recursive program and program correctness might get harder in the future. For now, i will try my best to conquer any difficulties in the most basic part.