Python Guide Pt 1 PDF

Preview

Summary

While True:print(“Learn Python”)I assume that you have ZERO knowledge in Python and you want to learnpython ASAP but there is not much time left.Fear NOT, as for today I will provide you a plan on how you should studypython starting from Week 1 – Week 12.Follow this plan and I can ensure you that yo...

Description

While True: print(“Learn Python”)

I assume that you have ZERO knowledge in Python and you want to learn python ASAP but there is not much time left.

Fear NOT, as for today I will provide you a plan on how you should study python starting from Week 1 – Week 12.

Follow this plan and I can ensure you that you will be prepared for the exams. This guide is somewhat brief therefore you should explore more from the links I provided

Prepared By: Chong Jun Wen SEE YOU NEXT SEM �

CHECKLIST WEEK 1

WEEK 2

WEEK 3

WEEK 4

WEEK 5

WEEK 6

WEEK 7

WEEK 8

WEEK 9

WEEK 10

WEEK 11

WEEK 12

WEEK 1 Definition of an algorithm: An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. “up to week 7, you will feel that python very easy. When week 8 comes, it hits you like a truck and you will feel like you want to die.” – Chong Basic stuff if you have been studying you should know will go going on in this week. Operators:

When we are using complex operators, you should know that there are precedence for each operator, don’t tell me you don’t know. “after all, you did this in your parsing.py assignment.”

The operator with the highest precedence will be evaluated first. (unless you add some parenthesis in your equations)

Functions In python, there are a lot of functions. Most of the time, we will not be able to access it unless you import it. “How can we do it?” Simple. We just type in the code { import module }

This is an example of what functions that we can use when we import the math module.

sqrt(2) will provide the same output as 2**(1/2) but it saves so much time in typing the code.

Variables

When you look at this x will be a variable address, and 17*2 will be the value stored in that x address. There are some rules on naming your variables.   

Reserved names and keywords used by python cannot be used as variable names You cannot start a variable name with digits They are case sensitive

You can also convert values of different types by doing this

WEEK 2 Creating a function by definitions: When you have a block of code that is repeating, we can use the def: to create a function for it. For example

A function is a block of reusable code that is used to perform a specific action. The advantages of using functions are: 

Reducing duplication of code



Decomposing complex problems into simpler pieces



Improving clarity of the code



Reuse of code



Information hiding

Boolean (Truth) Values ==

 Equal

!=

 not Equal

Logical operators are a must to be used to try and create selection statements. You have to be very careful when attempting to using logical operators. This is because short circuiting exists in python as well. If you are using and “AND” operator, and the first statement is “FALSE”, the next term will not be evaluated. That is what short circuiting means. I don’t really need to explain about selection statements as I assume that you are familiar with it already. “For god’s sake we are in week 12”

Conditional and counter loops While loop

 Conditional

For loop

 Counter Loop

For Loops Do you know everything in python starts from 0? If you put “for I in range(8):” , it will iterate from 0 – 7. Totalling up to 8 times but it does not end at 8. This is because that there is a thing called upper bounds, when looping through a range of numbers, python always stops before touching the last digit in the range. If you put “for I in range(8):” without any additional arguments, it will iterate from numbers 0-7 by stepping i+1 until it reaches 7 but as for “for I in range(1,8,2):” it will iterate from numbers 1-7 by stepping i+2 until It reaches 7 as “2” in the parameter is the stepping argument.

While Loops While loops are a bit tricky, every time you create a while loop, you enter a Boolean statement as the looping condition. You have to ensure that there is something in the loop can make the condition false so that you will not have an infinite loop. Example: I=1 While I == 1: Print(“Hello”)

This loop will print “Hello” infinitely as the Boolean condition is always true. You have to add a line in the loop “I += 1” so that you can make sure the loop can stop.

WEEK 3 mou List Methods

Algorithmic solution

Graphs Here is an example of a graph

There is a list V which is known as Vertex and E which is known as Edges. Vertex = The points Edges = The connections for the points

