By the end of this week, you should be able to:

- Understand and be able to design simple algorithms
- Apply problem-solving techniques in algorithm design
- Have installed PyCharm (A tool for Python programming) on your local computer

- All of the readings are in the module for the week

- Introduce Yourself
- Discussion - Design your own Algorithm
- Maze Solving
- Thought Problem: “How high can you count on five fingers?”
- Install PyCharm

**Algorithm**: A finite set of instructions that specify a sequence of operations to be carried out in order to solve a specific problem or class of problems- We judge an algorithm based on two criteria:
- Correctness
- Efficiency

- An algorithm is
*not*a program - a**program**is the concrete expression of an algorithm in a particular programming language - Guessing game - guess number between 1 and 16, with each guess you will be told high or low, what is the most efficient way to find the right number?
**Linear Search**- Start from number one and work your way up one number at a time. Will find the right answer, but it is inneficient and slow. In worst case it could take 16 guesses to find right answer.**Binary Search**- Guess the middle each time. Cuts the search space in half each time. At worst, it would take 5 guesses. This is the most efficient algorithm for this problem.

- Let’s try to design an algorithm for a maze, that you could always follow to solve any maze.

**Random Walk Algorithm**

- Move forward until there is either a left or right turn or a dead end
- If there is a left or right rurn, choose a random direction
- If you are at a dead end turn around

**Problem**: Can take a very long time

**Follow Right Wall Algorithm**

- Go in a straight line until you encounter a junction or a dead-end
- At a junction, always go to rightmost option from where you are currently facing
- At a dead-end, turn around 180 degrees

**Problem**: May get stuck in some mazes, or Islands - correctness

**Tremaux’s Algorithm**

- Charles Pierre Tremaux invented an algorithm for colving mazes:

- As you walk down the maze, draw a line on the path
- At a dead end, turn around and walk back the way you came
- At a junction you’ve not seen before, take any new path
- At junction you have been to before:
- If you are on a new path, turn back the way you came
- If you are on a path you’ve marked before, take a new path if you can

- Never go down a path already marked with two lines
- When your path reaches a junction, you choose an exit

- Solved solution: Link

```
moveForward();
moveForward();
```

- Solved solution: Link

```
moveForward();
turnLeft();
moveForward();
turnRight();
moveForward();
```

- Solved solution: Link

```
while (notDone()) {
moveForward();
}
```

- Solved solution: Link

```
while (notDone()) {
moveForward();
turnLeft();
moveForward();
turnRight();
}
```

- Solved solution: Link

```
moveForward();
moveForward();
turnLeft();
while (notDone()) {
moveForward();
}
```

- Solved solution: Link

```
while (notDone()) {
if (isPathLeft()) {
turnLeft();
}
moveForward();
}
```

- Solved solution: Link

```
while (notDone()) {
if (isPathForward()) {
moveForward();
}
if (isPathRight()) {
turnRight();
}
}
```

- Solved solution: Link

```
while (notDone()) {
if (isPathLeft()) {
turnLeft();
}
if (isPathRight()) {
turnRight();
}
moveForward();
}
```

- Solved solution: Link

```
while (notDone()) {
if (isPathForward()) {
moveForward();
} else {
if (isPathLeft()) {
turnLeft();
} else {
turnRight();
}
}
}
```

- Solved solution: Link

```
while (notDone()) {
if (isPathForward()) {
if (isPathRight()) {
turnRight();
} else {
if (isPathLeft()) {
turnLeft();
}
}
} else {
if (isPathLeft()) {
turnLeft();
} else {
turnRight();
}
}
moveForward();
}
```