C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 1 of n
Description
In mathematics, computer science, and related subjects, an 'algorithm' is an effective method for solving a problem expressed as a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields. (In more advanced or abstract settings, the instructions do not necessarily constitute a finite sequence, or even a sequence; see, for example, "nondeterministic algorithm".)
Each algorithm is a list of welldefined instructions for completing a task. Starting from an initial state, the instructions describe a computation that proceeds through a welldefined series of successive states, eventually terminating in a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate randomness.
Here, the great Yuri Gurevich, mathematician, computer scientist and inventor of abstract state machines, will teach us about algorithms beginning with this introductory lecture that includes plenty of historical context. This is the first in a series of lectures exploring the fundamental logic that powers all that we as software engineers and computer scientists do in computingthe algorithm. What is an algorithm, exactly? You may be surprised to learn that this is actually not a very simple question...
Find some time to watch this introduction on a truly fascinating topic by one of the world's premiere minds in the field of mathematical logic and algorithms. We designed this to increase in complexity over time, like a typical college course, so Yuri moves slowly through several topics, providing plenty of time for viewers to catch up before moving on to more advanced topics.
Thank you, Yuri, for taking the time to share your extensive knowledge and gentle, kind spirit with Niner nation. We all really appreciate it! Thanks, too, to Karsten and Sampy for being our live audience for this lecture and asking great questions!
See Part 2
See Part 3
Share
Download
Download this episode
 High Quality WMV (1.1 GB)
 MP3 (37.2 MB)
 Low Quality MP4 (406.9 MB)
 Mid Quality WMV (655.2 MB)
More episodes in this series
C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 3 of…
Related episodes
C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 3 of…
C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 2 of…
C9 Conversations: Yuri Gurevich On Logic, Imperative, Abstraction and Algorithms
E2E: Erik Meijer and Leslie Lamport  Mathematical Reasoning and Distributed Systems
Brian Beckman: Hidden Markov Models, Viterbi Algorithm, LINQ, Rx and Higgs Boson
C9 Lectures: Greg Meredith  Monadic Design Patterns for the Web 4 of 4
ICSE 2011: Victor Pankratius  Developing Manycore Applications with Concurrency…
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 7 of n
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 6 of n
E2E: Whiteboard Jam Session with Brian Beckman and Greg Meredith  Monads and Coordinate…
The Discussion

This looks awesome.

My thoughts exactly!!! Wow Charles ... this is awesome stuff! As you know, we (C9ers) love the technical content!! Now I've gotta listen to the first interview with Yuri again!
Keep it coming!

Thanks for a great lecture!
It reminds me "Feynman Lectures on Computation."
I'm watching this video with his book.
iStation
p.s.
It is interesting that computer science flourished before modern computer.

This promises to be an awesome series. Specially for people like me, not belonging to Computer Science Backgroud though we have tons of experience.
Keep up Yuri! This is a service to nonCS developers.

Fantastic! Fantastic! Fantastic! Fantastic!!!

Even for people with a CS background, this is a great lecture. I didn't realize there were other kinds of computing models (Pointer machines, Kolmogarov machines). He also gave some great algorithm examples that you can't computer (bucketsofrain) or that are too slow (real arithmetic).
Great start to a very promising series, thank you!

excellent stuff ! long live channel 9 !

Just watched this (again... I was in the room...). Incredible lecture, Yuri. So much great information and the historical approach made learning the concepts real (as in not purely abstract). Reminds me of my days at Evergreen State, where professors would not only teach the mechanics of, say, calculus, but also explore the historical and philosophical contexts that surrounded the discipline (which in some sense, drove the thinking behind it and also grabbed the attention of more students > it's important to provide concrete conceptual handles to very abstract topics).
Yuri is very humble by nature. It should be made clear that his contributions to this field were and continue to be very significant.
I am really looking forward to the next lecture in this series. Thank you, Yuri.
C9 University. I like the sound of that (I can't remember which Niner coined this term, but you know who you are)
Happy holidays to all American Niners. Have a fun 4th (and be safe with those Roman Candles).
To all Niners, keep on learning.
C

I wanted to go out shopping yesterday and Yuri diverted those plans.
Looking forward to the next installment.

Great content, great man. keep on going. thanks

Thank you very much sir for great lecture.

I watched this last week, and feel I need to watch it again.

We miss Yuri and a little math, when will see him again?

In a few months. These lectures will progress slowly, as Yuri has many deadlines....
C

Simply brilliant !! the presenter is so into his subject, using "simple" examples to illusrtate not so simple concepts.
One little detail kinda "astonished" me: historically, the greek science was no lost, but transmitted to the renaissance europe through the arab civilisation (remember that algorithm is the name european gave to Alkhawarizmi, an arab mathematician).
Anyway, great lecture, birlliant presenter : keep'em coming :) 
As the title suggests 1 of n. Please, at least get us 2 of n.

Agreed. Whoever is contributing to Yuri's deadlines needs to go on vacation for a while.

This reminds me of the beauty of CS when it comes from the right teacher.

<h3>I recommend the book,</h3>
<p> </p>
<h3>How Mathematicians Think:<br />Using Ambiguity, Contradiction, and Paradox to Create Mathematics</h3>
<h3> </h3>
<h3>by</h3>
<h3><br /><span>William Byers</span></h3>
<p> </p>
<p> </p>