Binary Search Tree❤

-Definition:

a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree.





-Properties:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. The left and right subtree each must also be a binary search tree.
4. There must be no duplicate nodes.

1&2 improve the efficiency, which allow us to ignore half the list, either left or right. ❤

 -Specific:
class BST:
    """Binary search tree."""

    def __init__(self: 'BST', root: BTNode=None) -> None:
        """Create BST with BTNode root."""
        self._root = root

    def __repr__(self: 'BST') -> str:
        """Represent this binary search tree."""
        return 'BST(' + repr(self._root) + ')'

    def find(self: 'BST', data: object) -> BTNode:
        """Return node containing data, otherwise return None."""
        return _find(self._root, data)

    def insert(self: 'BST', data: object) -> None:
        """Insert data, if necessary, into this tree.

        >>> b = BST()
        >>> b.insert(8)
        >>> b.insert(4)
        >>> b.insert(2)
        >>> b.insert(6)
        >>> b.insert(12)
        >>> b.insert(14)
        >>> b.insert(10)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
    """
        self._root = _insert(self._root, data)

    def delete(self: 'BST', data: object) -> None:
        """Remove, if there, node containing data.

        >>> b = BST()
        >>> b.insert(8)
        >>> b.insert(4)
        >>> b.insert(2)
        >>> b.insert(6)
        >>> b.insert(12)
        >>> b.insert(14)
        >>> b.insert(10)
        >>> b.delete(12)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(10, None, BTNode(14, None, None))))
        >>> b.delete(14)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(10, None, None)))
        """
        self._root = _delete(self._root, data)

    def height(self: 'BST') -> int:
        """Return height of this tree."""
        return _height(self._root)


def _insert(node: BTNode, data: object) -> BTNode:
    """Insert data in BST rooted at node, if necessary, and return root."""
    return_node = node
    if not node:
        return_node = BTNode(data)
    elif data < node.data:
        node.left = _insert(node.left, data)
    elif data > node.data:
        node.right = _insert(node.right, data)
    else:  # nothing to do
        pass
    return return_node

def _find(node: BTNode, data: object):
    """Return the node containing data, or else None."""
    if not node or node.data == data:
        return node
    else:
        return (_find(node.left, data) if (data < node.data)
                else _find(node.right, data))


def _delete(node: BTNode, data: object) -> BTNode:
    """Delete, if exists, node with data and return resulting tree."""
    # Algorithm for _delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node
    return_node = node
    if not node:
        pass
    elif data < node.data:
        node.left = _delete(node.left, data)
    elif data > node.data:
        node.right = _delete(node.right, data)
    elif not node.left:
        return_node = node.right
    elif not node.right:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = _delete(node.left, node.data)
    return return_node


def _find_max(node: BTNode) -> BTNode:
    """Find and return maximal node, assume node is not None"""
    return _find_max(node.right) if node.right else node


def _height(node):
    """Return height of tree rooted at node."""
    return 1 + max(_height(node.left), _height(node.right)) if node else -1


class BTNode:
    """Binary Tree node."""

    def __init__(self: 'BTNode', data: object,
                 left: 'BTNode'=None, right: 'BTNode'=None) -> None:
        """Create BT node with data and children left and right."""
        self.data, self.left, self.right = data, left, right

    def __repr__(self: 'BTNode') -> str:
        """Represent this node as a string."""
        return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
                ', ' + repr(self.right) + ')')

    def is_leaf(self: 'BTNode') -> bool:
        """Is this node a leaf?"""
        return node and not self.left and not self.right
 

27.8. Glossary

binary operator

An operator that takes two operands.

binary tree

A tree in which each node refers to zero, one, or two dependent nodes.

child

One of the nodes referred to by a node.

leaf

A bottom-most node in a tree, with no children.

level

The set of nodes equidistant from the root.

parent

The node that refers to a given node.

postorder

A way to traverse a tree, visiting the children of each node before the node itself.

prefix notation

A way of writing a mathematical expression with each operator appearing before its operands.

preorder

A way to traverse a tree, visiting each node before its children.

root

The topmost node in a tree, with no parent.

siblings

Nodes that share a common parent.

subexpression

An expression in parentheses that acts as a single operand in a larger expression.

Linked Structures

Linked lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo.

A linked list is considered a recursive data structure because it has a recursive definition.

A linked list is either:

1. the empty list, represented by None, or
2. a node that contains a cargo object and a reference to a linked list.

i.e. sequence of nodes, each with a value and reference to next node.(Use 'next'?)

e.g.

class Node:
    def __init__(self, cargo=None, next=None):
        self.cargo = cargo
        self.next  = next

    def __str__(self):
        return str(self.cargo)

 

24.11. Glossary

embedded reference

A reference stored in an attribute of an object.

linked list

A data structure that implements a collection using a sequence of linked nodes.

node

An element of a list, usually implemented as an object that contains a reference to another object of the same type.

cargo

An item of data contained in a node.

