CSC165H1 SLOG7 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG6

In this week, professor first introduces some scary announcements which are that A2 will be due on next Tuesday and test 2 will be held on the day that is followed. Although I think CSC165 is a challenge course for me, I do not consider dropping the course.

Tips for Assignment2

When we try to prove a statement with multiple quantifiers, there are some useful tips for us to solve the problems. For example, the symbol which indicates all can be written in to ‘assume generic’ in the process of proof. The symbol which means any can be treated as ‘pick’ or ‘let…be’. Moreover, when we see the statement of ‘if P then Q’, we can easily change it into assume P then Q. These tips have its capabilities to make proofing easily.

Lecture of this week

This week’s lecture is based on the definition of ‘O’ and ‘Ω’ and the worst case analyses of two algorithms.

The definition of ‘O’ and ‘Ω’

Form last week’s lecture we have known that O (n^2) means a set of function that grow no faster than O (n^2). Assuming we have a function ‘7n’, which is a linear function; therefore, the function ‘7n’ must be included in the set of O (n^2), because the function ‘7n’ grows no fast than O (n^2). There is another element which has to be presented first which is the breakpoint B. Breakpoint is very simple to understand by using graph to imply. As image 1 indicates that the function f (n) is at the lower position compared with the function cn^2 after the breakpoint B; so the purpose of breakpoint B indicates that after break point B, if f(n) is upper-bounded by cn^2, then it must grow faster than cn^2 and if f(n) is lower-bounded by cn^2, then f(n) is slower than cn^2, no matter f(n) is at what position before breakpoint B. after introducing the breakpoint B, the formal definition can be written in this way: a function f(n) is in O (n^2) if and only if .

The definition of ‘Ω’(n^2) is the opposite version of ‘O’(n^2) which is set of functions that grow no slower than n^2; therefore the definition could be written in this way:

This is image 1

Analyzing a sorting algorithm

A sorting algorithm basically means that grow a sorted list inside an unsorted list. For example, an unsorted list which is [1, 3, 4, 5, 2], through sorting algorithm, this list must be written into this way: [1, 2, 3, 4, 5]. The working principle is removing an element from the unsorted part and inserting it into the correct position in the sorted part.

In conclusion, this week’s lecture and tutorial went very well, because I can see my improvement in this week. Professor slows his speed of processing the lecture which makes me much comfortable and confident to learn.

Seventh slog

Mingyu Liu