0:01

Welcome. I'm Bob Sedgewick, professor of computer science at Princeton. This is our

Â online course Algorithms developed by myself and Kevin Wayne here at Princeton.

Â We're gonna start with an overview discussion of why you might want to study

Â algorithms and a little bit of discussion about the resources that you need to take

Â this course. So, what is this course? It's an intermediate level survey course on

Â algorithms. We're going to concentrate on programming and problem solving in the

Â context of real applications, and our focus is going to be on two things,

Â Algorithms which are methods for solving problems and data structures which store

Â the information associated in problem, with a problem and go hand in hand with

Â algorithms. These are the basic topics that we'll cover in part one and part two

Â of the course. The first part is data type sorting and searching. We'll consider a

Â number of data structures and algorithms that are basic to all the methods we

Â consider including stacks, queues, bags and priority queues. Then we'll consider

Â classic algorithms for sorting, putting things in order. That's quicksort,

Â mergesort, heapsort and radix sorts. And we'll consider classic methods for

Â searching. Including binary search trees, red-black binary search trees and hash

Â tables. The second part of the course is for more advanced algorithms including

Â graph algorithms, classic graph searching algorithms, minimum spanning tree and

Â shortest path algorithms, algorithms for processing strings including regular

Â expressions and data compression. And then some advanced algorithms that make use of

Â the basic algorithms that we developed earlier in the course. So, why should one

Â study algorithms? Well, their input, impact is very broad and far-reaching.

Â From the internet to biology to, commercial computing, computer graphics,

Â security, multimedia, social networks, and scientific applications, algorithms are

Â all around us. They're used for movies and video games, for particle collision

Â simulation, they're used to study the genome, and all manner of other

Â applications. So, that's one important reason to study algorithms, their impact

Â is broad and far-reaching. Algorithms are also interesting to study, because they,

Â they have ancient roots. Now the first algorithm we studied goes back to 300

Â B.C., dating at least to Euclid. The concept of an algorithm was formalized

Â actually here at Princeton, by Church and Turing, in the 1930s. But most algorithms

Â that we consider, were discovered in recent decades. In fact, some were

Â discovered by undergraduates in a course, course like this. And there's plenty of

Â other algorithms waiting to be discovered by students like you. The main reason that

Â people study algorithms, is to be able to solve problems that it could not otherwise

Â be addressed. For example, in the first lecture, we're going to talk about the

Â network connectivity problem, where the problem is, given a large set of items

Â that are connected together pairwise is there a way to get from one to another

Â with a path through the connections. As you can see from this example, it's not

Â clear whether or not there's such a path, we need a computer program to do it, in

Â fact, we need an efficient algorithm to do it. In this case the answer is that there

Â is such a path. Another reason to study algorithms is for intellectual

Â stimulation. Algorithms are very interesting objects to study. Don Knuth

Â who wrote several books on, on algorithms and was a pioneer in the field said that,

Â "An algorithm must be seen to be believed." You can't just think about an

Â algorithm you have to work with it. Another quote from Francis Sullivan, says,

Â "The great algorithms are the poetry of computation." Just like verse, they can be

Â terse, elusive, dense, and even mysterious. But once unlocked, they cast a

Â brilliant new light on some aspect of computing. Algorithms are interesting for

Â intellectual stimulation. Another reason many people study algorithms and I suspect

Â many of you, is it's necessary to understand good algorithms, efficient

Â algorithms, a good data structures in order to be a proficient programmer. Linus

Â Torvalds, who created lin, Linux, says that the difference between a bad

Â programmer and a good one is whether he considers his code or his data structures

Â more important. Bad programmers worry about the code, good programmers worry

Â about data structures, and their relationships. And, I might add, the

Â algorithms that process them. Niklaus Wirth, another pioneer in computer

Â science, wrote a famous book called Algorithms + Data Structures = Programs.

Â [cough]. Another reason nowadays to study algorithms is that, they have become a

Â common language for understanding, nature. Algorithms are computational models, and

Â algorithmic models are replacing mathematical models in scientific inquiry.

Â In the twentieth century, math, scientists developed mathematical models to try to

Â understand natural phenomenon. It soon became clear that those mathematical

Â models were difficult to solve. It was difficult to create solutions, to be able

Â to test hypotheses against natural phenomenon. So, more and more and more now

Â a days people are developing computational models, where they attempt to simulate

Â what might be happening in nature in order to try to better understand it. Algorithms

Â play an extremely important role in this process. And we'll see some examples of

Â this in this course. Another important reason is that if you know effect, how to

Â effectively use algorithms and data structures you're going to have a much

Â better chance at interviewing for a job in the technology industry then if you don't.

Â So, here's a bunch of reasons that I just went through for studying algorithms.

Â Their impact's broad and far-reaching, they have old roots and present new

Â opportunities, they allow us to solve problems that could not otherwise be

Â addressed, you can use them for intellectual stimulation to become a

Â proficient programmer. They might unlock the secrets of life in the universe, and

Â they're good for fun and profit. In fact, a pr ogrammer might ask, why study

Â anything else? Well, there's plenty of good reasons to study other things, but

Â I'll submit there's no good reason not to study algorithims. [cough] So, for this

Â course we have two resources that I want to talk about and make sure that people

Â are familiar with before entering into the content. This is a publishing model that

Â Kevin Wayne and I developed and have been using for many years, and we think it's a

Â very effective way to support the, kinds of lectures that we're going to be giving

Â in this course. Down at the bottom, and it's optional for this course, we have a

Â text book. It's a traditional, text book that extensively covers the topics in the

Â course, in fact many more topics than we can present in lecture. And then

Â supporting that textbook, is free online material that we call the book site. You

Â can go to books, the book site to see the lecture slides. But more important,

Â there's code, there's exercises, tere's a great deal of information there. In fact,

Â maybe ten times what's in the book, including a summary of the content. So,

Â during this course you'll be referring to the book site frequently while working

Â online. People often ask about prerequisites. We're assuming that people

Â who take this course know how to program, and know the basics of loops, arrays,

Â functions. They have some exposure to object oriented programming and recursion.

Â We use the Java language, but we don't dwell on details of Java, we mostly use it

Â as an expository language. We do some math, but not advanced math. If you want

Â to review the material that we think is prerequisite for the material in this

Â course, you can do a quick review by looking at sections 1.1 and 1.2 of the

Â book. Either at the book site or in the text book. If you want an in depth review,

Â we have a full text book called, An Introduction to Programming in Java: An

Â Interdisciplinary Approach. There is a book site and text book as well. But, the

Â bottom line is, you should be able t o program, and the quick exercise to get

Â ready is, to write a java program on your computer perhaps using a programming

Â model, as described on the book site. We will provide much more detail information

Â on that as we get into the assignments. You can use your own programming

Â environment if your comfortable with one or you download ours. We have instructions

Â on the web on how to do that.

Â