Data Structures and Algorithms

This repository will contain my work from the Master Algorithmic Programming Techniques Specialization that was created by UC San Diego and delivered through Coursera. I will be implementing solutions in Python3, Java, and C++.

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 with time and memory results from grader

Week 1

Solving a Simple Code Problem

Problem: Maximum Pairwise Product

• Python: Max time used: 0.14/5.00, max memory used: 26456064/536870912
• Java: Max time used: 0.07/1.00, max memory used: 21037056/536870912
• C++: Max time used: 0.12/1.00, max memory used: 21045248/536870912

Week 2

Prgramming Assignment: Introduction

Problem: Small Fibonacci Number

• Python: Max time used: 0.02/5.00, max memory used: 8740864/536870912
• Java: Max time used: 0.21/1.50, max memory used: 24145920/536870912
• C++: Max time used: 0.00/1.00, max memory used: 8744960/536870912

Problem: The Last Digit of a Large Fibonacci Number

• Python: Max time used: 0.17/5.00, max memory used: 8699904/536870912
• Java: Max time used: 0.19/1.50, max memory used: 28651520/536870912
• C++: Max time used: 0.00/1.00, max memory used: 8699904/536870912

Problem: Greatest Common Divisor

• Python: Max time used: 0.05/5.00, max memory used: 9568256/536870912
• Java: Max time used: 0.21/1.50, max memory used: 24121344/536870912
• C++: Max time used: 0.00/1.00, max memory used: 9560064/536870912

Problem: Least Common Multiple

• Python: Max time used: 0.09/5.00, max memory used: 9601024/536870912
• Java: Max time used: 0.17/1.50, max memory used: 24133632/536870912
• C++: Max time used: 0.00/1.00, max memory used: 9580544/536870912

Advanced Problem: Huge Fibonacci Number modulo m

• Python: Max time used: 0.21/5.00, max memory used: 30359552/536870912
• Java: Max time used: 0.17/1.50, max memory used: 30363648/536870912
• C++: Max time used: 0.00/1.00, max memory used: 30363648/536870912

Advanced Problem: Last Digit of a Sum of Fibonacci Numbers

• Python: Max time used: 0.06/5.00, max memory used: 9564160/536870912
• Java: Max time used: 0.21/1.50, max memory used: 24285184/536870912
• C++: Max time used: 0.00/1.00, max memory used: 8720384/536870912

Advanced Problem: Last Digit of a Partial Sum of Fibonacci Numbers

• Python: Max time used: 0.05/5.00, max memory used: 8720384/536870912

Week 3

Programming Assignment: Greedy Algorithms

Problem: Changing Money

• Python: Max time used: 0.05/5.00, max memory used: 8716288/536870912
• Java: Max time used: 0.17/1.50, max memory used: 24166400/536870912
• C++: Max time used: 0.00/1.00, max memory used: 8716288/536870912

Problem: Fractional Knapsack

• Python: Max time used: 0.05/5.00, max memory used: 8761344/671088640
• Java: Max time used: 0.36/1.50, max memory used: 33243136/671088640
• C++: Max time used: 0.00/1.00, max memory used: 8769536/671088640

Problem: Minimum Dot Product

• Python: Max time used: 0.02/5.00, max memory used: 8945664/536870912
• Java: Max time used: 0.31/1.50, max memory used: 32632832/536870912
• C++: Max time used: 0.00/1.00, max memory used: 8957952/536870912

Problem: Covering Segments by Points

• Python: Max time used: 0.03/5.00, max memory used: 9023488/536870912
• Java: Max time used: 0.20/1.50, max memory used: 24457216/536870912
• C++: Max time used: 0.00/1.00, max memory used: 9019392/536870912

Problem: Pairwise Distinct Summands

• Python: Max time used: 0.07/5.00, max memory used: 9617408/536870912
• Java: Max time used: 0.69/1.50, max memory used: 47325184/536870912
• C++: Max time used: 0.00/1.00, max memory used: 9613312/536870912

Week 4

Programming Assignment: Divide and Conquer

Problem: Binary Search

• Python: Max time used: 0.82/10.00, max memory used: 37974016/536870912
• Java: Max time used: 1.13/3.00, max memory used: 74174464/536870912
• C++: Max time used: 0.10/2.00, max memory used: 37974016/536870912

Problem: Majority Element

• Python: Max time used: 0.66/5.00, max memory used: 21393408/536870912
• Java: Max time used: 0.36/1.50, max memory used: 42090496/536870912
• C++: Max time used: 0.05/1.00, max memory used: 21393408/536870912

Problem: 3-Way Partition

• Python: Max time used: 1.02/11.00, max memory used: 28880896/536870912
• Java: Max time used: 1.16/5.50, max memory used: 70074368/536870912
• C++: Max time used: 0.08/2.20, max memory used: 29736960/536870912

Advanced Problem: Number of Inversions

• Python: Max time used: 0.77/15.00, max memory used: 21364736/536870912
• Java: Max time used: 0.87/4.50, max memory used: 112693248/536870912
• C++: Max time used: 0.05/3.00, max memory used: 21360640/536870912

Advanced Problem: Points and Segments

• Python: Max time used: 0.41/20.00, max memory used: 44896256/536870912

Week 5

Programming Assignment: Dynamic Programming

Problem: Primitive Calculator

• Python: Max time used: 1.08/7.50, max memory used: 13688832/536870912
• Java: Max time used: 0.19/2.25, max memory used: 32600064/536870912
• C++: Max time used: 0.01/1.50, max memory used: 9396224/536870912

Problem: Take as Much Gold as Possible

• Python: Max time used: 0.61/10.00, max memory used: 20611072/536870912
• Java:
• C++:

Problem: Compute the Edit Distance Between Two Strings

• Python:
• Java:
• C++:

Problem: Maximize the Value of an Arithmetic Expression

• Python:
• Java:
• C++:

Advanced Problem: Longest Common Subsequence of Three Sequences

• Python:
• Java:
• C++: