Algorithms, Part II from Coursera

What's inside

Syllabus

Introduction

Welcome to Algorithms, Part II.

Undirected Graphs

We define an undirected graph API and consider the adjacency-matrix and adjacency-lists representations. We introduce two classic algorithms for searching a graph—depth-first search and breadth-first search. We also consider the problem of computing connected components and conclude with related problems and applications.

Directed Graphs

In this lecture we study directed graphs. We begin with depth-first search and breadth-first search in digraphs and describe applications ranging from garbage collection to web crawling. Next, we introduce a depth-first search based algorithm for computing the topological order of an acyclic digraph. Finally, we implement the Kosaraju−Sharir algorithm for computing the strong components of a digraph.

Minimum Spanning Trees

In this lecture we study the minimum spanning tree problem. We begin by considering a generic greedy algorithm for the problem. Next, we consider and implement two classic algorithm for the problem—Kruskal's algorithm and Prim's algorithm. We conclude with some applications and open problems.

Shortest Paths

In this lecture we study shortest-paths problems. We begin by analyzing some basic properties of shortest paths and a generic algorithm for the problem. We introduce and analyze Dijkstra's algorithm for shortest-paths problems with nonnegative weights. Next, we consider an even faster algorithm for DAGs, which works even if the weights are negative. We conclude with the Bellman−Ford−Moore algorithm for edge-weighted digraphs with no negative cycles. We also consider applications ranging from content-aware fill to arbitrage.

Maximum Flow and Minimum Cut

In this lecture we introduce the maximum flow and minimum cut problems. We begin with the Ford−Fulkerson algorithm. To analyze its correctness, we establish the maxflow−mincut theorem. Next, we consider an efficient implementation of the Ford−Fulkerson algorithm, using the shortest augmenting path rule. Finally, we consider applications, including bipartite matching and baseball elimination.

Radix Sorts

In this lecture we consider specialized sorting algorithms for strings and related objects. We begin with a subroutine to sort integers in a small range. We then consider two classic radix sorting algorithms—LSD and MSD radix sorts. Next, we consider an especially efficient variant, which is a hybrid of MSD radix sort and quicksort known as 3-way radix quicksort. We conclude with suffix sorting and related applications.

Tries

In this lecture we consider specialized algorithms for symbol tables with string keys. Our goal is a data structure that is as fast as hashing and even more flexible than binary search trees. We begin with multiway tries; next we consider ternary search tries. Finally, we consider character-based operations, including prefix match and longest prefix, and related applications.

Substring Search

In this lecture we consider algorithms for searching for a substring in a piece of text. We begin with a brute-force algorithm, whose running time is quadratic in the worst case. Next, we consider the ingenious Knuth−Morris−Pratt algorithm whose running time is guaranteed to be linear in the worst case. Then, we introduce the Boyer−Moore algorithm, whose running time is sublinear on typical inputs. Finally, we consider the Rabin−Karp fingerprint algorithm, which uses hashing in a clever way to solve the substring search and related problems.

Regular Expressions

A regular expression is a method for specifying a set of strings. Our topic for this lecture is the famous grep algorithm that determines whether a given text contains any substring from the set. We examine an efficient implementation that makes use of our digraph reachability implementation from Week 1.

Data Compression

We study and implement several classic data compression schemes, including run-length coding, Huffman compression, and LZW compression. We develop efficient implementations from first principles using a Java library for manipulating binary data that we developed for this purpose, based on priority queue and symbol table implementations from earlier lectures.

Reductions

Our lectures this week are centered on the idea of problem-solving models like maxflow and shortest path, where a new problem can be formulated as an instance of one of those problems, and then solved with a classic and efficient algorithm. To complete the course, we describe the classic unsolved problem from theoretical computer science that is centered on the concept of algorithm efficiency and guides us in the search for efficient solutions to difficult problems.

Linear Programming (optional)

The quintessential problem-solving model is known as linear programming, and the simplex method for solving it is one of the most widely used algorithms. In this lecture, we given an overview of this central topic in operations research and describe its relationship to algorithms that we have considered.

Intractability

Is there a universal problem-solving model to which all problems that we would like to solve reduce and for which we know an efficient algorithm? You may be surprised to learn that we do no know the answer to this question. In this lecture we introduce the complexity classes P, NP, and NP-complete, pose the famous P = NP question, and consider implications in the context of algorithms that we have treated in this course.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Taught by Robert Sedgewick and Kevin Wayne, who have written an acclaimed textbook on algorithms

Covers topics in graph theory and string processing, making it relevant for programmers in various fields, including computer science, data science, and software engineering

Develops problem-solving skills and deepens understanding of algorithms and data structures, which are fundamental concepts in computer science

Covers topics that are frequently used in industry, such as graph algorithms, string processing, and data compression

Uses Java implementation and examples throughout the course, making it accessible to learners with a background in Java programming

Requires students to have a basic understanding of data structures, algorithms, and Java programming

Reviews summary

Advanced algorithms and complexity

