# Week 1 - Beginner Guide
Use this guide to support the discussion of the problems in the live sessions.

## Session 1

During the first session you are meeting your pod for the first time! You'll be grouped with your same pod each time, so the first session will be an icebreaker.

Go around and introduce yourselves! Once everyone has arrived in the breakout room, introduce yourself and tell everyone:

- Your Name
- Where you work (if any) or what internships you have done (for students)
- Where you went to school
- How you got into coding and CS
- What you want to be when you "grow up" / aspirations for learning
- Favorite coding joke
- Decide on a team emoji

Then have students go around and answer each question.

# 1. 1000 Digit Fibonacci
[ Original Problem Statement](https://projecteuler.net/problem=25):

[Repl.it WorkPad](https://repl.it/@lizthedeveloper/SE101-Session-2)

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

### Understand
Ensure students clarify input and output parameters of the problem:
- There is no input to this function, as the function determines a static value
- Do students notice the difference between the length of the number and the index of the number in the sequence?

**:exclamation:Before finishing this section, ensure the students have done the following:**
- Established a method for determining the next fibonacci number
- Identified a method for storing numbers
- Identified a method for determining the count of digits within the number

***NOTE:** Students tend to rush problems. Encouraging students to spend more time in the Understanding phase of the process may help them avoid issues later in the interview.*

## Match
*In the Matching step of UMPIRE, you want to think about common patterns and tricks that could apply to this problem.*

***NOTE:** At this point in the course, students may not be able to match problems to specific patterns.*

This problem involves *matching* from the Fibonacci problem in the videos and the problem sandbox - the best thing you can do when they're trying to figure out how to get prime factors is get them to recall this problem.

For Numbers, common solution patterns include:
- For loops
- While loops with a termination clause
- While loops with a break statement
- "If not"

For this problem students may lean towards a list, allow them to use a list if they understand how it is used, but if they struggle bring up that they might not need the list with a question like "what are we doing with the terms that are earlier than these two terms that we need to calculate the result?"

**:exclamation: Mentors it is important that the students consider all problem patterns.**

## Plan
**Before ANY pseudocode, have students explain their general idea.**

Ask students how they would manually determine the answer for the first fiboncacci digit to have four digits.

**Mentors, before diving into specifics about algorithms, have students give a 1-2 sentence summary on their approach.**
- This question may be too simple to generate a concise summary about; however, keep in mind moving forward that during the planning phase students should come up with 1-2 sentence summaries beforehand.

Sample Approach #1 (only pointers, iterate up)

1) Set two variables to the first two terms, 0 and 1
2) Set a variable to 2 to keep track of what index we're on
3) Begin a loop that will terminate when the length of the string value of the current term is 1000
4) Calculate the next number by adding the last two
5) Set the first term to be the second, the second to be the third, and then calculate the next term
6) Increment the index
7) End Loop
8) Return the index

Sample Approach #2 (Use a list)

1) Create a list and add the first two terms, 0 and 1
2) Begin a loop that will terminate when the length of the string value of the current term is 1000
3) Calculate the next number by adding the last two and append it to the list
4) End Loop
5) Return the index of last term in the list

**:exclamation: We won't get into time and space complexity until halfway through, but if students ask feel free to explain.**

After students devise their own algorithm or series of steps to solve this problem, ensure students run through their previous test cases. This verifies the proposed solution and ensures the student communicates well throughout the interview.

### :exclamation: Before moving to the next section, verify the following:
- Students have an established algorithm
- Students have verified this algorithm on their initial test cases

## Implement

Students should discuss how to translate their general algorithm into specific code before implementing.

Python Solution (Approach #1):

def fibonacci_1000():
  i = 0
  one = 0
  two = 1
  term = 0
  while len(str(term)) < 1000:
    term = one + two
    one = two
    two = term
    i += 1
  print(term)
  return i


print(fibonacci_1000())

Python Solution (Approach #2):

def fibonacci_1000():
  fib_terms = []
  while len(str(fib_terms[-1])) < 1000:
    fib_terms.append(fib_terms[-2] + fib_terms[-1])

  return fib_terms[-1]


print(fibonacci_1000())

### Advanced Debugging

Beginner students often have trouble "following" the code, or reading and interpreting what is happening. [Open up PythonTutor with them](http://www.pythontutor.com/visualize.html#mode=edit) and walk them through their code if they get stuck, or if one member of the team is having trouble following the progression of the code. This is most common among newer coders who are using Solution 1, as the multiple pointer variables can get confusing.

## Review
Verify the code works for small cases such as 4 or 10 digits. Afterwards, calculate the final result.

Discuss other possible methods, and if students ended up using a list, begin the discussion about how much memory it takes up to use a list, and if there is time try to guide students to use variables instead.

Don't worry about the formal complexity definitions, we'll be discussing it in unit 5.