starters as a java student

 I am a transfer student, and i did not take csc108. Instead, I studied Java before, and here are some differences between Java and Python.



As far as I am concerned, python and Java are two very different programming languages, but both can be useful tools for modern developers. If you are thinking about learning to program for the first time, then you might find Python easier to master. Python’s syntax is designed to be intuitive and its relative simplicity allows newbies to quickly start writing code for a variety of applications. While Java has a steeper learning curve, it is extremely useful for developing applications that will run on any platform.

One of the biggest differences between Python and Java is the way that each language handles variables. Java forces you to define the type of a variable when you first declare it and will not allow you to change the type later in the program. This is known as static typing. In contrast, Python uses dynamic typing, which allows you to change the type of a variable, by replacing an integer with a string, for example.
Dynamic typing is easier for the novice programmer to get to grips with, because it means you can just use your variables as you want to without worrying too much about their types. However, many developers would argue that static typing reduces the risk of undetected errors plaguing your program. When variables do not need to be explicitly declared before you use them, it is easy to misspell a variable name and accidentally create a whole new variable.

Braces 
Python is unusual among programming languages in that it uses indentation to separate code into blocks. Java, like most other languages, uses curly braces to define the beginning and end of each function and class definition. The advantage of using indentation is that it forces you to set your program out in a way that is easy to read, and there is no chance of errors resulting from a missing brace.

Speed vs Portability

The great advantage of Java is that it can be used to create platform-independent applications. Any computer or mobile device that is able to run the Java virtual machine can run a Java application, whereas to run Python programs you need a compiler that can turn Python code into code that your particular operating system can understand. Thanks to the popularity of Java for web applications and simple desktop programs, most devices already have the Java virtual machine installed, so a Java programmer can be confident that their application will be usable by almost all users. The disadvantage of running inside a virtual machine is that Java programs run more slowly than Python programs.

Python vs Java: Which is Easier to Use?

Most programmers agree that Python is an easier language for novice programmers to learn. You will progress faster if you are learning Python as a first language than Java. However, the popularity of Java means that learning this powerful language is essential if you want to develop apps for Android, for example.

assignment 2

Assignment 2



 regular expression:
Regular expressions are text matching patterns described with a formal syntax. The patterns are interpreted as a set of instructions, which are then executed with a string as input to produce a matching subset or modified version of the original. The term “regular expressions” is frequently shortened to as “regex” or “regexp” in conversation. Expressions can include literal text matching, repetition, pattern-composition, branching, and other sophisticated rules. A large number of parsing problems are easier to solve with a regular expression than by creating a special-purpose lexer and parser.
Regular expressions are typically used in applications that involve a lot of text processing. For example, they are commonly used as search patterns in text editing programs used by developers, including vi, emacs, and modern IDEs. They are also an integral part of Unix command line utilities such as sed, grep, and awk. Many programming languages include support for regular expressions in the language syntax (Perl, Ruby, Awk, and Tcl). Other languages, such as C, C++, and Python supports regular expressions through extension libraries.
There are multiple open source implementations of regular expressions, each sharing a common core syntax but with different extensions or modifications to their advanced features. The syntax used in Python’s re module is based on the syntax used for regular expressions in Perl, with a few Python-specific enhancements.


it was regular expressions, or regex, for short. Regular expressions are a series of characters that form patterns, or a sort of template, that can be interpreted by a computer to preform a command. In regular expressions, specific characters have different meaning, and the string follows a pattern that can be converted to preform tasks. Assignment 2 focused on the basic concept of parsing through a custom regular expression and converting that string into a binary tree of nodes based on the operators used in the regex.

I implemented a iterative solution for parsing the string. I first dealt with the base cases, then the StarNode, then after checking the ending parentheses (indicating the end of an expression), added in the BarNode and DotNode. All it really took was going through every character and one stack (rex in this case).
The solution for matching was a bit more complicated so I'm not going to post my full solution, but essentially it required checking the .symbol value of the RegexTree and matching it up with the base cases. I was fine for most of the test expressions, but I was not able to fully perfect how the code dealt with StarNode, so my solution did have some problems with some test cases.

iteration vs recursion

In my previous posts. i already discussed recursion. Here, i take a further insight on recursion.

• Iterative functions are typically faster than their recursive counterparts. So, if speed is an issue, you would normally use iteration.
• If the stack limit is too constraining then you will prefer iteration over recursion.
• Some procedures are very naturally programmed recursively, and all but unmanageable iteratively. Here, then, the choice is clear.

Typically, iteration is used for less complex problems, It depends on the complexity of the problem when it comes to deciding whether to use recursion or iteration. Recursion can be good or not, for example,  when dealing with easy ones, it is more efficient to use for loop rather than always use recursion.

Iteration is significantly cheaper than recursion. You will actually get an error ( RuntimeError: maximum recursion depth exceeded ) indicating that you exceeded maximum recursion depth if your function recurses too far.