link

An embedded reference used to link one object to another.

precondition

An assertion that must be true in order for a method to work correctly.

fundamental ambiguity theorem

A reference to a list node can be treated as a single object or as the first in a list of nodes.

singleton

A linked list with a single node.

wrapper

A method that acts as a middleman between a caller and a helper method, often making the method easier or less error-prone to invoke.

helper

A method that is not invoked directly by a caller but is used by another method to perform part of an operation.

invariant

An assertion that should be true of an object at all times (except perhaps while the object is being modified).

Object-Oriented Programming & Recursion

This week Task:

As well as your regular entries in your SLOG, this week I'd like you
to write two short paragraphs: one on Object-Oriented Programming, and
one on Recursion.
Each paragraph should state, in your own words, what the concept is
and why it is useful (or not) for computer scientists.


 Object-Oriented Programming:

 Object-Oriented Programming is like we can come up with concepts("objects, instances of classes"), also have approaches attributes to it, which is known as methods.  Languages like C++, Java are example of objext-oriented programming language. This programming paradigm makes programming more flexible and extendable as well as make people enable to simply design something and use it.


Recursion:

Recursion is like a method that repeatedly call itself.
For example, fibonacci sequences( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...), we have maths definition:


 

we can write in python like,

def fib(n):
   if n == 1:
      return 1
   elif n == 0:   
      return 0            
   else:                      
      return fib(n-1) + fib(n-2)

so we have 

fib(0) = 0

fib(1) = 1

fib(2) = fib(1) + fib(0) = 1

fib(3) = fib(2) + fib(1) = 2

...

This approach is very convenient in programming, as it makes it possible to 

'define an infinite set of objects by a finite statement' because of repetitions. 

Recursion & Testcase

1.Recursion:

a).Recursion means “defining something in terms of itself” usually at some smaller scale, perhaps multiple times, to achieve your objective.

i.e. functions can call themselves to solve smaller subproblems. 

e.g. Fibonacci numbers

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  for n >= 2

def fib(n):
    if n <= 1:
        return n
    t = fib(n-1) + fib(n-2)
    return t 

b). ! Nested-lists:

# some recursive functions on nested lists

def nested_depth(L):
    """
    Return if L is non-list, or 1 + maximum of depths of elements list L.
    Not defined for infinitely nested lists.

    >>> nested_depth(3)
    0
    >>> nested_depth([1, 2, 3])
    1
    >>> nested_depth([1, [2, 3], 4])
    2
    """

    return (1 + max([nested_depth(x) for x in L] + [0])
            if isinstance(L, list) else 0)

def rec_max(L):
    """
    Return the maximum number in possibly nested list of numbers.

    >>> rec_max([17, 21, 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    """

    return max([rec_max(x) if isinstance(x, list) else x for x in L])


if __name__ == '__main__':
    import doctest
    doctest.testmod() 

2.Testcase: 

When choosing test cases, consider the following factors:

• Size
  For collections (strings, lists, tuples, dictionaries) test with:
  • empty collection
  • a collection with 1 item
  • smallest interesting case
  • collection with several items
• Dichotomies
  Consider your situation:
  For example:
  • vowels/non-vowels
  • even/odd
  • positive/negative
  • empty/full
  • etc.
• Boundaries
  If a function behaves differently for a value near a particular threshold (i.e. an if statement checking when a value is 3; 3 is a threshold), test at the that threshold.
• Order
  If a function behaves differently when the values are in a different order, identify and test each of those orders.

There is often overlap between the categories, so one test case may fall into more than 1 category.

 - import unittest

 - if __name__ == '__main__':
     unittest.main(exit=False)

 

18.7. Glossary

base case

A branch of the conditional statement in a recursive function that does not give rise to further recursive calls.

infinite recursion

A function that calls itself recursively without ever reaching any base case. Eventually, infinite recursion causes a runtime error.

recursion

The process of calling a function that is already executing.

recursive call

The statement that calls an already executing function. Recursion can also be indirect — function f can call g which calls h, and h could make a call back to f.

recursive definition

A definition which defines something in terms of itself. To be useful it must include base cases which are not recursive. In this way it differs from a circular definition. Recursive definitions often provide an elegant way to express complex data structures, like a directory that can contain other directories, or a menu that can contain other menus.

Inheritance & Exceptions

1. Inheritance:

 - superclass vs subclass:
  

  class DerivedClassName(BaseClassName):

  class DerivedClassName(modname.BaseClassName): 

  e.g.class IntStack(Stack): 

- built-in functions that work with inheritance:

   a)Use isinstance() to check an instance’s type: isinstance(obj, int) will be True only if   obj.__class__ is int or some class derived from int.
   b)Use issubclass() to check class inheritance: issubclass(bool, int) is True since bool is a subclass of int. However, issubclass(float, int) is False since float is not a subclass of int.



2. Exceptions:

e.g. class SpecialException(Exception):
    pass

class ExtremeException(SpecialException):
    pass

