Skip to content

Commit 9ef0e20

Browse files
R-ChavarroR-Chavarro
committed
cleaned up bad files from branch
1 parent 69f950d commit 9ef0e20

File tree

72 files changed

+388
-6034
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

72 files changed

+388
-6034
lines changed

‎Algorithm Analysis and Big O/.~Introduction to Algorithm Analysis and Big O .ipynb

Lines changed: 194 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,194 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {
6+
"collapsed": true,
7+
"slideshow": {
8+
"slide_type": "slide"
9+
}
10+
},
11+
"source": [
12+
"# Introduction to Algorithm Analysis and Big O\n",
13+
"\n",
14+
"In this lecture we will discuss how to analyze Algorithms and why it is important to do so!\n",
15+
"\n",
16+
"## Why analyze algorithms?\n",
17+
"\n",
18+
"Before we begin, let's clarify what an algorthim is. In this course, an **algorithm** is simply a procedure or formula for solving a problem. Some problems are famous enough that the algorithms have names, as well as some procdures being common enough that the algorithm associated with it also has a name. So now we have a good question we need to answer:\n",
19+
"\n",
20+
"** *How do analyze algorithms and how can we compare algorithms against each other?* **\n",
21+
"\n",
22+
"Imagine if you and a friend both came up with functions to sum the numbers from 0 to N. How would you compare the functions and algorithms within the functions? Let's say you both cam up with these two seperate functions:"
23+
]
24+
},
25+
{
26+
"cell_type": "code",
27+
"execution_count": 4,
28+
"metadata": {
29+
"collapsed": true
30+
},
31+
"outputs": [],
32+
"source": [
33+
"# First function (Note the use of xrange since this is in Python 2)\n",
34+
"def sum1(n):\n",
35+
" '''\n",
36+
" Take an input of n and return the sum of the numbers from 0 to n\n",
37+
" '''\n",
38+
" final_sum = 0\n",
39+
" for x in xrange(n+1): \n",
40+
" final_sum += x\n",
41+
" \n",
42+
" return final_sum"
43+
]
44+
},
45+
{
46+
"cell_type": "code",
47+
"execution_count": 5,
48+
"metadata": {
49+
"collapsed": false
50+
},
51+
"outputs": [
52+
{
53+
"data": {
54+
"text/plain": [
55+
"55"
56+
]
57+
},
58+
"execution_count": 5,
59+
"metadata": {},
60+
"output_type": "execute_result"
61+
}
62+
],
63+
"source": [
64+
"sum1(10)"
65+
]
66+
},
67+
{
68+
"cell_type": "code",
69+
"execution_count": 7,
70+
"metadata": {
71+
"collapsed": true
72+
},
73+
"outputs": [],
74+
"source": [
75+
"def sum2(n):\n",
76+
" \"\"\"\n",
77+
" Take an input of n and return the sum of the numbers from 0 to n\n",
78+
" \"\"\"\n",
79+
" return (n*(n+1))/2"
80+
]
81+
},
82+
{
83+
"cell_type": "code",
84+
"execution_count": 9,
85+
"metadata": {
86+
"collapsed": false
87+
},
88+
"outputs": [
89+
{
90+
"data": {
91+
"text/plain": [
92+
"55"
93+
]
94+
},
95+
"execution_count": 9,
96+
"metadata": {},
97+
"output_type": "execute_result"
98+
}
99+
],
100+
"source": [
101+
"sum2(10)"
102+
]
103+
},
104+
{
105+
"cell_type": "markdown",
106+
"metadata": {},
107+
"source": [
108+
"You'll notice both functions have the same result, but completely different algorithms. You'll note that the first function iteratively adds the numbers, while the second function makes use of:\n",
109+
"$$ \\sum_{i=0}^{n} {i} = \\frac{n(n+1)}{2} $$\n",
110+
"\n",
111+
"So how can we objectively compare the algorithms? We could compare the amount of space they take in memory or we could also compare how much time it takes each function to run. We can use the built in **%timeit** magic function in jupyter to compare the time of the functions. The [**%timeit**](https://ipython.org/ipython-doc/3/interactive/magics.html#magic-timeit) magic in Jupyter Notebooks will repeat the loop iteration a certain number of times and take the best result. Check out the link for the documentation. \n",
112+
"\n",
113+
"Let's go ahead and compare the time it took to run the functions:"
114+
]
115+
},
116+
{
117+
"cell_type": "code",
118+
"execution_count": 10,
119+
"metadata": {
120+
"collapsed": false
121+
},
122+
"outputs": [
123+
{
124+
"name": "stdout",
125+
"output_type": "stream",
126+
"text": [
127+
"The slowest run took 5.15 times longer than the fastest. This could mean that an intermediate result is being cached \n",
128+
"100000 loops, best of 3: 4.86 µs per loop\n"
129+
]
130+
}
131+
],
132+
"source": [
133+
"%timeit sum1(100)"
134+
]
135+
},
136+
{
137+
"cell_type": "code",
138+
"execution_count": 12,
139+
"metadata": {
140+
"collapsed": false
141+
},
142+
"outputs": [
143+
{
144+
"name": "stdout",
145+
"output_type": "stream",
146+
"text": [
147+
"The slowest run took 16.54 times longer than the fastest. This could mean that an intermediate result is being cached \n",
148+
"10000000 loops, best of 3: 173 ns per loop\n"
149+
]
150+
}
151+
],
152+
"source": [
153+
"%timeit sum2(100)"
154+
]
155+
},
156+
{
157+
"cell_type": "markdown",
158+
"metadata": {},
159+
"source": [
160+
"We can see that the second function is much more efficient! Running at a much faster rate than the first. However, we can not use \"time to run\" as an objective measurement, because that will depend on the speed of the computer itself and hardware capabilities. So we will need to use another method, **Big-O**!"
161+
]
162+
},
163+
{
164+
"cell_type": "markdown",
165+
"metadata": {
166+
"collapsed": true
167+
},
168+
"source": [
169+
"In the next lecture we will discuss Big-O notation and why its so important!"
170+
]
171+
}
172+
],
173+
"metadata": {
174+
"kernelspec": {
175+
"display_name": "Python 2",
176+
"language": "python",
177+
"name": "python2"
178+
},
179+
"language_info": {
180+
"codemirror_mode": {
181+
"name": "ipython",
182+
"version": 2
183+
},
184+
"file_extension": ".py",
185+
"mimetype": "text/x-python",
186+
"name": "python",
187+
"nbconvert_exporter": "python",
188+
"pygments_lexer": "ipython2",
189+
"version": "2.7.10"
190+
}
191+
},
192+
"nbformat": 4,
193+
"nbformat_minor": 0
194+
}

