Now that you've got the hang of running Python programs through the terminal, let me introduce you to a much easier option: iPython notebooks! These allow you to run blocks of Python code right in your browser and to integrate blocks of code with text (as I'm doing now).
To open an iPython notebook, navigate to the file containing it in your terminal and type
ipython notebook fileName.ipynbTo run a block of code, click somewhere in it and press Shift-Enter.
print("Hello, iPython!")
In Python you can combine boolean expressions to create more complex conditionals using the keywords and, or, and not (equivalent to &&, ||, and ! in Java). For example,
(x < 10) and not (x % 3 == 0)
will evaluate to True if and only if x is less than 10 and not a multiple of 3.
Note: using parentheses to separate parts of compound conditionals makes them much more readable.
Complete the following code to print out all integers less than 100 which are either
for i in range(100):
# Replace 'True' with the appropriate conditional
if True:
print(i)
So far we have learned about several types of objects in Python: numbers, strings, booleans (True/False), etc. Another type of object is the list—an object which contains a collection of other objects (even other lists!). This is similar to the mathematical concept of a set, except that order matter in a list. Lists are the equivalent of arrays in Java.
Lists are defined using square brackets []:
L = [1, 3 * 5, "cat", "dog", [3.14, "pie"]]
Note that the expression 3 * 5 will be evaluated and the result stored in L, not the string "3 * 5".
Here is some stuff you can do with lists:
# Define a new list
L = ["Bilal", "dylan", "Ethan"]
print(L)
# Get the length of the list (number of elements)
print(len(L))
# Get an individual element of the list
print(L[0])
L[1] = "Dylan"
print(L)
# Notice that the indices start at 0, not 1, and go up to len(L) - 1
# Add an element to the end of the list
L.append("Ginger")
print(L)
print(len(L))
# Sublists
print(L[1:3])
# Iterate through a list
# You can use any variable name you want instead of 'person'
for person in L:
print(person + " stinks!")
# Another way of iterating through the list
for i in range(len(L)):
print(L[i] + " stinks really bad!")
# Create a new list using a for loop
# This is called "list comprehension"
A = [True for i in range(10)] # 10 copies of True
B = [i for i in range(10)] # Integers 0 through 9
C = [2 * i for i in range(10)] # Even integers 0 through 18
print(A)
print(B)
print(C)
print("")
### 2D lists ###
# A 10 x 20 array of 0s
# I.e., a list of 10 lists of length 20
A = [[0 for j in range(20)] for i in range(10)]
print(A)
print("")
# A prettier way of printing A
# Each "row" of A is one of the inner lists of
for row in A:
print(row)
for i in range(10):
for j in range(20):
A[i][j] = i + j # Change the (i, j)the entry of A to i + j
print("")
for row in A:
print(row)
Repeat Exercise 1, but instead of printing out each number add it to a list and print the list at the end.
# Start with an empty list
L = []
# Your code here
print(L)
In math, a function is an operation that takes an input, does some computations, then gives you an output. For example, the function $f(x) = 3x + 5$ takes the input $3$, computes $3 \cdot 3 + 5$, and spits out the output $14$. The beauty of functions is that you can give them many different inputs and they will compute the output for each one!
Here is how we would define this function in Python:
def f(x):
return 3 * x + 5
print(f(3))
print(f(2.1))
n = float(input("Enter a number: ")) # float converts your input from a string to a decimal
print("f(" + str(n) + ") == " + str(f(n)))
Notice how a single function definition is enough to compute the function for any input we throw at it!
In the code above:
f is the name of the function. You can name a function anything you like; it doesn't have to just be a single letter. For example, we could have called our function times3Plus5(x).x is the argument to the function. It is a variable which acts as a placeholder for whatever input you give the function (3, 2.1, etc.). Again, you can choose the name of this variable. Functions can have multiple arguments, and they can be any data type (number, string, boolean, etc.).return statement determines the output of the function. The output is sometimes called the return value.f(3) we say that we are passing the value 3 to the function.Functions are one of the most important concepts in programming, so make sure you understand them! Don't be afraid to ask questions if something doesn't make sense to you!
Implement the function $g(x, y) = x^2 + xy + y^2$ in Python. You can compute x$^2$ by doing either x * x or x ** 2. Write some code to test your function (similar to the code above).
# Your code here
Sometimes functions involve more complicated computations. For example, here is a function which computes $n!$:
def factorial(n):
fact = 1 # Start with 1
# Multiply by all the integers up to n
for i in range(1, n + 1):
fact = fact * i
# The number computed is the output
return fact
theNum = int(input("Enter an integer: "))
print(fact(theNum))
The variable fact is called a local variable. It is defined inside the function to help with computations, and it goes away when the function returns. Try adding some code that uses it ouside the function and see what happens...
Implement a recusive version of factorial.
The Fibonacci numbers are a sequence of integers $F_0, F_1, F_2, \ldots$, where $F_0 = F_1 = 1$ and $F_n = F_{n - 1} + F_{n - 2}$. In other words, each number in the sequence is the sum of the two previous numbers. The first few Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, ...
Write a function fib( $n$ ) which returns the $n$th Fibonacci number.
Hints:
for loop to compute $F_0, F_1, \ldots, F_n$.def fib(n):
# Your code here
# Return the appropriate value instead of 0
return 0
n = int(input("Enter an integer: "))
print("F_" + str(n) + " == " + str(fib(n)))
Now write another function, fibs( $n$ ), which retuns a list of the Fibonacci numbers $F_0, F_1, \ldots, F_n$.
def fibs(n):
L = []
# Your code here
return L
n = int(input("Enter an integer: "))
print(fibs(n))
I implemented a basic graph class for you to play around with. You can download it here (save it in the same directory as this iPython notebook). You can take a look at the code if you are curious about what classes look like in Python, but otherwise don't worry about it. This implementation allows loops but not multiple edges.
Below is a simple example illustrating its basic functionality:
from graphs import Graph # This line imports the Graph class from graphs.py; you won't be able to use it otherwise
G = Graph(3) # Create a new graph with vertices 0, 1, and 2
G.addVertex("cat") # Add a new vertex called "cat"
# Add an edge from cat to each other vertex
for i in range(3):
G.addEdge("cat", i)
print(G) # Display the graph G by listing each vertex and its list of neighbors
print(G.numVertices()) # Number of vertices
print(G.numEdges()) # Number of edges
print(G.neighbors("cat")) # Print cat's list of neighbors
print(G.degree(0)) # Print degree of vertex 0
# Remove vertex 1 and all of its incident edges
G.removeVertex(1)
# Remove the edge from cat to 0
G.removeEdge("cat", 0)
print("")
print(G)
Run the block of code below and draw a picture of the graph from the output.
from graphs import Graph
G = Graph(4)
for v in range(3):
G.addEdge(v, (v + 1) % 3)
G.addVertex("v")
G.addEdge("v", 2)
print(G)
Write a function Path( $n$ ) which returns a path of length $n$, i.e. a graph with vertices $0, 1, \ldots, n$ and edges $01, 12, \ldots, (n - 1)n$.
from graphs import Graph
def Path(n):
G = Graph(n + 1) # Why n + 1 and not n?
# To do: add edges!
return G
print(Path(10))
Write a function Cycle( $n$ ) which returns a cycle of length $n$. Be sure to test your code.
Hint: a cycle of length $n$ is a path of length $n - 1$, plus one extra edge. Use your function from the previous exercise!
from graphs import Graph
# Your code here
Write a function CompleteGraph( $n$ ) which returns the complete graph $K_n$. This graph should have all possible edges EXCEPT loops.
from graphs import Graph
# Your code here
Write a function RandomGraph( $n$ ) which returns a random graph on $n$ vertices. By this I mean the following:
random.randInt(0, 1).from graphs import Graph
# Your code here
Write a function isWalk( $G, W$ ) which takes a graph $G$ and a list of vertices $W$ and returns True iff. $W$ represents a walk in $G$. This means that each pair of consecutive elements of $W$ must be an edge in $G$.
Hint: iterate through the list until you find a pair that's not an edge; if you make it all the way through, return True.
from graphs import Graph
# Your code here
Similarly, write functions isPath( $G, W$ ), isCircuit( $G, W$ ), and isCycle( $G, W$ ) based on the definitions we covered in class.
from graphs import Graph
# Your code here
Write a function randomWalk( $G, k, v$ ) which computes a random walk of length $k$ in $G$, starting with vertex $v$. In other words, start at $v$, and randomly bounce along the edges of $G$. More formally, at each step, pick a random neighbor of the current vertex and move to that vertex. Add the vertices visited to a list as you go along, and have your function return the list.
from graphs import Graph
# Your code here