learners say this course is largely positive, covering advanced algorithms, data compression, and graph theory. The challenging but rewarding programming assignments use topics from the first course in the series and receive detailed feedback from an autograder. One learner said, "This covers the most algorithm in the interview."

Lectures are well-structured and clear.

"Clear lectures. Interesting exercises."

"Fantastic Course, especially the well-designed high quality homework"

"Great quality of academic content. Mr Sedgewick is a great lecturer"

Assignments use algorithms in real-world applications.

"This course focuses on both theory and application."

"projects were chosen to be excellent building blocks for real applications."

"This was a great overview of more advanced algorithms, and I also got to prep for interviews and use concepts in actual work."

Interview questions help students prepare for technical interviews.

"This course provided we with detailed and vivid teaching class , challenging interview questions and practical hands-on labs"

"This class (and part 1) are the best courses I've ever done online."

"I've completed both Algorithms I and II, combined with reading the book "Algorithms" 4th Edition."

Assignments are well-prepared and help students understand concepts.

"Excellent exercises with grader - lecture material is clear and on point."

"Programming assignments in this course is very informative."

"The programming assignments in this course surprised me as being closely related to the applications"

Professor Sedgewick is an excellent lecturer and conveys his passion for algorithms.

"Very informative and well structured course. Assignments are interesting"

"Very good course, where you'll learn a lot."

"What an amazing journey. I am lucky to have such amazing teachers and wonderful content."

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Algorithms, Part II with these activities:

Create a comprehensive study guide

Show steps

Enhance your learning by organizing and summarizing course materials into a concise and accessible study guide.

Browse courses on Study Guide

Show steps

Gather all relevant course materials
Extract key concepts, algorithms, and examples
Organize and structure the information in a logical flow

Organize weekly study groups

Show steps

Foster collaboration and enhance your understanding by discussing course concepts with peers.

Show steps

Connect with classmates and form a study group
Schedule regular meetings
Review course material, discuss problems, and share insights

Read textbook Algorithms, Fourth Edition

Show steps

Strengthen your foundation in algorithms and data structures, deepening your understanding of concepts covered in the course.

View Algorithms on Amazon

Show steps

Read textbook chapters 1-7
Complete corresponding practice exercises
Attend office hours or discussion forums to clarify concepts

Five other activities

Expand to see all activities and additional details

Show all eight activities

Follow online tutorials on advanced graph algorithms

Show steps

Expand your knowledge by exploring specialized graph algorithms beyond the scope of the course.

Browse courses on Graph Algorithms

Show steps

Identify relevant graph algorithm tutorials
Follow the tutorials and implement the algorithms
Experiment with different graph inputs and analyze outputs

Solve coding challenges on LeetCode

Show steps

Improve your problem-solving skills and reinforce your understanding of algorithms and data structures through practical application.

Browse courses on Data Structures

Show steps

Choose problems from LeetCode related to course topics
Implement solutions in Java
Review solutions and optimize code

Write blog posts summarizing course concepts

Show steps

Enhance your understanding by explaining concepts in your own words, solidifying your grasp of key ideas and improving your communication skills.

Browse courses on Algorithms

Show steps

Identify a specific concept or algorithm
Research and gather information
Write a clear and concise blog post
Share your blog post and engage with readers

Build a data visualization tool

Show steps

Demonstrate your skills by creating a tool that visually represents relationships and patterns in data, enhancing your understanding of data structures.

Browse courses on Data Visualization

Show steps

Define the project scope and goals
Research and choose appropriate data visualization techniques
Design and implement the tool using Java
Test and refine the tool

Contribute to open-source projects related to algorithms

Show steps

Gain practical experience and contribute to the community by participating in open-source projects that utilize algorithms.

Browse courses on Open Source

Show steps

Identify open-source projects related to algorithms
Review project documentation and contribute to discussions
Implement or improve features related to algorithms

Career center

Learners who complete Algorithms, Part II will develop knowledge and skills that may be useful to these careers:

Algorithm Engineer

Algorithm Engineers design and develop algorithms to solve complex problems in various domains such as computer science, finance, and healthcare. Familiarity with efficient algorithms and data structures is essential for Algorithm Engineers, as it enables them to develop high-performance algorithms for real-world applications. This course provides a strong theoretical foundation in algorithm design and analysis, as well as practical experience in implementing efficient algorithms in Java.

See salaries and explore the career path for Algorithm Engineer

Computational Biology Researcher

Computational Biology Researchers create and improve algorithms and software tools to analyze biological data. Usually, this data has a large volume, and to manage such data, familiarity with efficient algorithms such as minimum spanning trees, graph traversal algorithms, and dynamic programming algorithms taught in the course is crucial. Also, the course's introduction to concepts such as data structures, graph theory, and string processing can help researchers gain a deep understanding of how to develop and analyze efficient algorithms for biological data analysis.

See salaries and explore the career path for Computational Biology Researcher

Data Scientist

Data Scientists collect, manage, and analyze large datasets to extract meaningful insights and help organizations make data-driven decisions. Knowledge of efficient algorithms and data structures covered in this course is highly valuable for Data Scientists. The course also emphasizes performance analysis of Java implementations, a skill that is in high demand for data science roles.

