This course is offered through Coursera — you can add it to your Accredible profile to organize your learning, find others learning the same thing and to showcase evidence of your learning on your CV with Accredible's export features.
Course Date: 05 September 2014 to 17 October 2014 (6 weeks)
This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers basic iterable data types, sorting, and searching algorithms.
Kevin Wayne is the Phillip Y. Goldman Senior Lecturer in Computer Science at Princeton University, where he has been teaching since 1998. He received a Ph.D. in operations research and industrial engineering from Cornell University. His research interests include the design, analysis, and implementation of algorithms, especially for graphs and discrete optimization. With Robert Sedgewick, he is the coauthor of two highly acclaimed textbooks, Introduction to Programming in Java: An Interdisciplinary Approach (Addison-Wesley, 2008) and Algorithms, 4th Edition (Addison-Wesley Professional 2011). For his teaching, he has won the School of Engineering and Applied Science's Distinguished Teacher Award and the Engineering Council's Excellence in Teaching Award.
Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton, where he was the founding chair of the Department of Computer Science. He received the Ph.D. degree from Stanford University, in 1975. Prof. Sedgewick also served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Palo Alto, CA, Institute for Defense Analyses, Princeton, NJ, and INRIA, Rocquencourt, France. He is a member of the board of directors of Adobe Systems. Prof. Sedgewick's interests are in analytic combinatorics, algorithm design, the scientific analysis of algorithms, curriculum development, and innovations in the dissemination of knowledge. He has published widely in these areas and is the author of several books.
An introduction to fundamental data types, algorithms, and data structures,
with emphasis on applications and scientific performance analysis of Java
implementations. Specific topics covered include: union-find algorithms;
basic iterable data types (stack, queues, and bags); sorting algorithms
(quicksort, mergesort, heapsort) and applications; priority queues; binary
search trees; red-black trees; hash tables; and symbol-table applications.
What algorithms and data structures are covered?
Part I focuses on elementary data structures, sorting, and searching.
Topics include union-find, binary search, stacks, queues, bags, insertion
sort, selection sort, shellsort, quicksort, 3-way quicksort, mergesort,heapsort,
binary heaps, binary search trees, red-black trees, separate chaining and
linear probing hash tables, Graham scan, and kd-trees.
Part II focuses on graph and string-processing algorithms. Topics include
depth-first search, breadth-first search, topological sort, Kosaraju-Sharir,
Kruskal, Prim, Dijkistra, Bellman-Ford, Ford-Fulkerson, LSD radix sort,
MSD radix sort, 3-way radix quicksort, multiway tries, ternary search tries,
Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, regular expression matching,
run-length coding, Huffman coding, LZW compression, and the Burrows-Wheeler
Are there any associated resources available on the web?
Yes. Our free booksite contains
synopses of the text, web exercises, Java implementations of all the algorithms
covered (any many more) that are designed for you to be able to download
and use with one click, test data, and many other resources.
How does this course differ from Design and Analysis of Algorithms?
The two courses are complementary. This one is essentially a programming
course that concentrates on developing code; that one is essentially a
math course that concentrates on understanding proofs. This course is about
learning algorithms in the context of implementing and testing them in
practical applications; that one is about learning algorithms in the context
of developing mathematical models that help explain why they are efficient.
In typical computer science curriculums, a course like this one is taken
by first- and second-year students and a course like that one is taken
by juniors and seniors.
I am/was not a computer science major. Is this course for me?
Yes. This course is for anyone using a computer to address large problems
(and therefore needing efficient algorithms). At Princeton, over 25% of
all students take the course, including people majoring in engineering,
biology, physics, chemistry, economics, and many other fields, not just
If I have no familiarity with Java programming, can I still take the course?
Our central thesis is that algorithms are best understood by implementing
and testing them. Our use of Java is essentially expository, and we shy
away from exotic features, so we expect you would be able to adapt our
code to your favorite language. However, we require that you submit the
programming assignments in Java. If you have some experience programming
in another language, you might find it worthwhile to learn our programming
model by studying our book An Introduction to Programming in Java: An Interdisciplinary
Approach and associated free booksite.
If I have not programmed before, can I still take the course?
Does Princeton University award credentials or reports regarding my work in this course?
No certificates, statements of accomplishment, or other credentials will
be awarded in connection with this course.
There will be two lectures (60-75 minutes each) each week. The lectures are
divided into about 4-6 segments, separated by interactive quiz questions
for you to to help you process and understand the material. In addition,
there will be a problem set and a programming assignment each week and
there will be a final exam.
Although the lectures are designed to be self-contained, students wanting
to expand their knowledge beyond what we can cover in a 6-week class can
find a much more extensive coverage of this topic in our book Algorithms, Part I (4th Edition), published by Addison-Wesley.