Ordered Relations: Directed Graphs

In directed graphs, the edge relation is asymmetric. This means that It can go in one direction. Simple graphs Definition: Simple graphs contain no loops and parallel edges. Maths knowledge

C

To calculate the max number of edges in a graph we take the number of vertexes, V and do V 2.

Cycles: A path (non-self-intersecting) with the same start and end vertex is called a cycle. From the graph above, 4  5  6 4 is a cycle. (4,5), (4,6), (5,6)

Connected Graph: A graph which every vertex can be reached from every other vertex. As for this graph above, it is not connected as 7,8 and 9 cannot be reached. However, it can be fixed if there is a connection between vertex 6 an 9 (6,9).

Representation of graphs: adjacency matrix There are many ways to represent graphs and adjacency matrix is one of the ways.

This should be simple enough to understand. But don’t get confused, during exam if they ask to write out the adjacency matrix, you do this.

I don’t think knowing how to get the neighbour is necessary to memorise, but you should know anyways, ill briefly explain about this code.

For this line of code, “i” will be vertex that you want to choose. As we know from graph representation of adjacency matrix, “i” is the index of the sub-list. Inside the sub-list “i”, we look for elements that have the value of 1 and we take their index and append it into the “res” list. This is because that if the element of the sub-list is a 1, it means that it is connected to that 1’s index and that’s the neighbour of the vertex.

Representation of graphs: adjacency lists

During exam if they ask to write out the adjacency lists, you do this.

*I’m stressing this week’s notes a lot because you have to understand this or else you are going to suffer for the next 12 weeks as you won’t understand a thing, so try your best and understand graphs.

Trees Definition: A simple graph is a called a tree if is connected and has no cycles. This means that a graph cannot not form a tree if it is not simple. A graphical representation of a tree:

Properties of a tree: is minimally connected, i.e., removing any edge renders disconnected and contains unique path between any two vertices

Spanning tree of a graph

Before we go any further, let me clear some of the confusion between spanning trees and trees A regular tree is a tree that may or may not have nodes; however, spanning tree is a subgraph that has all the vertices that are there in the graph, and is a tree. The spanning tree has the

same vertex as the original graph.

Ayy since now you are familiar with graphs, lets move on to the toughest part in this topic. Prim’s algorithm for finding a spanning tree

This is the code for spanning tree. Graph:

The spanning tree that we will get:

Let me briefly explain what the code does. The graph used is very simple therefore its much simpler to understand. Firstly, lets explain about the variables I have declared. graph



This is a simple tree graph

empty_graph (function)



This creates a graph that is not connected at all which which has the same length of the simple graph (copy of the graph but no vertices are connected)

n



the length of the graph, if there are 4 vertices, there there will be a length of 4

tree



the return value of empty graph and this variable will be the spanning tree in the end

conn



vertices that are connected. If there are 4 vertices, in the end the conn must be [0,1,2,3] and then the function ends because a spanning tree must be a tree that is connected.

Alright, lets get to it. Let’s just say we have the graph ready and we call the function spanning_tree. This initializes n, tree and the initial value of on will be set to 0. Then we move on to the while loop, the while loop has a condition that will make sure it keeps running until the length of the conn is more than the length of the graph (line12). The found variable is just to help break from the for loop and it is reset every time a while loop starts but I will explain later. Remember when I say that the conn initially has the value 0? This means that the For loop in line 14 will set “j” as elements of conn which is [0] currently and it will look at the graph [ 0 ]. And “I” increases every time till It satisfies the condition in line 16. For example in the code, “I” when it is 0 will be ignored and it wont enter the block of code because graph[ 0 ][ 0 ] does not have the element 1. Then “i” will become 1 and this will enter the block of code because graph[ 0 ][ 1 ] has the element 1. Therefore, in the tree, it will add an edge for vertex 0 and vertex 1. There are 2 lines that does it which are line 17 and line 18 because we know that the connection is symmetric. After that it will add vertex “1” into conn because now vertex [0,1] are connected. Next, it makes Found = True and breaks the for loop in line 15. After that, there is another if statement that checks if Found == True and if it is, it breaks it out of the for loop in line 14 which causes it to go back to line 12 because the while loop condition is still True. Once that happens Found will be set back to False and the value of “i” in the for loop in line 14 will be set back to 0 and the cycle continues. This function wastes a lot of cycles as every time it connects something, it resets the value ‘for i in conn’ and it checks from the beginning again. Example, “for i in conn” and conn = [0,1,2]. If I can connect something when my “i” value is 2 it resets the “i” value back to 0 and rechecks again starting from scratch given that “len(conn) < n” (condition to make sure the while loop runs)