See salaries and explore the career path for Data Scientist

Software Engineer

Software Engineers design, develop, and maintain software systems. Familiarity with efficient algorithms and data structures is a core requirement for Software Engineers, as it enables them to develop efficient and scalable software solutions. The course's coverage of graph algorithms, string processing algorithms, and optimization algorithms provides a strong foundation for Software Engineers to tackle complex software development challenges.

See salaries and explore the career path for Software Engineer

Machine Learning Engineer

Machine Learning Engineers design, develop, and deploy machine learning models to solve real-world problems. Familiarity with efficient algorithms and data structures is crucial for Machine Learning Engineers, as it enables them to develop efficient and scalable machine learning models. This course provides a strong foundation in algorithm design, implementation, and performance analysis, which can enhance a Machine Learning Engineer's ability to build and deploy high-performance machine learning solutions.

See salaries and explore the career path for Machine Learning Engineer

Research Scientist

Research Scientists conduct research in various scientific disciplines, including computer science, biology, and physics. Familiarity with efficient algorithms and data structures is beneficial for Research Scientists, as it enables them to develop and analyze complex algorithms for scientific research. This course provides a strong foundation in algorithm design, implementation, and performance analysis, which can enhance a Research Scientist's ability to conduct groundbreaking research.

See salaries and explore the career path for Research Scientist

Quantitative Analyst

Quantitative Analysts use mathematical and statistical models to analyze financial data and make investment decisions. Familiarity with efficient algorithms and data structures is crucial for Quantitative Analysts, as it enables them to develop and analyze complex financial models efficiently. The course's coverage of graph algorithms, optimization algorithms, and string processing algorithms provides a solid foundation for Quantitative Analysts to succeed in their roles.

See salaries and explore the career path for Quantitative Analyst

Front-End Developer

Front-End Developers are responsible for the user interface and user experience of websites and applications. Familiarity with efficient algorithms and data structures is crucial for optimizing the performance and responsiveness of web applications. This course, with its focus on Java implementations, can help Front-End Developers build a solid foundation in algorithm design and implementation, leading to more efficient and user-friendly web applications.

See salaries and explore the career path for Front-End Developer

Database Administrator

Database Administrators design, implement, and maintain database systems to store and manage data. Familiarity with efficient algorithms and data structures is beneficial for Database Administrators, as it enables them to optimize database performance and ensure data integrity. This course provides a solid foundation in algorithms, data structures, and performance analysis, which can enhance a Database Administrator's ability to manage complex database systems.

See salaries and explore the career path for Database Administrator

Consultant

Consultants provide expert advice and solutions to businesses and organizations. Familiarity with efficient algorithms and data structures is valuable for Consultants, as it enables them to analyze complex business problems and develop data-driven solutions. This course provides a strong foundation in algorithm design, implementation, and performance analysis, which can enhance a Consultant's ability to deliver effective solutions to clients.

See salaries and explore the career path for Consultant

Systems Administrator

Systems Administrators manage and maintain computer systems and networks. Familiarity with efficient algorithms and data structures is beneficial for Systems Administrators, as it enables them to optimize system performance and troubleshoot complex issues. This course provides a foundation in algorithms, data structures, and performance analysis, which can enhance a Systems Administrator's ability to manage and maintain robust and efficient systems.

See salaries and explore the career path for Systems Administrator

Business Analyst

Business Analysts identify and analyze business needs and develop solutions to improve organizational performance. Familiarity with efficient algorithms and data structures can be beneficial for Business Analysts, as it enables them to understand and analyze complex business processes and develop data-driven recommendations. The course provides a foundation in algorithms, data structures, and performance analysis, which can enhance a Business Analyst's ability to contribute to data-driven decision-making within organizations.

See salaries and explore the career path for Business Analyst

Technical Writer

Technical Writers create and maintain technical documentation, such as user manuals and technical reports. Familiarity with efficient algorithms and data structures can benefit Technical Writers, as it enables them to understand and explain complex technical concepts in a clear and concise manner. This course provides a foundation in algorithms, data structures, and performance analysis, which can enhance a Technical Writer's ability to communicate technical information effectively.

See salaries and explore the career path for Technical Writer

Product Manager

Product Managers define and manage the development and launch of products. Familiarity with efficient algorithms and data structures can be beneficial for Product Managers, as it enables them to understand the technical aspects of product development and make informed decisions about product design. This course provides a foundation in algorithms, data structures, and performance analysis, which can enhance a Product Manager's ability to lead successful product development initiatives.

See salaries and explore the career path for Product Manager

User Experience Designer

User Experience Designers create and evaluate user interfaces for websites and applications. Familiarity with efficient algorithms and data structures can be beneficial for User Experience Designers, as it enables them to understand the performance implications of different design choices. This course provides a foundation in algorithms, data structures, and performance analysis, which can enhance a User Experience Designer's ability to create user-friendly and efficient interfaces.

See salaries and explore the career path for User Experience Designer