﻿ Week_1_Notes.md

# Week 1

## Overview

### Objectives

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

### Activities & Assignments

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

## Lesson

### Algorithms

• 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.

### Algorithm for a Maze

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

### Maze Solution #1 - The Random Approach

Random Walk Algorithm

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

Problem: Can take a very long time

### Maze Solution #2 - Follow the right wall

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

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

### Maze Solution #3 - Tremauz’s Algorithm

Tremaux’s Algorithm

• Charles Pierre Tremaux invented an algorithm for colving mazes:
1. As you walk down the maze, draw a line on the path
2. At a dead end, turn around and walk back the way you came
3. At a junction you’ve not seen before, take any new path
4. At junction you have been to before:
1. If you are on a new path, turn back the way you came
2. If you are on a path you’ve marked before, take a new path if you can
5. Never go down a path already marked with two lines
6. When your path reaches a junction, you choose an exit

## Homework

### Maze Solving Game

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