Week 11 of Coding

Assignment 2

This in fact was not a really hard assignment, it only has very straightforward for loops and recursions. So I went on the web and looked over more background information about regular expressions.

Firstly, this complex syntax is used to check whether a given string matches or contains a given pattern. But it is not this simple, it has a flexible system that allows check upon a pattern not just fixed characters. Like in the assignment, we could match a symbol to multiple number of spaces.

It consists of various symbols and patterns,

a, X, 9
ordinary characters just match themselves exactly. 

. ^ $ * + ? { [ ]  | ( ) 
meta-characters with special meanings (see below)
 
. (a period)
matches any single character except newline 'n'

w    
matches a "word" character: a letter or digit or underbar [a-zA-Z0-9_]. 
It only matches a single character not a whole word.

W 
matches any non-word character.

w+
matches one or more words / characters

b 
boundary between word and non-word

s 
matches a single whitespace character, space, newline, return, tab, form

S 
matches any non-whitespace character.

t, n, r 
tab, newline, return

D
matches anything but a digit

d 
matches a decimal digit [0-9]

d{1,5}
matches a digit between 1 and 5 in lengths. 

{n} d{5}
matches for 5 digits in a row

^
match the start of the string

$
match the of the string end

*
matches 0 or more repetitions

?
matches 0 or 1 characters of whatever precedes it

 
use . to match a period or  to match a slash. 

With these 'rules' I believe they can compare any complex syntax in an efficient way.

The regular expressions also have some methods such as search, sub, compile.

Search is just for searching a regex pattern.

sub replaces occurences of certain sub-strings.

compile in my understanding is putting patterns together to build an object that is necessary for searching or matching.

Week 10 of Coding

MIDTERM 2

it was a really frustrating experience writing this test. I expected everything from the second half of our syllabus like binary search tree, pre-order, in-order traversal, and the big-Oh especially.

```````````````
Note: tree traversal is a systematic way of going through each node of the binary tree. Usually used for searching a node.

Pre-order traversal

1.root
2.left child
3.right child

Post-order traversal
1.left
2.right
3.root

In-order traversal
1. left
2. root
3. right
```````````````

Big-Oh is basically just a count of how much work to go through for each algorithm.
If an algorithm counts how many numbers are in a list, this is O(n), because it just counts n numbers.
An algorithm that looks for an x in list A that is also in list B takes O(n squared). because for each item in A going through, One has to look for at most n times in list B that matches.
```````````````

Anyhow, the test was mostly about recursions which I am worst at. I took the first 15 min thinking about what I can grab from mid-air. I don't think I've received a good mark on it, but I do know where to work on for my final now. The good thing was I was not completely blank about the questions, but it just took me longer than usual to work them out.

Week 9 of Coding

There are many ways to sort a piece of data according to its complexity and desired organization. I'm not talking about the sort method that is build in python. There are in fact complex algorithms coded just for sorting.

```````````````
Bubble Sort

numbers with index: 0 - 1- 2- 3- 4 - 5

1.compare every pair of numbers in turn ( 0 and 1, 1 and 2)
2. switch around if bigger one in the front
3. the biggest number would end up at the back after a number of switches.
4. redo the comparison from the beginning.

this takes huge amount of time, because it requires going over n comparisons for n numbers in the list and then n rounds in total.

```````````````
Selection Sort

this is better than Bubble sort in that it only makes one 'comparison' each round.

1. find the biggest number of the list.
2. place at the back
3. repeat

```````````````
Insertion Sort

Troublesome as well, but works in a new way from the two above.

numbers with index: 0 - 1- 2- 3- 4 - 5

1. assume number at index 0 is sorted
2. compare index 1 to 0, switch if smaller one at the back
3. assume index 0 and 1 are sorted sub-list
4. compare index 2 to each number in sub-list and make switches.
5. now index 0, 1, and 2 are the sorted sub-list
6. repeat

This is like bubble sort, it make n comparison at most for the n numbers in list, and then repeat for n rounds.

```````````````
Merge Sort

I always thought that this is a hard concept. Because it is much different from any other sorting method.

1. split the list in half
2. split each sub-list in half (until you cannot split anymore)
3. sort the numbers in each sub-list
4. merge with the other sub-list when splitting on the upper level before. Sort it
5. continue to merge all sub-lists

Week 8 of Coding

Now comes my favorite part of this class, the binary tree. This is a data structure that builds upon linked lists. Simply, linked lists are one way with one pointer, like a chain. On the other hand, binary tree is more complicated with at most two branches under each data. One can even say that linked lists are binary trees but with one branch all the way. Of course there might be other tree structures with more than two branches, but what we are learning now is only the basic type.

```````````````
We still start with a 'linked list'-like structure, only with more parameters. Data is still the value we are looking at, left and right are simply named for the two branches the data connects to. Like a family tree, the data on top is a parent, and it has left children and right children.

class Node:
      def __init__(self, data, left, right):
           self.data = data
           self.left = left
           self.right = right

Of course there has to be a tree top in the whole binary tree to start with, we call it the root.

class BinaryTree(Node):
     def__init__(self):
          self.root = None

```````````````
Binary Tree has a much better use on data with multiple branching factors. A linked list may be a string of numbers. The Binary Tree would be able to give a tree of numbers differentiating odd and even, big and small. Normally the tree data is in a certain order so when we look for a particular piece of information, we know to look into the left branch or the right. (suppose left is for data smaller than value X, right is for data bigger than value X).

Inserting a node would not be hard in this sorted structure.
```````````````
inserting an object into the tree

def insert(self, root, object):
     if root == None:
          root = Node(object)
     else:
          if(object <= root.data):
               root.left = self.insert(root.left, object)
          else:
               root.right = self.insert(root.right, object)
 
the first if clause is to place the object where should be placed.