The while loop ends when the length of the graph is the length of conn which means that all vertices are connected. 1st connection, conn = [0,1]

2nd connection, conn = [0,1,2]

3rd connection, conn = [0,1,2,3]

Spanning tree is now complete as conn = [0,1,2,3] which connects all the vertices. (connected tree and has all vertices)

Decomposition What is decomposition? Well, it’s simple  

Decomposition is breaking down programs into sub-programs Decomposition is also breaking down problems into sub problems

Pure Functions   

Simple association of output to input values Calling it does not alter the state of environment Always yield the same result for same input

General sub-programs  

Can have side effects and alter the environment Return value can depend of the environment

Remember out Prim’s algorithm in finding the spanning tree? Well this is how it looks like after being broken down in to smaller parts

Should be simple enough to understand, its will be doing the same thing but it is broken down

WEEK 4 mou I love it when python gives you a hard week and then an easy one. Makes me wanna kill myself. Understanding python I tell u ah, this week hor its like u go to lecture and you don’t learn jack shit. But oh well I don’t think this will be focused a lot, its just that you need to understand it. That’s all…. You know how swapping works right? Meh just do this

The reason you declare a temp value is to store it in a place because if you declare the value of y into x your x’s value will change, therefore losing the original x value can you cannot swap. What are functions? Common question, a function can be either defined or using python’s built in function. I can create my own function and code what it does and just call it and it will do what it is supposed to do or I can use python’s built in functions to do what I want it to do.

List mutability Oh yeah, remember lists? These bad boys are a reference data type. Therefore, they are mutable.

If you do this, it will return you True, True, False. Why? This is because this

I don’t think I need to explain lmao. If you assign Z = X means that it shares the same ID as it is referencing the same list. But if you assign X = [‘a’, ’b’, ’c’] and y =[‘a’, ’b’, ’c’] individually. The id does not share, therefore the id(x) == id(y) will return False.

If you are lazy and you want to assign the same values of a list onto another variable without doing it individually and making sure that changing one of the values does not affect another, you can do copying. There are two ways of doing the copying Way 1: use [:] x = [1,2,3] y = x [:] This method is a slicing method

Way 2: Import copy module from copy import copy x = [1,2,3] y = copy(x) This method is called the copy method

There are 2 types of copy, shallow copy and deep copy. I don’t think this will be asked but ill just leave the definition for it here Shallow Copy: simple copy only copies references and not object referenced Deep Copy: deep copy is fully independent copy of original object

Some random stuff you probably should know Variables (names for objects)  

Can be re-assigned Lose object when no longer referenced

Functions  

Bound to variable on definition references to them can be passed to other variables (including arguments of other functions)

Tuples (Basically the immutable version of lists)  

can be used for multiple assignment useful function needs to return more than one value

Mutable  

value of variable pointing to mutable object can changed without being re-assigned augmented assignment changes in-place (whatever this is lmao idek)

Omg Its Sorting, yay another bad chapter that I must explain everything You should already know what is sorting, you don’t bullshit me Sorting Problem: Input = list Output = sorted list I’m going to skip the invariant for this because its much easier to understand later on, so just bear with me.

