Coursera | Data Structures and Algorithms Specialization

This repository contains Javascript solutions for Data Structures and Algorithms Specialization. All program assignments can be found inside the course weeks directory.

Algorithmic Toolbox

Programming Challenges

• Sum of Two Digits
• Maximum Pairwise Product

Algorithmic Warm-up

• Fibonacci Number
• Last Digit of a Large Fibonacci Number
• Greatest Common Divisor
• Least Common Multiple
• Fibonacci Number Again
• Last Digit of the Sum of Fibonacci Numbers
• Last Digit of the Sum of Fibonacci Numbers Again
• Last Digit of the Sum of Squares of Fibonacci Numbers

Greedy Algorithms

• Money Change
• Maximum Value of the Loot
• Car Fueling
• Maximum Advertisement Revenue
• Collecting Signatures
• Maximum Number of Prizes
• Maximum Salary

Divide and Conquer

• Binary Search
• Majority Element
• Improving Quick Sort
• Number of Inversions
• Organizing a Lottery
• Closest Points

Dynamic Programming 1

• Money Change Again
• Primitive Calculator
• Edit Distance
• Longest Common Subsequence of Two Sequences
• Longest Common Subsequence of Three Sequences

Dynamic Programming 2

• Maximum Amount of Gold
• Partitioning Souvenirs
• Maximum Value of an Arithmetic Expression

Data Structures

Basic Data Structures

• Check brackets in the code
• Tree height
• Network packet processing simulation
• Stack with maximum
• Maximum in Sliding Window

Priority Queues and Disjoint Sets

• Make Heap
• Parallel Processing
• Merging Tables

Hash Tables

• Phone Book
• Chaining Simulation
• Find Substring
• Substring Comparison
• Longest Common Substring
• Pattern Matching with Mismatches

Binary Search Trees

• Tree Orders
• Is it a Binary Search Tree?
• Is it a Binary Search Tree? Hard version.
• Set range sum
• Rope string

Algorithms on Graphs

Decomposition of Graphs 1

• Reachability
• Connected Components

Decomposition of Graphs 2

• Acyclicity
• Topological Sort
• Strongly connected components

Paths in Graphs 1

• Breadth first search (minimum number of flight segments)
• Bipartite

Paths in Graphs 2

• Dijkstra
• Negative Cycle
• Shortest Paths

Minimum Spanning Trees

• Connecting Points
• Clustering

Algorithms on String

Suffix Trees

• Construct a Trie from a Collection of Patterns
• Implement TrieMatching
• Extend TrieMatching
• Suffix Tree
• Shortest Non-Shared Substring

Burrows–Wheeler Transform and Suffix Arrays

• Burrows-Wheeler Transform
• Reconstruct String from its Burrows-Wheeler Transform
• Implement BetterBWMatching
• Construct Suffix Array of a String

Algorithmic Challenges

• Find all Occurrences of a Pattern in a String
• Construct Suffix Array of a Long String
• Pattern Matching with the Suffix Array
• Construct a Suffix Tree from a Suffix Array

Advanced Algorithms and Complexity

Flows in Networks

• Evacuating People
• Airline Crews
• Stock Charts

Linear Programming

• Infer Energy Values of Ingredients
• Optimal Diet Problem
• Online Advertisement Allocation

NP-completeness

• Assign Frequencies to the Cells of a GSM Network
• Cleaning the Apartment
• Advertisement Budget Allocation

Coping with NP-completeness

• Plan a Fun Party
• School Bus