This isn't specific to Python by any means. Recursion in most languages has a bit more overhead than iteration, since you have to make another function call every time and allocate a new stack frame.

Of course, there's nothing "wrong" with using recursion. Many algorithms can be expressed much more elegantly recursively than iteratively. However, if efficiency is a concern on any level, iteration is definitely the way to go.

Test doctring

The doctest module searches for pieces of text that look like interactive Python sessions, and then executes those sessions to verify that they work exactly as shown. There are several common ways to use doctest:

• To check that a module’s docstrings are up-to-date by verifying that all interactive examples still work as documented.
• To perform regression testing by verifying that interactive examples from a test file or a test object work as expected.
• To write tutorial documentation for a package, liberally illustrated with input-output examples. Depending on whether the examples or the expository text are emphasized, this has the flavor of “literate testing” or “executable documentation”.

when it comes to test, we need to intelligently choose different test methods for different test cases. here are some things that we need to take into consideration.

• 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.

stack implemetion

 

in python, we use stack to store and modify data.

 

list.append(x)

Add an item to the end of the list; equivalent to a[len(a):] = [x].

list.extend(L)

Extend the list by appending all the items in the given list; equivalent to a[len(a):] = L.

list.insert(i, x)

Insert an item at a given position. The first argument is the index of the element before which to insert, so a.insert(0, x) inserts at the front of the list, and a.insert(len(a), x) is equivalent to a.append(x).

list.remove(x)

Remove the first item from the list whose value is x. It is an error if there is no such item.

list.pop([i])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

list.index(x)

Return the index in the list of the first item whose value is x. It is an error if there is no such item.

list.count(x)

Return the number of times x appears in the list.

list.sort()

Sort the items of the list, in place.

list.reverse()

Reverse the elements of the list, in place.
 

 

exception

Even if a statement or expression is syntactically correct, it may cause an error when an attempt is made to execute it. Errors detected during execution are called exceptions and are not unconditionally fatal: you will soon learn how to handle them in Python programs. Most exceptions are not handled by programs, however, and result in error messages as shown here:
The last line of the error message indicates what happened. Exceptions come in different types, and the type is printed as part of the message. The string printed as the exception type is the name of the built-in exception that occurred. This is true for all built-in exceptions, but need not be true for user-defined exceptions (although it is a useful convention). Standard exception names are built-in identifiers (not reserved keywords).
The rest of the line provides detail based on the type of exception and what caused it.
The preceding part of the error message shows the context where the exception happened, in the form of a stack trace back. In general it contains a stack trace back listing source lines; however, it will not display lines read from standard input.


The try statement works as follows.

• First, the try clause (the statement(s) between the try and exceptions keywords) is executed.
• If no exception occurs, the except clause is skipped and execution of the try statement is finished.
• If an exception occurs during execution of the try clause, the rest of the clause is skipped. Then if its type matches the exception named after the  keyword, the except clause is executed, and then execution continues after the try statement.
• If an exception occurs which does not match the exception named in the except clause, it is passed on to outer try statements; if no handler is found, it is an unhandled exception and execution stops with a message as shown above.

A try statement may have more than one except clause, to specify handlers for different exceptions. At most one handler will be executed. Handlers only handle exceptions that occur in the corresponding try clause, not in other handlers of the same statement. An except clause may name multiple exceptions as a parenthesized tuple.

The use of the else clause is better than adding additional code to the tryclause because it avoids accidentally catching an exception that wasn’t raised by the code being protected by the try..exceptstatement.
When an exception occurs, it may have an associated value, also known as the exception’s argument. The presence and type of the argument depend on the exception type.
The except clause may specify a variable after the exception name (or tuple). The variable is bound to an exception instance with the arguments stored in instance.args. For convenience, the exception instance defines the arguments can be printed directly without having to reference .args.
One may also instantiate an exception first before raising it and add any attributes to it as desired.

Test 1

the test turns to be incredibly easy.
it is more about basic knowledge rather than much of sophisticated programming.

there are some things that i found i should improve:
1) catch up CSC108
2) need to more familiar with built-in methods in python
3)write the code on my own rather than just looking at them
4) utilize the professor's office hours and TA' s office hours.
5) go the help centre on time rather than keep the questions for a long time.
6) I made a lot of so basic calculation mistakes! i do need to figure out a way to improve my computing skills and try to more cautious next time.

TEST 2

i did terribly on test, the reason for this is simply because i did not complete the labs and exercises, and i even skipped some classes, and i am really confused about recursion. However, the truth is that It is supposed to be easy!!

When look through materials covered in class, every code seems to be natural. So i just study these codes by looking at the final code rather than writing code on my own before i turn to look at the answers.

when i was doing recursion problems on the test. so easy things became difficult. i decided to work on recursion harder and try do keep up with others by finishing all the labs and exercises.

Binary tree

 There are three orders in binary tree:

 preorder:

       Visit root, then pre-order left subtree, then pre-order right subtree

 in-order: 

       Visit in-order left subtree, then root, then in-order right subtree 

 post-order:

        Visit post-order left subtree, then post-order right subtree, then
