Week 12: A week in review

So.. This will be dedicated to a critique on my progress... and oh hey look the existence of other people.

I've spent almost two hours reviewing other classmates' slogs, all I have to ask is how do you and the professor manage?

For the 165 weekly quizzes, I am beginning to get stuck on proofs involving big- theta when there are multiple variables and functions being compared those involving the proof of a limit which I need to review because I've somehow forgotten it... These, I can only improve on through practice with past tests. I keep doubting myself when I answer a question, then record a second attempt that is usually wrong when I approach these problems. Practice makes perfect.

I could have posted on other people's slogs a lot more, it's really interesting to see how other people think and go about in approaching a problem to learn different techniques. Uh so to be honest I kinda of regret not talking enough in my tutorial classes to ask people for help and questions.
Either its the gender gap-
       *been there done that in high school...(Let's just say I know way more than I need to know)
       *This year...
       *goes to first CSC148 lab
       *looks beyond monitor
       * sees person staring with dumbstruck face*(twitches)
- or I'm being lazy or shy I don't know, but I need to overcome that dumb barrier otherwise I'll just be wasting a lot of good opportunities in the future -____- and this joy-ride is just beginning...
 
I have stuck with two close friends in particular to do the assignments with and I'm beginning to only see more and more why I need to put myself out there a bit more. Learning from others is key, because the days without their help will come sooner or later, and I'll suffer if I keep relying on them of course, especially as a girl, I need to get used to the gender gap (and find a way of how to survive) that has only increased even further than as compared to my high school CS courses.
By doing group work, I realize I'm horrible at trying to figure out what I'm confused and I have some difficulty figuring out a way to form a question for it O_O. I think I know it, but I don't, but then again, this just pushes for the need to talk with other peers a lot more to problem solve. Looking at the student slogs and Piazza would have been a good place to start, because it's easier to get away with, asking for feedback in a slightly anonymous way. Out of all of the slogs, there were a few that appealed to me for their different aspects.

http://forcsc165.wordpress.com/

This person's slog is pretty informative, in terms of the way they relate the 165 class concepts to a few of their other courses to programming languages and compilers. They have well structured attempts to solving the in class problems like the diagonal problem. Their posts are straight and to the point unlike mine which include ranting. If I knew this person I would have learned quite a bit from this person if I knew them in person aside from 165 content, judging by the connections they make to other CS-related topics- especially those of their A2 post.

http://exp-csc165.blogspot.ca/
Dannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnngg

Well ok A+ to this person for their slog LOL. Well if not from the professor, then an A+ from me, despite the fact that my grade aren't sufficient enough to send over those percentages.

This person's slog is filled with problem solving techniques, I'm sorry I have no interest in the chess section of their blog, but everything else on here has a very detailed approach on how they solve their problems. This person's posts aren't too bland either so it keeps you reading for more on answers and little tips to look for in surviving 165, hah they even mentioned the Project Euler page, which is a pretty good resource with those familiar  familiar 50000003204893242378493278 programming problems to solve and ponder about. The slog is a worthwhile read.

Now to sum it up after reflecting on what I could have done in this course to improve, I wonder what it'll be like taking CSC 236 next year...

Problem Solving: Paper Folding

Understand the problem:

Predict the sequence of up and down folds for any number of times you fold a strip of paper in half

Devise a Plan

1. Hypothesize what pattern will occur in the sequence of folds produced for each folding         operation made.
2. Observe and record the folding operation, folding the paper in half from 1 to 5 times, then record the number of 'half-folds' and their up and down pattern of creases produced in an organized  table.
3. Look for a pattern betweens between each sequence of up(U) and down(D) creases made    from each folding operation carried out and compare them with previous sequences made before the current fold operation. Note down and verify your conjectures with real results and simulations from your observation table in Step 2.
4. Create and test an algorithm on how you can predict the sequences produced from executing a number of n folding operations.
5. Simulate the folding operation in a Python program.

Carry out the plan

1. HypothesizeBecause the creases of previous folding operations are permanently embedded on the strip of paper, the next sequence will depend on the sequence of the previous folding operations. This hints to the fact that the folding operation is recursive. The next result depends on the previous results that ultimately depend on the first result, the smallest, simplest instance of this folding operation, the base case. When the folding operation is carried out once a single downward crease is made.


2. Observe and record
By making multiple folds, we can produce the following table of upward(U) and downward(D) creases occurring in each fold sequence.

3. Look for a pattern

Looking at the table, we can see that the first fold reappears in all sequences produced after      
the first folding operation. The 'D' fold can be found in the very middle of each sequence.

If the first downward fold recurs throughout all sequences, then there should be more
 reappearing patterns. Lets look for them...

The sequence from making n = 1 folds, DDU reappears. Also, notice how when we fold for          

more the strip of paper more than once, part of the fold sequence before the first D produced          

when n = 1, is reflected on the paper strip to the right of the first D crease, in a reversed  

pattern. The D made from when n = 1 acts as a 'mirror' in which everything to the left of D 

is reversed in folds, going from D -> U or U -> D, producing a 'reflection' on the right side of

mirror D. 

D recurs through all sequences. Our hypothesis is true.

In our example, the sequence DDU for n = 2 reappears in all other sequences for n > 2.
DDUDDUU, the sequence of n = 3 reappears in sequences for which n > 3...
The same thing occurs for the sequence n = 4, n = 5 and so forth.

Now what importance does this have?

Parts of the folding sequences enclosed in the same coloured rectangles are identical patterns that repeat from the previous n-1 before it.

we can see that...

4. Create and test an algorithm

- our simplest case of the folding operation is when n, the number of half-folds made on the strip of paper, is n = 1, the sequence produced is D

- Notice that the 'left pattern' to the left of the mirror D (produced from n = 1) is D, which is reflected(D changes to U), producing the 'right pattern' to the right of the mirror, U.
But, where do we get the left pattern from?
The entire previous sequence becomes the new left pattern.

Knowing these facts, we can create a rough idea that:

- resulting fold sequence =         left pattern           +       D       +          right pattern

                                       previous sequence           mirror          reflection of left pattern

Testing...
If this is so, knowing that when n = 2, a sequence of DDU is produced.
Then, for n = 3:
     - the left sequence should be DDU, the previous sequence in its entirety,
     - the mirror is D as always
     - the right sequence, generated by 'reflecting' the left sequence is: UUD
     - when 'reflecting' a sequence, you reverse the pattern sequence and change U or D's to their  
       opposites**
So the final fold sequence for n = 3 is: DDUDUUD
Checking our observation table, this pattern generated is correct.


Testing our formula to produce a sequence for n = 3 will match without error if true.

Given n = 3 produces a sequence DDUDUUD,

Then for n = 4, the sequence should be:
DDUDUUDDUDDUDUU,
which matches the real results according to the observation table.

Then, for n = 5, the fold sequence should be DDUDUUDDUDDUDUUDDDUDUUDUUDDUDUU,
which is correct.

5. Simulate

We can create pseudo code from this summary to structure the Python program for this problem:
=======================================================================
Pseudocode
fold_sequence(number of half-folds):
      sequence = ''
      mirror = D
      if number of half-folds == 1:

            sequence = D
      if number of half folds > 1:

            sequence += previous fold sequence + mirror + reflection of previous fold                      
                      #      ^                                               sequence
                      # recursive call here
      return sequence

reflect(fold sequence):''' Some helper method to 'reflect' fold sequences.'''
    reflection = ''
    for every character in fold sequence:

        if character is D:

            add U to reflection
        else:
            vice versa of above

        reverse reflection
return reflection
=======================================================================Python Code

DOWN = 'D'

UP = 'U'

MIRROR = 'D'

def gen_fold_sequence(n):

    ''' (int) -> str

    Return the sequence of upward(U) and downward(D) creases given the number

    of half-folds.

    '''

    sequence = ''

    if n == 1:

        sequence += MIRROR

    elif n > 1:

        left_pattern = gen_fold_sequence(n-1)

        sequence += gen_fold_sequence(n-1) + MIRROR + reflect(left_pattern)

    return sequence

def reflect(s):

    ''' (str) -> str

    Return a reflection given s, the sequence.

    '''

    reflection = ''

    if len(s) >= 1:

        for char in s:

            if char == UP:

                reflection += DOWN

            else:

                reflection += UP

    return reflection[::-1]

if __name__ == '__main__':

    for i in range(1, 6, 1):

        print(gen_fold_sequence(i))

Counting sheep doesn't work.

Week 11

Man, this week's topic on the Halting problem truly is confusing. Making  a program that can predict when all other programs in the universe could halt, gee whoever makes that, we should make a new religion for them and bow down to them as a new God, but I don't think that'll be happening anytime soon...

Anddd back on to Earth the class lectures' examples were sort of confusing it first, but I guess it's the idea of being a self referential you think of:

immediately makes it so. Imagining how many times the functions call themselves over and over...a belly button in a belly button in a belly button in a belly button in a -oh look there's lint- return 42 (the meaning of life lolwut...) -is a little strange.

But then I reread the code again for the navel_gaze example and found that it's actually quite simple, it's just an infinite loop which never actually reaches the return 42 line, so when you call it upon itself a check for H(navel_gaze, navel_gaze), and of course using H() on another 'inner' execution of navel_gaze never actually halts, so an infinite loop occurs for the while H() line in the 'outer' function of navel_gaze, which then infinitely loops again. In Python though, which stops first? The inner while loop of navel_gaze in the H(navel_gaze_, navel_gaze) line or the outer while loop?

The hash function used in halt_0 has a bit strange because it was my first time seeing it in Python. The Python dictionary structure uses the hash function right? I almost forgot what hash-values and tables were and it was a huge reminder that I need to review my Java again because it'll be introduced in my second year of CS... (argh the amount of syntax...)

What I'm wondering though is how exactly we're going to be tested on the Halting problem on the final exam for this course. Will there be something simple as determining whether a program's counting is 1-1 or onto, or would it be something a bit more difficult, like predicting how a program will run another inner function and reduce to that same inner function(like the daunting fifth question on A3)?
For now, though I guess I'll refer to the course notes pdf on how to format a proof for it...

Week 10

*warning I typed an essay*

*Gets back T2
Yepp, I make careless mistakes
I COULDN'T EVEN NEGATE THE STATEMENT PROPERLY...
OF COURSE DIVISION PRODUCES A NON-NATURAL NUMBER

WRRRRRRRRRRRRRRYYYYYYYYYYYY

As for week 10, I finally get to see the guts and details of how math is directly involved in piecing together a program's complexity and giving a visual idea of how it's run time may be optimized further. The proofs have now begun to finally pick up on math, involving our first-year calculus concepts and leading more into the gory details of how a proof can work and it's beginning to make more and more sense, but of course this is only first year. Some of the proofs have become daunting to understand with the big theta formula introduced but I'll just have to get used with imagining multiple graphs I guess...

 I'm still wondering how I should go about choosing my courses for CS in my second and future years to come, because it becomes split between technical CS or theoretical...

I really do like math and have sat with it in front of my face every Saturday for 10 years, trying out different math textbooks to a few university handbooks and some geometric proofs, but my relentless habit for making careless mistakes is always getting in my way -____________________________- for getting those good marks in my classes. I've always made a tonne of mistakes in those Saturday math classes, they served content that was sometimes a few years ahead of my elementary school curriculum, then I'd do the assignments, probably get like only 4 our 20 of the questions right, but then run back and correct them all ASAP always trying, and I still don't ever hate math. I have a long long record of silly mistakes -_-, no matter how serious I am, they seem to be resurging back up again in my school work though...

*Every time I look at my T1*: "Wah-ok was I drunk?.. How did I not get this? -.-"

*T2*: "...How did I..."
*-5 marks

*If you really think you're going to die reading this, skip this section and scroll past the ===*

========================================================================

BECAUSE I'M PRETTY SURE THAT I CAN...
ASSUME THAT Logics is pretty hard to do
               THEN ASK: should I work with CS's practical/technical uses instead?

               THEN ASK: (it's-first-year-I-did-not-take-a-lot-of-courses-to-say-that-I-want-to-major-or-
                                      specialize-in-say-CS-or-STATS-and-I-have-to-decide-on-a-POSt-soon)

               THEN CONSIDER (the job profits and omg-am-I-going-to-die-in-the upper-years?  yay-I-will-          
                                               be-broke-after-graduation)

                 # lose marks for this proof structure
                THEN ASK: Will I have a cubicle job? How fun are cubicle jobs? *twitches
THEN unresolved answer

========================================================================

So uh what are some  further applications of CS that use intensive logics and proofs, aside from dealing with a program's efficiency?

What careers does it typically involve?

Any hints as to which 165-ish courses are the most valuable to take for second year?
(CSC236/240 introduces Computation Theory, CSC 260 sounds interesting?)
(p.s .financial math and biology scare me...... Economics sounds... ergh...and I'm a very visual person)

... versus the courses focussing on CS's practical uses, or related courses outside of the CS department(example: Math)

Since this kind of logic deals with efficiency, that butts in a lot with managing databases and information, is there going to be a lot of hardware courses that I'll have to take(nuoooooooooooooooooooooooo)?

If you can recall...what were some mixes of courses past students took that were logic intensive?



Congrats you survived.
Thanks for reading my huge ugly essay.

Week 9

There was not too much difficulty with this week's content.

Today's midterm was not too bad, as much as the first midterm, it actually seemed a bit easier.
Though, because of this week's midterm I am a bit behind on week 9's lectures on proofs with  Big-Oh
notation. I think the best way for me to catch up and understand them quickly will be a visual approach using graphs and a little review on the definition of limits in calculus will help.

Week 8

Alrighty uh so far this week's Assignment 2 was actually pretty bearable, more so than the first one. The only difficult thing was how to solve the actual proof itself, but I think my group did pretty well on it except for the last question.

We were debating really loudly on how to answer question 6 and in the end they picked a sample number representative of real numbers, like 2, to prove that all elements of a set of real numbers have that property that they proved o_O.  Usually when you prove a statement that says "for all x in set  S", you usually prove it by using and manipulating variables representative of the elements of the set rather than picking actual values right? Because there is a possibility that the number you chose just happens to have with a unique weird property that may not be a good representation of all other elements in that set..


Aaaaaaaaaand I just read the sample solution to question number 6... Exactly what I thought..
 HOLY CRAP
WHY DOESN'T ANYONE LISTEN TO ME OMG THIS HAPPENED FOR THE FIRST ASSIGNMENT TOO
I HAD THE EXACT SAME PROOF WRITTEN DOWN
I WAS RIGHT AJKSDHFDJKFHJKASDHFJKASDHJFKHADSJCNJKSDBNCJKNXZMVNCZXMNVJCMKSNZVJKNDFVJKFASNVJNADKVNJWDKNVJNASFVKBNFJV JKASDNVJDVJADIVJBIKDFVBHFBHVBDHDBVHBDHVBHDBVBHDSbvHBDSZBCXHBHCBXDHVBHCHDBHCBHBVBdhVBDHbVHDBHVBHDBVHCBJDSbHDBSHBDSJVCHSDBVHSDVJDS

*flips table
ARGHHHHHHHHHHHH


Uhh... so yah complexity of a program...
What is a Loop Guard(LG) in a program? (Refer to Friday, March 8th lecture)
When writing an equation like 4n^3 + 3n^2 + 2n + C, where C is a constant,
How do you "overestimate" to rewrite this expression in Big-O Notation?
I know you take the term with the greatest degree, but in the last slide of Friday's lecture, why is the coefficient of this term the sum of the coefficients of the other terms? I believe it resulted in O(n^3), I'm not entirely sure, the slides are not exactly up yet..