Data Structure and Algorithm Specializtion Course 1

This repository contains all solutions for the course Algorithmic-Toolbox offered on Coursera. The assignment solutions are in Python3.

About This Specialization

The Specialization covers algorithmic techniques for solving problems arising in computer science applications. It is a mix of theory and practice: you will not only design algorithms and estimate their complexity, but you will get a deeper understanding of algorithms by implementing them in the programming language of your choice (C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby, and Scala).

This Specialization is unique, because it offers two real-world projects. Advanced Shortest Paths project is offered in the end of the Algorithms on Graphs course. In this project, you'll deal with road network analysis and social network analysis. You'll learn how to compute the fastest route between New York and Mountain View thousands of times faster than classic algorithms and close to those used in Google Maps. Through Genome Assembly culminating project at the end of the Specialization, you'll learn how to assemble genomes from millions of short pieces and how algorithms fuel recent developments in personalized medicine.

Algorithmic-Toolbox

Assignments for Algorithmic Toolbox on Coursera

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

Reference Book: [Learning Algorithms Through Programming and Puzzle Solving by Alexander S. Kulikov, Pavel Pevzner]

Week 1- Programming Challenges (PDF)

• Sum of Two Digits
• Maximum Pairwise Product

Week 2- Algorithmic Warm-up (PDF)

• 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 (PDF)

• Money Change
• Maximum Value of the Loot (Fractional Knapsack)
• Car Fueling
• Maximum Advertisement Revenue (Maximum Dot Product)
• Collecting Signatures (Covering Segments by Points)
• Maximum Number of Prizes (Different Summands)
• Maximum Salary (Largest Number)

Week 4- Divide and Conquer (PDF)

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

Week 5- Dynamic Programming 1 (PDF)

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

Week 6- Dynamic Programming 2 (PDF)

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

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 (adding docstrings)
• Better algorithms that reduce time complexity