Algorithmic Thinking

Prof. Dr. Mirco Schoenfeld

Applied Programming

In this seminar, we want to get to know computational thinking.

Applied Programming

Ada Lovelace

Carpenter (1836)

Applied Programming

Lovelace describes an algorithm to compute Bernoulli numbers in her notes to Babbage’s lecture notes in 1842.

Lovelace (1842)

Applied Programming

It is considered to be the first published algorithm ever specifically tailored for implementation on a computer.

Lovelace (1842)

Algorithms: A definition

Algorithms are finite sequences of instructions,
typically used to solve specific problems.

Algorithms vs. Programs

Algorithms

abstract description
hardware independent
language agnostic

Programs

concrete list of instructions
written in a specific language
solve exactly one problem

Dead-Simple Programs

Let’s look at some dead simple programs.

Finite-state automata

https://en.wikipedia.org/wiki/File:Compass_vending_machines_at_King_George_station.jpg

https://commons.wikimedia.org/wiki/File:Tornelli.jpg

https://www.nw.de/nachrichten/zwischen_weser_und_rhein/23904169_Grillwurst-to-go-Hier-stehen-Fleischautomaten-in-Ostwestfalen-Lippe.html

https://www.kikkoman.com/en/culture/foodforum/trends-in-taste/36-4.html

https://gruene-fraktion-wuerzburg.de/vorziehen-von-planung-und-realisierung-der-ampelkreuzung-am-knoten-k4/

Finite-state automata

Such systems are called Finite-state automata (FSA)

finite-state machines,

finite automata,

or simply state machines.

Finite-state automata

An FSA is an abstract machine that can be in
exactly one of a finite number of states at any given time.

FSA can change from one state to another in response to inputs.

Finite-state automata

Finite-state automata have

little computational power
their memory limited to the number of states
no functionality to write their state persistently

Finite-state automata: the turnstile

https://commons.wikimedia.org/wiki/File:Tornelli.jpg

Finite-state automata: the turnstile

https://commons.wikimedia.org/wiki/File:Turnstile_state_machine_colored.svg

That is a state diagram.

Nodes (circles) represent states, edges (arrows) represent transitions from one state to another.

Why do we consider this?

FSA enable automation

Goddard (2024)

FSA enable automation.

It’s your turn!

Task

Develop a state diagram

Give an example of an application, scenario, machine, game, etc.
that requires some level of automation
identify inputs
identify states
use inputs as transitions between states

Inspirations: Apple Sorting Machine, Useless Machine, Whack a Mole

Time: 30 minutes

Task Summary

Let’s summarize!

https://xkcd.com/627/

Today’s computers

https://commons.wikimedia.org/wiki/File:ASRock_K7VT4A_Pro_Mainboard.jpg

Today’s computers

Today’s computers are based on the von Neumann model often implemented using a x86-64 architecture.

https://commons.wikimedia.org/wiki/File:AMD_Opteron_146_Venus,_2005.jpg

Today’s computers

At it’s core, they deal with 0 and 1.

https://commons.wikimedia.org/wiki/File:Standby_switch.jpg

What are today’s computers?

Imagine a Modern CPU. Every bit in a machine can only be in two states (0 or 1).

Therefore, there are a finite number of possible states.

In addition, when considering the parts of a computer a CPU interacts with, there are a finite number of possible inputs from the computer’s mouse, keyboard, hard disk, different slot cards, etc.

As a result, one can conclude that a CPU can be modeled as a finite-state machine.

Aziz, Cackler, and Yung (2004)

What are today’s computers?

Is a modern computer a finite-state machine?

What are today’s computers?

Now, consider a computer.

Although every bit in a machine can only be in two different states (0 or 1), there are an infinite number of interactions within the computer as a whole.

It becomes exceeding difficult to model the workings of a computer within the constraints of a finite-state machine.
However, higher-level, infinite and more powerful automata would be capable of carrying out this task.

Aziz, Cackler, and Yung (2004)

Turing machine

The first “infinite” model of computation
was conceived by Alan Turing.

It is known as the Turing machine.

Turing machine

https://en.wikipedia.org/wiki/File:Turing_Machine_Model_Davey_2012.jpg

From Turing machines to modern PCs

The difference to FSA lies in the capability of a Turing machine to change symbols on its tape thereby simulating computer execution and storage.

From Turing machines to modern PCs

It can be said that the Turing Machine has the power to model all computations that can be calculated today through modern computers.

Aziz, Cackler, and Yung (2004)

Turing limitations

There are two major limitations in the analogy between Turing machines and modern PCs:

modern PCs are Random-Access Stored-Program machines separating programs from instruction memory. That allows for some computational optimizations.
modern PCs are interacted with. So the model of a computer producing outputs based on inputs rarely matches how interactions actually happens.

digression

From states to programs

Let’s move from states and programs to algorithms.

Algorithms

Remember, algorithms are

abstract description
hardware independent
language agnostic

Algorithms

Algorithms are much like a cooking recipe

https://www.lovefood.com/gallerylist/87632/shockingly-bad-food-nightmares-we-just-cant-forget

It’s your turn!

Task

Escape the maze!

Develop a general strategy to find a path from the red entrance to the green exit.

Do not ask ChatGPT 😜

If you are an experienced programmer, you can think about implementing
your strategy in python. Please check out this framework!

Time: 45 minutes

Task Summary

What is your strategy?

It’s your turn!

Task

Translating the general strategy

Translate your general strategy in program code. Use this set of functions to have your agent take the corresponding action:

move() to move your agent forward
turnLeft() and turnRight() to turn your agent
canMove() to tell you’re blocked by a wall
visitedBefore() to tell you if you have visited a path before
isExit() which tells you if you have reached the exit

Is there any other functionality you need?

If you are an experienced programmer, you can implement
your strategy in python using this framework!

Time: 45 minutes

Task Summary

Were you able to translate your strategy?

Were you missing some functionality?

What was your approach?

References

Aziz, Amal Dar, Joe Cackler, and Raylene Yung. 2004. “Automata Theory.” Online. https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/index.html.

Carpenter, Margaret Sarah. 1836. “File:ada Lovelace.jpg.” https://commons.wikimedia.org/w/index.php?title=File:Ada_Lovelace.jpg&oldid=890224213.

Goddard, Wayne. 2024. Intro to Theory of Computation. Online. https://people.computing.clemson.edu/~goddard/handouts/cpsc3500/.

Lovelace, Ada. 1842. “File:diagram for the Computation of Bernoulli Numbers.jpg — Wikimedia Commons, the Free Media Repository.” https://commons.wikimedia.org/w/index.php?title=File:Diagram_for_the_computation_of_Bernoulli_numbers.jpg&oldid=874462909.