Solved Assignments of Coursera's DSA Specialization

This repository contains the solved assignments of Data Structures and Algorithms Specialization. Each solution is written in C++14.

Each of the file is tested to compile successfully on g++ 7.4.0 with the flags as mentioned in the following command:

g++ -pipe -O2 -std=c++14 <filename> -lm

Disclaimer: If you are enrolled in any of the courses of this specialization, please strictly follow the Coursera Honor Code. The sole motive of publishing this repository publicly was to provide you with some reference. Please view the code only when you are really struck at a problem, and that too after performing stress testing.

Note: While doing these courses I was focussing much on my competitive coding skills rather than the developmental ones. Consequently, I have used many tricks, macro definitions and C++ features (and that too without great formatting and comments) which may confuse a newbie. I don't recommend using all of these tricks everywhere, they are included here because it is a good learning experience. You can go and research about each trick. And in the end you can also design a template for yourself if you want to continue with C++14/C++17 while giving competitions. The code present here is not much ideal. In some places, instead of designing and implementing an algorithm myself I have used standard STL functions and also have took implementations of certain functions directly from the Boost library. I have tried my best to give minimal code along with best possible (time and space) complexity. At many places code can be made more space efficient by using lower level data structures instead of C++ containers. Anyone who wants to enhance the codes in any terms is most welcomed!

Course 1. Algorithmic Toolbox

Week 1. Programming Challenges

• Sum of Two Digits
• Maximum Pairwise Product

Week 2. 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

Week 3. Greedy Algorithms

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

Week 4. Divide-and-Conquer

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

Week 5. Dynamic Programming 1

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

Week 6. Dynamic Programming 2

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