Algorithms, Part I

Kevin Wayne and Robert Sedgewick, Princeton University

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.

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.

Recommended Background

All you need is a basic familiarity with programming in Java. This course is primarily aimed at first- and second-year undergraduates interested in engineering or science, along with high school students and professionals with an interest (and some background) in programming.

Suggested Readings

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 (4th Edition), published by Addison-Wesley Professional.

Course Format

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.

FAQ

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

  • 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 (and 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 computer science.

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

    Probably not.

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

Dates:
  • 22 January 2016, 6 weeks
  • 4 September 2015, 6 weeks
  • 4 September 2015, 6 weeks
  • 19 June 2015, 6 weeks
  • 23 January 2015, 6 weeks
  • 5 September 2014, 6 weeks
  • 13 June 2014, 6 weeks
  • 31 January 2014, 6 weeks
  • 23 August 2013, 6 weeks
  • 4 February 2013, 6 weeks
  • 12 August 2012, 6 weeks
  • Details to be announced
Course properties:
  • Free:
  • Paid:
  • Certificate:
  • MOOC:
  • Video:
  • Audio:
  • Email-course:
  • Language: English Gb

Reviews

No reviews yet. Want to be the first?

Register to leave a review

Included in selections:
6-046jf05 Algorithms
Algorithms and data structures from the beginning to advanced analysis.
Vyyjayfzd3pynkssdhnqwcrx4bk4ennc1-ren956ujr2e1pya9umefxe-z08yngaz4nptzjr4nqcte0whwul=s0#w=1724&h=1060 Алгоритмизация вычислений
1 курс МИЭМ ВШЭ, 4 кредита
More on this topic:
Images_course_image-262x136 30240184x: Data Structures • 数据结构
Learn the basics of data structures and methods to design algorithms and analyze...
Extensionflag Data Structures
This course is a survey of fundamental data structures for information...
65522_3a49_5 Information Retrieval and Mining Massive Data Sets
Learn various techniques to build a Google scale Information Retrieval System...
Cs224n Natural Language Processing
This course is designed to introduce students to the fundamental concepts and...
40684_d8c2_5 Data Organization - Learn Big Data Management - Udemy
Infrastructure, Algorithms, and Visualizations
More from 'Engineering & Technology':
Regular_23a1c71e-65c8-40a4-a9e5-79a192768f06 Maths Puzzles: Cryptarithms, Symbologies and Secret Codes
Explore and solve encrypted maths puzzles, in which numbers are replaced by...
Regular_dce4ba33-6339-4af2-b880-8f7a60dde10d Battery Storage Technology: Opportunities and Uses
Explore battery storage technology - how and why it works, and how it could...
Regular_dfd02155-57c0-4276-82a4-73ad33e18b85 Project Management Principles, Practices and Systems
Grow your project management skills, and understand project management methodologies...
Regular_e5858e9c-5d4f-4760-bc33-3c73e8b4a7b3 What is Genetic Counselling?
Learn about genetic counselling and what genetic counsellors do with this online...
8f9c73ef-73f5-45dd-aca1-7dad3696f743-552e331333d3.small Circuits and Electronics 1: Basic Circuit Analysis
Learn techniques that are foundational to the design of microchips used in smartphones...
More from 'Coursera':
Success-from-the-start-2 First Year Teaching (Secondary Grades) - Success from the Start
Success with your students starts on Day 1. Learn from NTC's 25 years developing...
New-york-city-78181 Understanding 9/11: Why Did al Qai’da Attack America?
This course will explore the forces that led to the 9/11 attacks and the policies...
Small-icon.hover Aboriginal Worldviews and Education
This course will explore indigenous ways of knowing and how this knowledge can...
Ac-logo Analytic Combinatorics
Analytic Combinatorics teaches a calculus that enables precise quantitative...
Talk_bubble_fin2 Accountable Talk®: Conversation that Works
Designed for teachers and learners in every setting - in school and out, in...

© 2013-2019