Selection Sort (This algorithm is a joke) For selection sort, you assume that List [ 0 ] is the minimum index and you compare with the rest of the list till you find the index of the element that is smaller than the element in List [ 0 ]. If no element is smaller than List [ 0 ], then List [ 0 ] is the smallest element in the list XD. If there is an element that is smaller than List[ 0 ], you get it’s index and swap places with it. After swapping, it will then check for List[ 1 ] and List [ 0 ] will be ignored as it is already sorted. This loops until the value of List [ n ] is the last element in the list.

Let me show you the code and I will explain more

As you can see, minimum_index(lst) function return the index of the lowest value in the list. It starts off by assuming index 0 is the lowest value, if there is someone lesser than the element in index 0, it will reassigned into minimumindex. The selection_sort(lst) function is where the sorting happens. As you can see, slicing is used, this is because that it is to ensure that the sorted items are put to the front and it will not be altered anymore as it is already sorted. It sorts by swapping the current position element with another element that hasn’t been sorted (That has lower value) This will be the steps to sort the list [3,8,2,1,6,9] Step 1

[1,8,2,3,6,9]

Step 2

[1,2,8,3,6,9]

Step 3

[1,2,3,8,6,9]

Step 4

[1,2,3,6,8,9]

Step 5

[1,2,3,6,8,9]

Insertion Sort UwU Insertion sort, ok. Let me explain you in simple words. Never mind I just show you a picture of what is insertion sort

Happy? If not call me 018-3563198. U come talk to me and see what shit you not happy about. I legit don’t feel like explaining this lmao, I want save energy for other algorithms in the back Lets see the code shall we? �

Sorting Steps: Step 1

[3,8,2,1,6,9]

Step 2

[2,3,8,1,6,9]

Step 3

[1,2,3,8,6,9]

Step 4

[1,2,3,6,8,9]

Step 5

[1,2,3,6,8,9]

I lazy explain so I steal ppl’s explanation:

WEEK 5 mou Sorry If look like I’m skipping certain stuff, I’m actually just trying to rush the notes because these stuff may not even come out and the important stuff is after week 7. Invariants and Assertions I’m just going to throw you the invariant for insertion sort

I’m also going to just throw you the invariant for selection sort

Definition for a loop Invariant: A loop invariant is simply something that is true on every iteration of the loop.

Lmao if this comes out in the test, everyone is fu*ked HAHAHAH

Greedy Algorithm and Optimization (yay! more hard stuff) Wiring problem

In the end it will look like this

Although it is connected, but it is not the minimal way of doing as the bottom one is more minimal

This is exactly same as creating simple graph that connects with every vertices and every edge has a weight, so you have to find a spanning tree that has the least total weight

Possible solution

You don’t have to care much about this as ill explain more in detail later

Greedy algorithms always find the fastest way to solve a problem but sometimes it may not be the most optimized solution. Keep that in mind.

There are 2 problems that are important in this subject and they are the change problem and the knapsack problem, please remember the input and outputs for both problems

I’ll just show you the python slides as they are pretty much self-explanatory

YAY for minimum spanning tree

This is the flow chart for the minimum spanning tree. The minimum spanning tree utilized the greedy algorithm to find the spanning tree that has the minimum weight

This is exactly same as the spanning tree algorithm, but this time there are 2 extra things added and they are in boxes. Since I have exaggerated on the spanning tree code, I will not do it again. The 2 lines of code makes sure that the edges chosen are the lowest weighted.

This is the part where I slack off in explanation because I’m tired. I skipped greedy knapsack problem as I assume that you know how to do it. After all, you did the something similar in your assignment 2 task 1.

YAY for WEEK 6 This week its going to be fun, its about brute force, ahh my favourite. This terminology almost killed me during assignment 2 week. The stupid algorithm has 3 steps, so please listen carefully. Remember greedy algorithm? That algorithm that uses the fastest way to solve a problem, but it may not be optimized all the time? Well brute force is slightly different. Brute ...