root

 this is how we created a binary tree

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

class BinaryTree(Node):
    def __init__(self):
        self.root = None

    def addNode(self,data):
        return Node(data)

    def insert(self,root,data):
        if(root == None):
            root = self.addNode(data)
        else:
            if(data <= root.data):
               root.left = self.insert(root.left,data)
            else:
                root.right = self.insert(root.right,data)
        return root

    def PreOrder(self,root):
        if root == None:
            pass
        else:
            print(root.data)
            self.PreOrder(root.left)
            self.PreOrder(root.right)

linked list

On Oct 22-24
we learned linked list in class.
linked list is about a sequence of nodes, each with a value and reference to next node. list has reference to front node.
and there are two kinds of operations insert a node and find a node.
besides, we can also implement stack using linked in list:
 def __init__(self: stack)
   self.top=None
 def pop
 def is_empty
 def push

the linked in list class can be created as follows:

class LinkedList:
    def __init__(self):
        self.length = 0
        self.head   = None

One nice thing about the LinkedList class is that it provides a natural place to put wrapper functions like print_backward_nicely, which we can make a method of the LinkedList class:

class LinkedList:
    ...
    def print_backward(self):
        print "[",
        if self.head != None:
            self.head.print_backward()
        print "]",

class Node:
    ...
    def print_backward(self):
    if self.next != None:
        tail = self.next
        tail.print_backward()
    print self.cargo, 

i found it very difficult to understand the linked in list in the first place. it befuddled me about 

how to make a reference to the next value. it should be like every item contain a value and also a reference

that can lead us to the next item, and the reference in the next value also take us to the other item.

object-oriented programming and recursion

object-oriented programming:

A type of programming in which programmers  define not only the data type of a data structure, but also the types of operations that can be applied to the data structure. In this way, the data structure becomes an object  that includes both data and functions. In addition, programmers can create relationships between one object and another. For example, objects can inherit characteristics from other objects.
One of the principal advantages of object-oriented programming techniques over procedural programming techniques is that they enable programmers to create module that do not need to be changed when a new type of object is added. A programmer can simply create a new object that inherits many of its features from existing objects. This makes object-oriented programs easier to modify.Python is a very clever and useful and mostly programming language.

recursion 

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".
The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some systems —are an exception to this.) .
For some functions  there is not an obvious base case implied by the input data; for these one may add a parameter (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by co-recursion, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".

Recursion in its most basic form refers to breaking up a problem into smaller instances so that you can solve those instances and use that to come to a final solution. In programming terms, a recursive program is one that calls itself. Recursive programming structures can be very efficient and solve a variety of problems, for example determining how nested an item is within a list or branching. For some problems, just simply iterating is more efficient, but for more complex problems, recursion is beneficial.


eg

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

The two key elements of a recursive algorithm are:

• The termination condition: n == 0
• The reduction step where the function calls itself with a smaller number each time: factorial(n - 1)

selection merge quick sort and logn

This week, we studied sorting, although we studied before, I still find selection sorting difficult.
Sorting

• The selection sort – for each element – finds the minimum value from that element onwards, and switches the two elements (this is for sorting in ascending order, of course).
•  
• The merge sort, on the other hand, continually halves an unsorted list (recursion’s a great tool!), then sorts those “halves” and then finally combines all of these halves to create a sorted list.
• The quick sort chooses a “pivot” 
• decide wherer the povot goes with respect to the rest of the list 
• repeat on partition

And Danny compared running time for each kind of sorting method. Some is really efficient,while some are always repeating the lass step which takes forever to get results.

thus, i understand that in order to become a good programmer, it is far from enough to just being able to write a programmable code, but also need to efficient, to work out the problem more quickly than others. 
In class, we compared each of the various sorts on different input sizes. the selection and merge sorts became inefficient quickly, while it was the quick sort that came out on top (of the sorts we studied); this didn’t surprise me one bit because its Big-O efficiency of O(n log n). But, it turned out that built-in list.sort() came up the winner in all but the very biggest inputs,due to its searching mechanism itself changes for different input sizes.

log n is the number of times you can divide n in half before reading 1

also the type of input is another essential factor in running efficiently.

from the angle of efficiency,  Danny mainly talks about BIG-O efficiency.
Big-O running time  is an upper-bound on the running-time of a given algorithm, and gives the worst-case performance of an algorithm. This worst-case performance is given in terms of the input size for the algorithm.( the Big-O efficiency of a linear search is O(n), or “Oh-n”,meaning that, at worst, the algorithm need to scan all n elements in a list to find a given element.)
Selection sort: O(n^2)Merge Sort: O(n log n)Quick Sort: O(n log n) — both merge and quick sorts may have the same Big-O efficiency. However , when we run into large input, the merge sort’s efficiency becomes closer to O(n),worse than the quick sort’s O(n log n)

hi i am enrolled in cs148