README.md

Coursera: Data Structures and Algorithms Specialization

Progress: 4/6 courses completed

This repository contains almost all the solutions for Data Structures and Algorithms Specialization. The language of choice is Python3, but I tend to switch to Ruby/Rust in the future. All program assignments can be found inside the course weeks directory.

Disclaimer: The below solutions is for reference only. Please design and implement your own algorithms to pass the courses.

Course 1. Algorithmic Toolbox

Week 1. Introduction

• Small Fibonacci Number
• The Last Digit of a Large Fibonacci Number
• Greatest Common Divisor
• Least Common Multiple
• Huge Fibonacci Number modulo m

Week 2. Greedy Algorithms

• Changing Money
• Fractional Knapsack
• Minimum Dot Product
• Covering Segments by Points
• Pairwise Distinct Summands

Week 3. Divide and Conquer

• Binary Search
• Majority Element
• Sorting: 3-Way Partition
• Number of Inversions
• Points and Segments

Week 4. Dynamic Programming

• Primitive Calculator
• Take as Much Gold as Possible
• Compute the Edit Distance Between Two Strings
• Maximize the Value of an Arithmetic Expression
• Longest Common Subsequence of Three Sequences

Course 2. Data Structures

Week 1. Basic Data Structures

• Check brackets in the code
• Compute tree height
• Network packet processing simulation

Week 2. Priority Queues and Disjoint Sets

• Convert array into heap
• Parallel processing
• Merging tables

Week 3. Hash Tables and Hash Functions

• Phone book
• Hashing with chains
• Find pattern in text

Week 4. Binary Search Trees

• Binary tree traversals
• Set with range sums
• Rope

Course 3. Algorithms on Graphs

Week 1. Decomposition of Graphs 1

• Finding an Exit from a Maze
• Adding Exits to a Maze

Week 2. Decomposition of Graphs 2

• Checking Consistency of CS Curriculum
• Determining an Order of Courses
• Checking Whether Any Intersection in a City is Reachable from Any Other

Week 3. Paths in Graphs 1

• Computing the Minimum Number of Flight Segments
• Checking whether a Graph is Bipartite

Week 4. Paths in Graphs 2

• Computing the Minimum Cost of a Flight
• Detecting Anomalies in Currency Exchange Rates
• Exchanging Money Optimally

Week 5. Minimum Spanning Trees

• Clustering
• Building Roads to Connect Cities

Week 6. Advanced Shortest Paths Project (Optional)

• Friend Suggestion
• Compute Distance Faster Using Coordinates
• Compute Distance with Preprocessing
• Compute Distance with Preprocessing on Larger Road Networks
• Travelling Salesman Problem

Course 4. Algorithms on Strings

Week 1. Suffix Trees

• Construct a Trie from a Collection of Patterns
• Implement TrieMatching
• Extend TrieMatching
• Construct the Suffix Tree of a String
• Find the Shortest Non-Shared Substring of Two Strings

Week 2. BWT and Suffix Arrays

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

Week 3-4. Algorithmic Challenges

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

Contributing

All contributions are welcome. Just make a PR. Below is a list of general improvements that need to be added that I would love help with:

• Improve documentation
• Clean up code (by fixing pep8 errors)
• Better algorithms that reduce time complexity (espescially for course #3 & #4)