Applied Algorithms (3 cr.) № 1

CSCI-B 505 Applied Algorithms (3 cr.) № 1

Contents
Introduction 2
Problem 1: Writing and Executing a Python Program 4
Program 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Executing Program 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Program 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Program 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Executing Program 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Problem 2: Named and Unnamed Functions 6
Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Approximation of Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Program 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Executing Program 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Problem 3: Arrays 7
Program 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Executing Program 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Problem 4: Looping 8
Program 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Executing Program 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Executing Program 5 with stack overflow . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Problem 5: Visualization 10
Program 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Program 6 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Assignment № 1 Page 1
Problem 6: Practice Homework 11
Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Visualiszation of function and derivative . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Assignment № 1 Page 2
Introduction
This homework is meant as precursor to the course: developing working knowledge of Python
and being exposed to some of the concepts of Applied Algorithms as we move through the
semester. Because of the consequences of Covid, these first few homeworks will not be graded;
rather, they are to help you prepare. The solutions are given at the end, but as graduate students
you know that skipping to the end without trying to solve the problems makes the exercise
unhelpful. We urge you, in the strongest terms, to treat these as though they were homework
and learn from them. With respect to this, we are not giving you the code explicitly–you should
type it in–this will help you immensely, since you’ll have bugs and bugs are always gifts to better
understand code! You are also encouraged to explore Python beyond what we present here–we
simply do not have time to teach the language completely–as computer and data scientists we
know that if you know one language, you know them all. We list here the salient topics for this
particular homework:
• Writing and executing a Python program
• Using both named and unnamed functions and modules
• Using arrays
• loops: bounded, unbounded, recursion
• Visualization of data
We end with three problems drawn from content above. Solutions are presented at the
end. As graduate students you are aware that there are often no single correct answer; rather,
collections of correct answers. If you have found a solution that’s different from what we present,
that’s great! The important point is to make sure you understand the underlying concept. If
you’re unsure, contact us.
Assignment № 1 Page 3
Problem 1:Writing and Executing a Python Programs
Python is now arguably among the most popular programming languages. While it has shortcomings, as all languages do, its strengths of community, ease of programming, modules (libraries), industry support, incredible visualization modules, continual evolution (to list a few),
make it an appealing language to study applied algorithms. In our examples, we will often switch
from Windows, Apple OS, and Linux – the OS doesn’t matter at this point–the commands are
essentially identical for what we will be doing.
Getting Started
1. Install Python (www.python.org)
2. (optional) Install an editor – you can write your code in any ASCII editor–for this example,
we’re using IDLE.
3. Create a folder for the class. We are using 505 as our folder name. In this folder, create
a subfolder Assignment_1.
4. Open an editor and write this code in folder Assignment_1
1 print("Hello, Indiana University!")
and save it as hello_IU.py.
5. Open a shell and execute the Python:
1 PS D:\505> py .\Assignment_1\hello_IU.py
2 Hello, Indiana University!
3 PS D:\505>
On our machine we abbreviated python to py. You do not need to do this. The code is
executed.
Adding Modules
In this problem, we will add the random module (please read about this) and our own. As you
probably know, deep learning relies on threshold functions: if a value is less than, say, zero, it’s
returns -1; otherwise it returns 1. We will write this as our own module. We will use the random
module to generate data.
1. Inside Assignment_1, write this program:
1 def f(x):
2 if (x >= 0):
Assignment № 1 Page 4
3 return 1
4 else:
5 return -1
and name it neuron.py. Make sure you understand what it does.
2. Inside Assignment_1, write this program:
1 import neuron
2 import random as rn
3
4 for _ in range(5):
5 data = rn.randint(-10,10)
6 print("{0:>4} {1:>4}".format(data, neuron.f(data)))
and name it threshold.py. Make sure you understand what it does.
3. We have written threshold.py so that it uses neuron and random. Execute the program:
1 PS D:\505> py .\Assignment_1\threshold.py
2 8 1
3 -2 -1
4 9 1
5 -9 -1
6 7 1
7 PS D:\505>
Observe we used formatted output to make readability easier.
Assignment № 1 Page 5
Problem 2: Named and Unnamed Functions
Python treats functions as first-class objects. This comes in handy. Newton’s difference quotient
describes the derivative:
f
0
(x) = lim
h→0
f(x + h) − f(x)
h
(1)
Observe that Eq. 1 is a function! There are times when we need to compute a derivative without
knowing the function a priori. We can approximate a derivative:
f
0
(x) ≈
f(x + h) − f(x − h)
2h
(2)
for very small values of h. Like the equation before, Eq. 2 is a function.
For example, let f(x) = x
3/10. Let’s find the value of the derivative at x = 2.5.
f(x) = x
3
/10 (3)
f
0
(x) = ( 3
10 )x
2
(4)
f
0
(2.5) = ( 3
10 )2.5
2 = 1.875 (5)
We will write a program that inputs univariate function of x and value and displays the derivative at 2.5.
1. Inside Assignment_1, write this program:
1 fn = input("input function: ")
2 fn = eval("lambda x: " + fn)
3 val = float(input("value: "))
4
5 def derivative(f):
6 h = 0.00001
7 return lambda x: (f(x + h) - f(x - h))/(2*h)
8
9 print(derivative(fn)(val))
and name it derivative.py. A couple of observations: Python’s I/O is via strings. So
you must change the type (when inputting) if you’re not going to use the string type. The
eval function converts the text to a valid Python expression. We changed the string 2.5
to float on line 3. The derivative function returns a function described by Eq. 2. Here is a
run of the program:
1 PS D:\505> py .\Assignment_1\derivative.py
2 input function: (1/10)*(x**3)
3 value: 2.5
4 1.8750000000178344
5 PS D:\505>
As you can obviously see, this is an approximation.
Assignment № 1 Page 6
Problem 3: Arrays
Python’s own array type isn’t considered as good as the array in the array module. We will only
use the numpy module. A array is a contiquous portion of memory allocated for a type. Since
applied algorithms have a great of data as arrays, it’s important you become familiar with them.
Arrays are collections–each element is accessed by an index. Python allows slicing which will
we not cover here, but you should look into it.
There will be many “quick tricks” to do operations on arrays–Python itself has many. You
should be cognizant, however, that these are only run-time fixes–the underlying algorithm is not
changed.
1. Inside Assignment_1, write this program:
1 import numpy as np
2 import random as rn
3
4 def search1(v, d_array):
5 for i in range(0, d_array.shape[0]):
6 if v == d_array[i]:
7 print("found {0} at {1}".format(v,i))
8
9 def search2(v, d_array):
10 for i,j in enumerate(d_array):
11 if v == j:
12 print("found {0} at {1}".format(v,i))
13
14 def search3(v, d_array):
15 if np.any(d_array[:] == v):
16 print("found")
17
18 data = [0,1,10,2,1,23,1]
19
20 da1 = np.array(data)
21 da2 = np.empty(7)
22 da3 = np.empty((2,3))
23
24 print(data)
25 print(da2)
26 da2 = da1
27 print(da2)
28 da2[0] = -1000
29 print(da1)
30 print(da3)
31
32 for i in range(da3.shape[0]):
33 for j in range(da3.shape[1]):
Assignment № 1 Page 7
34 da3[i][j] = rn.randint(-5,5)
35
36 print(da3)
37
38 search1(23,da1)
39 search2(23,da1)
40 search3(23,da1)
and name it array1.py.
2. Execute array1.py
1 PS D:\505> py ’.\Assignment_1\array1.py’
2 [0, 1, 10, 2, 1, 23, 1]
3 [3.76624467e+112 1.33501124e+151 8.71458132e+150 6.52933223e+044
4 2.43395092e-152 1.14407192e+243 0.00000000e+000]
5 [ 0 1 10 2 1 23 1]
6 [-1000 1 10 2 1 23 1]
7 [[6.23042070e-307 1.16824187e-307 1.89146896e-307]
8 [1.02360528e-306 1.33511290e-306 1.03980870e-312]]
9 [[-4. 1. 0.]
10 [ 0. -5. 1.]]
11 found 23 at 5
12 found 23 at 5
13 found
Observe that when printing, a list includes commas, whereas the numpy array does not. Also
observe that arrays are initialized with numbers albeit small. Also observe that arrays are callby-reference–so the assignment of da2 and subsequent altering of value changes da1. We can
avoid this explicitly–you should read how. There are a number of ways to search through the
array–you should always use simply scanning, since this is true to algorithms. Again, any fast
tricks you see have other algorithms hidden–so, ultimately, it won’t make a difference.
Problem 4: Looping
There are four ways to loop:
• Goto (which we will not ever use)
• Bounded looping (a fixed number of iterations)
• Unbounded looping (a potentially infinite number of iterations)
• Recursion (a potentially infinite number of iterations)
Assignment № 1 Page 8
Bounded is strictly less powerful than either unbounded or recursion (which are equal in expressiveness). Some problems are more easily solved with one kind of looping than others. In
Python, there is a limit to the stack when recursing. Also, tail-recursion is not treated differently
than recursion. Here is an example we’ve sure you’ve seen:
f(0) = 0 (6)
f(n) = n × f(n), n = 0, 1, 2, . . . (7)
We’ll write this in three different forms.
1. Inside Assignment_1, write this program:
1 def f(n):
2 if n == 0:
3 return 1
4 else:
5 return n * f(n-1)
6
7 def f1(n, acc=1):
8 if n == 0:
9 return acc
10 else:
11 return f1(n-1, acc*n)
12
13 def f3(n):
14 v = 1
15 for i in range(n,0,-1):
16 v *= i
17 return v
18
19 print(f(5), f1(5), f3(5))
20
21 print(f3(2021))
and name it recur.py.
2. Execute the program:
1 PS D:\505> py ’.\Assignment_1\recur.py’
2 120 120 120
3 7803019396418109670749835934800040105723943770373208703399325747239667←-
4 0638272179141117802934475394226002164644216644923930930542069974053352←-
5 9828443589112978094315790589459115326726585869546644590908033098153851←-
Assignment № 1 Page 9
6 (a lot of numbers) ... 0
7 PS D:\505>
3. Replace the last print with print(f(2021)) and execute the program. You’ll see this:
1 120 120 120
2 Traceback (most recent call last):
3 File ".\Assignment_1\recur.py", line 25, in <module>
4 print(f(2021))
5 File ".\Assignment_1\recur.py", line 5, in f
6 return n * f(n-1)
7 File ".\Assignment_1\recur.py", line 5, in f
8 return n * f(n-1)
9 File ".\Assignment_1\recur.py", line 5, in f
10 return n * f(n-1)
11 [Previous line repeated 995 more times]
12 File ".\Assignment_1\recur.py", line 2, in f
13 if n == 0:
14 RecursionError: maximum recursion depth exceeded in comparison
As you can see, Python has a strict limit on the stack. This should not pose any problem for
us during the semester in general. You should remember any recursive program can be written
using only unbounded loops–though it might be difficult and even tedious.
Problem 5: Visualization
One of the most heavily used elements of Python is its visualization. In this example we plot the
curve in Problem 2.
1. Inside Assignment_1, write this program:
1 import matplotlib.pyplot as plt
2 import numpy as np
3
4 data = np.linspace(-10,10,100)
5 fn = (1/10)*(data**3)
6
7
8 fig = plt.figure()
9 ax = fig.add_subplot(1, 1, 1)
10
11 ax.spines[’left’].set_position(’center’)
12 ax.spines[’bottom’].set_position(’zero’)
13 ax.spines[’right’].set_color(’none’)
Assignment № 1 Page 10
14 ax.spines[’top’].set_color(’none’)
15 ax.xaxis.set_ticks_position(’bottom’)
16 ax.yaxis.set_ticks_position(’left’)
17
18 plt.title(’$f(x) = (1/10)x^3$’)
19 plt.plot(data,fn, ’r’)
20 plt.show()
The output is shown in Fig. 1.
Figure 1: Visualizing f
Problem 6: Practice
1. The second derivative is the derivative of the first derivative. Let’s look out original example:
For example, let f(x) = x
3/10. Let’s find the value of the 2
nd derivative at x = 2.5.
f(x) = x
3
/10 (8)
f
0
(x) = ( 3
10 )x
2
(9)
f
00(x) = ( 2×3)
10 x = ( 3
5
)x (10)
Assignment № 1 Page 11
The value of f
00(2.5) = 1.5. Add a new function called der2 that takes a function and
returns the second derivative. Verify with the value 2.5.
2. Parametric problems are those for which we have (or assume to have) an underlying distribution. Two statistics we are always interested in (with context) are the mean and variance.
Assume we have a data set of non-negative integers |D| = n. The mean (a measure of
central tendency) is:
µ =
1
n
X
d∈D
d (11)
The variance is spread around µ and is:
σ
2 =
1
n
X
d∈D
(d − µ)
2
(12)
Write a program that generates 100 random integers from 0 to 100 inclusive (repeating)
and store them into an array. Find the mean and variance. The mean and variance should
be written as functions. Look-up the size attribute of numpy arrays before you begin.
3. This problem will take some thinking–it will help you understand the array type. In the
original plot, we created a second array implicitly on line 5. Python understood we had
an entire array as input and then created an array of values each applied to the values in
the initial array. For this problem, we’ll have to eschew this and create the arrays explicitly.
What we want to do is draw our original curve, but include the first derivative curve as well.
The challenge is that our derivative function is not compatiable with the array. So we need
to explicitly create two arrays, one with f (red) and another with f
0
(blue). See how far you
go. The output is in Fig. 2.
Figure 2: Visualizing f and its derivative.
Assignment № 1 Page 12