def factorial(n):
	if n == 0:      # base case
		return 1
	return n * factorial(n-1)

def double(n):
	return 2 * n

def triple(n):
	return n + double(n)

print(triple(5))

def fibonnaci(n):
	if n == 1:    # base cases
		return 1
	if n == 0:          
		return 0

	return fibonnaci(n-1) + fibonnaci(n-2)

fib(3)                    +  fib(2)
fib(2)          + fib(1)  +  fib(2)
fib(1) + fib(0) + fib(1)  +  fib(2)
1      + fib(0) + fib(1)  +  fib(2)
1      + 0      + fib(1)  +  fib(2)
1      + 0      + 1       +  fib(2)
1      + 0      + 1       +  fib(1) + fib(0)
1      + 0      + 1       +  1      + fib(0)
1      + 0      + 1       +  1      + 0
3

# Set up our data structures
DICT = {}
infile = open("wordlist.txt", 'r')
for x in infile: # x goes through each line in the file
	DICT[x.strip()] = 0 # Creates an entry in DICT with key x.strip() and value 0
print(len(DICT))
infile.close() # close the file after we’re done with it.

WORDLIST = []
for y in DICT: # put the DICT keys into WORDLIST
	WORDLIST.append(y)
print(len(WORDLIST))

# Algorithm 1 - Lists
from time import time
start = time()
infile = open("PeterPan.txt", 'r')
largeText = infile.read()
infile.close()
counter = 0
words = largeText.split()
for x in words:
	x = x.strip("\"\'()[]{},.?<>:;-").lower()
	if x in WORDLIST:
		counter += 1
end = time()
print(counter)
print("Time elapsed with WORDLIST (in seconds):", end - start)

# Algorithm 2 - Dictionaries
start = time()
infile = open("PeterPan.txt", 'r')
largeText = infile.read()
infile.close()
words = largeText.split()
counter = 0
for x in words:
	x = x.strip("\"\'()[]{},.?<>:;-").lower()
	if x in DICT: # Searching through the DICT
		counter += 1
end = time()
print(counter)
print("Time elapsed with DICT (in seconds):", end - start)

Time:
* In-person (BIOEN 1001), Thursday 8/24 9:30am - 10:50am PST

Logistics:
* Bring a writing utensil and student ID
* Please write legibly (if we can't read your answer, we can't grade it)
* When leaving the room, you must hand in your exam and present your ID
* Closed book (no notes / book / electronic devices)
* TAs and I will be proctoring the exam. We can answer any CLARIFYING questions

Possible Types of Questions:
* True / False (if False, briefly state why (1 sentence))
* Short Answer - Briefly define / state / describe / ...
* Given some code, write the output / state the O-notation
* Write code satisfying a specification
* Given some partial algorithm, fill in the blank to make it work
* Draw diagrams

Midterm Topics:

Will cover material from the beginning of the class up until the end of week 2 lecture, h00 - h03, lab00 - lab03

Python Basics 
- Types
    * I don't expect students to know ALL Python basics, but do expect students to know the ones we explicitly covered in lectures and/or assignments
    * int, float, boolean, strings, lists, sets, dictionaries, ...
    * conversion functions (int(), float(), str(), ...)
    * mutable vs. immutable
- Relational / logical operators (==, <, >, <=, >=, and, or, not, ...)
- Python Lists
    * Supporting methods (count, pop, append, insert, ...)
    * List / string slicing [:]
- Strings
    * Supporting methods (replace, split, find, ...)
- Function definitions
- Control Structures (if, else, elif, for, while, ...)

Python Errors / Exceptions
- Runtime vs. Syntax
- Exception types
- Exception handling
    * try / except / raise
    * Flow of execution
    * Passing exceptions to function / method caller(s) when not handled in try / except
    * Multiple except blocks
    * Handling Exceptions in an Inheritance hierarchy

Object Oriented Programming
- Defining classes and methods
- constructors (defining / initializing default state)
- Shallow vs. Deep equality (overloading __eq__ method)
- Overloading operators (__str__, __add__, __le__, ...)
- Inheritance
    * Know method lookup for inheritance hierarchy
    * implementation for inherited fields / methods
    * overriding inherited methods
    * calling super / base class(es) methods

Testing
- Test Driven Development (TDD)
- pytest

Algorithm Analysis and O-notation
- Know how to derive O-notation for snippets of code

Recursion
- Implementation of recursive functions
- Understanding how recursive algorithms are managed by the call stack
- Note: I'll defer deriving O-notation questions for recursive functions / methods to the final exam