Algorithmic Toolbox - Coursera

This repository contains my solutions to Algorithmic Toolbox course (UC San Diego - Coursera) assignments.

About

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

Syllabus

• Week 1: Programming Challenges
  • Sum of 2 digits
  • Maximum pairwise product
  • Stress test implementation
• Week 2: Algorithmic Warm-up
  • Why study algorithms?
  • Fibonacci number
  • Greatest common divisor
  • Big-O notation
• Week 3: Greedy Algorithms
  • Introduction
  • Grouping children
  • Fractional Knapsack
• Week 4: Divide & Conquer
  • Introduction
  • Polynomial multiplication
  • Master Theorem
  • Sorting problem
  • Quick sort
• Week 5: Dynamic Programming 1
  • Change problem
  • String comparison
• Week 6: Dynamic Programming 2
  • Knapsack
  • Placing parethenses

Status

• Week 1 ✔️
• Week 2 ✔️
• Week 3 ✔️
• Week 4 ✔️
• Week 5 ✔️
• Week 6 ✔️

Week 1 Results

• Maximum Pairwise Product (C)

Good job! (Max time used: 0.01/1.00, max memory used: 25698304/2147483648.)

Week 2 Results

• Fibonnacci Number (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11235328/2147483648.)

• Last Digit of Fibonacci Number (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11288576/2147483648.)

• Greatest Common Divisor (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11243520/2147483648.)

• Least Common Multiple (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11268096/2147483648.)

• Fibonacci Number Again (C)

Good job! (Max time used: 0.01/1.00, max memory used: 11513856/2147483648.)

• Last Digit of Sum of Fibonacci Numbers (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11206656/2147483648.)

• Last Digit of Sum of Fibonacci Numbers Again (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11231232/2147483648.)

• Last Digit of the Sum of Squares of Fibonacci Numbers (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11235328/2147483648.)

Week 3 Results

• Money Change (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11231232/2147483648.)

• Maximum Value of the Loot (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11407360/2684354560.)

• Car Fueling (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11292672/2147483648.)

• Maximum Advertisement Revenue (C)

Good job! (Max time used: 0.00/1.00, max memory used: 11718656/2147483648.)

• Collecting Signatures (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 11558912/2147483648.)

• Maximum Number of Prizes (C)

Good job! (Max time used: 0.00/1.00, max memory used: 12582912/2147483648.)

• Maximum Salary (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 11239424/2147483648.)

Week 4 Results

• Binary Search (C++)

Good job! (Max time used: 0.05/1.00, max memory used: 43175936/536870912.)

• Majority Element (C++)

Good job! (Max time used: 0.03/1.00, max memory used: 24256512/2147483648.)

• Improving Quick Sort (C++)

Good job! (Max time used: 0.02/1.00, max memory used: 23142400/2147483648.)

• Number of Inversions (C++)

Good job! (Max time used: 0.01/1.00, max memory used: 14692352/2147483648.)

• Organizing a Lottery:
• Closest Points:

Week 5 Results

• Money Change Again (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 11341824/2147483648.)

• Primitive Calulator (C++)

Good job! (Max time used: 0.00/1.50, max memory used: 11231232/2147483648.)

• Edit Distance (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 11268096/2147483648.)

• Longest Common Subsequence of Two Sequence (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 11485184/2147483648.)

• Longest Common Subsequence of Three Sequence (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 19664896/2147483648.)

Week 6 Results

• Maximum Amount of Gold (C++)

Good job! (Max time used: 0.01/2.00, max memory used: 14782464/2147483648.)

• Partitioning Souvenirs (C++)

Good job! (Max time used: 0.03/2.00, max memory used: 13537280/2147483648.)

• Maximum Value of Arithmetic Expression (C++)

Good job! (Max time used: 0.00/1.00, max memory used: 11259904/2147483648.)

Compiler Flags

Language	Flag
C	gcc -pipe -02 -std=c11 <filename.c> -lm
C++	g++ -pipe -02 -std=c++14 <filename.cpp> -lm