‎Algorithm Analysis and Big O/Introduction to Algorithm Analysis and Big O.ipynb

Lines changed: 194 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,194 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {
6+
"collapsed": true,
7+
"slideshow": {
8+
"slide_type": "slide"
9+
}
10+
},
11+
"source": [
12+
"# Introduction to Algorithm Analysis and Big O\n",
13+
"\n",
14+
"In this lecture we will discuss how to analyze Algorithms and why it is important to do so!\n",
15+
"\n",
16+
"## Why analyze algorithms?\n",
17+
"\n",
18+
"Before we begin, let's clarify what an algorthim is. In this course, an **algorithm** is simply a procedure or formula for solving a problem. Some problems are famous enough that the algorithms have names, as well as some procdures being common enough that the algorithm associated with it also has a name. So now we have a good question we need to answer:\n",
19+
"\n",
20+
"** *How do analyze algorithms and how can we compare algorithms against each other?* **\n",
21+
"\n",
22+
"Imagine if you and a friend both came up with functions to sum the numbers from 0 to N. How would you compare the functions and algorithms within the functions? Let's say you both cam up with these two seperate functions:"
23+
]
24+
},
25+
{
26+
"cell_type": "code",
27+
"execution_count": 4,
28+
"metadata": {
29+
"collapsed": true
30+
},
31+
"outputs": [],
32+
"source": [
33+
"# First function (Note the use of xrange since this is in Python 2)\n",
34+
"def sum1(n):\n",
35+
" '''\n",
36+
" Take an input of n and return the sum of the numbers from 0 to n\n",
37+
" '''\n",
38+
" final_sum = 0\n",
39+
" for x in xrange(n+1): \n",
40+
" final_sum += x\n",
41+
" \n",
42+
" return final_sum"
43+
]
44+
},
45+
{
46+
"cell_type": "code",
47+
"execution_count": 5,
48+
"metadata": {
49+
"collapsed": false
50+
},
51+
"outputs": [
52+
{
53+
"data": {
54+
"text/plain": [
55+
"55"
56+
]
57+
},
58+
"execution_count": 5,
59+
"metadata": {},
60+
"output_type": "execute_result"
61+
}
62+
],
63+
"source": [
64+
"sum1(10)"
65+
]
66+
},
67+
{
68+
"cell_type": "code",
69+
"execution_count": 7,
70+
"metadata": {
71+
"collapsed": true
72+
},
73+
"outputs": [],
74+
"source": [
75+
"def sum2(n):\n",
76+
" \"\"\"\n",
77+
" Take an input of n and return the sum of the numbers from 0 to n\n",
78+
" \"\"\"\n",
79+
" return (n*(n+1))/2"
80+
]
81+
},
82+
{
83+
"cell_type": "code",
84+
"execution_count": 9,
85+
"metadata": {
86+
"collapsed": false
87+
},
88+
"outputs": [
89+
{
90+
"data": {
91+
"text/plain": [
92+
"55"
93+
]
94+
},
95+
"execution_count": 9,
96+
"metadata": {},
97+
"output_type": "execute_result"
98+
}
99+
],
100+
"source": [
101+
"sum2(10)"
102+
]
103+
},
104+
{
105+
"cell_type": "markdown",
106+
"metadata": {},
107+
"source": [
108+
"You'll notice both functions have the same result, but completely different algorithms. You'll note that the first function iteratively adds the numbers, while the second function makes use of:\n",
109+
"$$ \\sum_{i=0}^{n} {i} = \\frac{n(n+1)}{2} $$\n",
110+
"\n",
111+
"So how can we objectively compare the algorithms? We could compare the amount of space they take in memory or we could also compare how much time it takes each function to run. We can use the built in **%timeit** magic function in jupyter to compare the time of the functions. The [**%timeit**](https://ipython.org/ipython-doc/3/interactive/magics.html#magic-timeit) magic in Jupyter Notebooks will repeat the loop iteration a certain number of times and take the best result. Check out the link for the documentation. \n",
112+
"\n",
113+
"Let's go ahead and compare the time it took to run the functions:"
114+
]
115+
},
116+
{
117+
"cell_type": "code",
118+
"execution_count": 10,
119+
"metadata": {
120+
"collapsed": false
121+
},
122+
"outputs": [
123+
{
124+
"name": "stdout",
125+
"output_type": "stream",
126+
"text": [
127+
"The slowest run took 5.15 times longer than the fastest. This could mean that an intermediate result is being cached \n",
128+
"100000 loops, best of 3: 4.86 µs per loop\n"
129+
]
130+
}
131+
],
132+
"source": [
133+
"%timeit sum1(100)"
134+
]
135+
},
136+
{
137+
"cell_type": "code",
138+
"execution_count": 12,
139+
"metadata": {
140+
"collapsed": false
141+
},
142+
"outputs": [
143+
{
144+
"name": "stdout",
145+
"output_type": "stream",
146+
"text": [
147+
"The slowest run took 16.54 times longer than the fastest. This could mean that an intermediate result is being cached \n",
148+
"10000000 loops, best of 3: 173 ns per loop\n"
149+
]
150+
}
151+
],
152+
"source": [
153+
"%timeit sum2(100)"
154+
]
155+
},
156+
{
157+
"cell_type": "markdown",
158+
"metadata": {},
159+
"source": [
160+
"We can see that the second function is much more efficient! Running at a much faster rate than the first. However, we can not use \"time to run\" as an objective measurement, because that will depend on the speed of the computer itself and hardware capabilities. So we will need to use another method, **Big-O**!"
161+
]
162+
},
163+
{
164+
"cell_type": "markdown",
165+
"metadata": {
166+
"collapsed": true
167+
},
168+
"source": [
169+
"In the next lecture we will discuss Big-O notation and why its so important!"
170+
]
171+
}
172+
],
173+
"metadata": {
174+
"kernelspec": {
175+
"display_name": "Python 2",
176+
"language": "python",
177+
"name": "python2"
178+
},
179+
"language_info": {
180+
"codemirror_mode": {
181+
"name": "ipython",
182+
"version": 2
183+
},
184+
"file_extension": ".py",
185+
"mimetype": "text/x-python",
186+
"name": "python",
187+
"nbconvert_exporter": "python",
188+
"pygments_lexer": "ipython2",
189+
"version": "2.7.10"
190+
}
191+
},
192+
"nbformat": 4,
193+
"nbformat_minor": 0
194+
}

0 commit comments

Comments
 (0)