if __name__ == '__main__':
    try:
        #1/0
        #raise SpecialException('I am a SpecialException')
        #raise Exception('I am an Exception')
        raise ExtremeException('I am an ExtremeException')
        #1/0
    except SpecialException as se:
        print(se)
        print('caught as SpecialException')
        raise
    except ExtremeException as ee:
        print(ee)
        print('caught as ExtremeException')
        #raise
    except Exception as e:
        print(e)
        print('caught as Exception')


Lab: Final question was solved by not shifting every positions after pop, but add 1 index to every elements, which saves operating time :)

19.5. Glossary

exception

An error that occurs at runtime.

handle an exception

To prevent an exception from causing our program to crash, by wrapping the block of code in a try ... except construct.

raise

To create a deliberate exception by using the raise statement.

Abstract Data Types(ADTs)

 An abstract data type, or ADT, specifies a set of operations (or methods) and the semantics of the operations (what they do), but it does not not specify the implementation of the operations. 

Common ADTs:list, dictionary, stack……(from slices)

 

Reading from a paragraph about Stack(useful information)

&

Design(class) 

& 

Implementation(init, push, pop, is_empty) 

&

 Test(if __name__ == '__main__')

 e.g.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return (self.items == [])

 

 

 The first lab we just be on time but lack of time check the correctness, 

 anyway, the cooperation was pleasant :)

 

25.9. Glossary

(again, for my own convenience:) )

abstract data type (ADT)

A data type (usually a collection of objects) that is defined by a set of operations but that can be implemented in a variety of ways.

client

A program (or the person who wrote it) that uses an ADT.

delimiter

A character that is used to separate tokens, such as punctuation in a natural language.

generic data structure

A kind of data structure that can contain data of any type.

implementation

Code that satisfies the syntactic and semantic requirements of an interface.

interface

The set of operations that define an ADT.

infix

A way of writing mathematical expressions with the operators between the operands.

parse

To read a string of characters or tokens and analyze its grammatical structure.

postfix

A way of writing mathematical expressions with the operators after the operands.

provider

The code (or the person who wrote it) that implements an ADT.

token

A set of characters that are treated as a unit for purposes of parsing, such as the words in a natural language.

veneer

A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client.

Code Like a Pythonista: Idiomatic Python:

http://python.net/~goodger/projects/pycon/2007/idiomatic/presentation.html

Getting Started With 108

For the first week, mainly what we did on my view was revision of CSC108.
Rereading notes from 108 and attending rampup session do helped a lot.
( I like the sheet that received at rampup session!)


Things from CSC108 notes:
 week1
 - Python as a calculator: Arithmetic operators (/ float, // int)
 - Syntax(valid combination) vs Semantics(meaning of combination)
 - Variables (Name start with letter or _ )
 - Function (Define, Calls, Built-in)
week2
- String(Escape Sequesces '\', format{})
- Input / Output
- Function Design steps(Example, Type, Header, Description, Body, Test)
- Call Stack(assignment statement, return expression)
week3
- Bool(comparison, logical)
- Converting(e.g. str())
- Import( import math or math.())
- If, elif, else
week4
- More String(==, !=,  <,  >,  <=, >=, in, len(), cannot be modified)
- Index and Slices
- Inside Object( dir(str))
- Loop(for variables in str:)
- Accumulator(number, string)
- While
week5
- Nested Loops
- Range
- Turples(Immutable)
week6
- Nested Lists(visualizer)
- Files(open, write, readline)
week7
- Dictionary(unique key, order doesn't matter)
week8
- Files(Random Story Generation, representing, working with data)
week9
- Test Cases
- Unittest
week10
- Run Time Complexity of Functions
- Sorting Algorithms(Selection, Bubble, Insertion)
week11
- Object-Oriented Programming Class Event/Day



What's new for me is conceps are introduced.

copying concepts just for my own convenience.

15.11 Glossary

 

attribute

One of the named data items that makes up an instance.

class

A user-defined compound type. A class can also be thought of as a template for the objects that are instances of it. (The iPhone is a class. By December 2010, estimates are that 50 million instances had been sold!)

constructor

Every class has a “factory”, called by the same name as the class, for making new instances. If the class has an initializer method, this method is used to get the attributes (i.e. the state) of the new object properly set up.

initializer method

A special method in Python (called __init__) that is invoked automatically to set a newly created object’s attributes to their initial (factory-default) state.

instance

An object whose type is of some class. Instance and object are used interchangeably.

instantiate

To create an instance of a class, and to run its initializer.

method

A function that is defined inside a class definition and is invoked on instances of that class.

object

A compound data type that is often used to model a thing or concept in the real world. It bundles together the data and the operations that are relevant for that kind of data. Instance and object are used interchangeably.

object-oriented programming

A powerful style of programming in which data and the operations that manipulate it are organized into objects.

object-oriented language

A language that provides features, such as user-defined classes and inheritance, that facilitate object-oriented programming.