Algorithmic Toolbox

4-6-17

Visualizations

  1. Algorithms: http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  2. Sorting: https://www.toptal.com/developers/sorting-algorithms/

Testing Techniques

  1. A few small manual tests.
  2. A test for each possible type of answer (smallest answer, biggest answer, answer doesn’t exist, etc.)
  3. Test for time/memory limit: generate a test with the largest possible size of input (“max test”), run your program, measure time and memory consumption.
  4. Tests for corner cases:
    1. Smallest possible “n”: the length of the input sequence or string, the number of queries, etc.
    2. Equal numbers, equal letters in the string, more generally, equal objects in the input. Any two objects that are not restricted to be different in the problem statement can be equal.
    3. Largest numbers in the input allowed by the problem statement – for example, to test for integer overflow.
    4. Degenerate cases like empty set, three points on one line, a tree which consists of just one chain of nodes.

Stress Testing

Implement two different solutions, one correct and fast, other a significantly different(perhaps even brute force) and compare the solutions obtained from both using random numbers for test cases. This significantly reduces failure and is guaranteed to give you edge test cases. Stress Testing is considered as last resort!

  1. It is very important to write programs that work correctly on all the allowed inputs.
  2. Testing is essential to writing correct programs.
  3. First test on a few small manual tests, then test for each type of answer, then test on large test cases for time limit and memory limit, then test on corner cases.
  4. After that, apply stress testing to ensure your program works – it will almost always lead to correct solution. You can do it before your first attempt to submit your solution – and will often get it right from the first attempt!
  5. Stress testing consists of implementing the intended solution, another simple possible slow solution, a test generator and an infinite loop which generates tests and compares answers of the two solutions.
  6. Always try to find the smallest test cases on which your solution fails.
  7. Try different regions of the test space when generating cases for stress testing.

Asymptotic Notation

Add images for the increasing run-times for different complexities as well as limits of n.

Screenshot from 2017-06-05 17-05-45Screenshot from 2017-06-05 17-06-07Screenshot from 2017-06-05 17-07-07

 

nth Fibonnaci number= Approximately (n/5) digits

Greedy Algorithms

Greedy strategy

  1. Make a greedy choice
  2. Prove that this choice is a safe move
  3. Break problems into sub-problems
  4. Iterate over each sub problem
  5. Estimate running time

General Example- Line, Points, covered by segments

Safe Move

A move is called a safe move if there is an optimal solution consistent with this first move.

Before solving any algorithm, try and covert it into a mathematical problem.

Divide and Conquer

  1. Break into non-overlapping subproblems of same kind
  2. Solve sub-problems
  3. Combine results

Solving using Recursion, we have:

  1. Create a recursive solution
  2. Define a corresponding recurrence relation using T(n)
  3. Determine worst case runtime T(n)
  4. Optionally, create iterative solution

Run time of binary search is Theta(N)

Normal polynomial multiplication= O(n^2)

Karatsuba polynomial multiplication= O(n^1.58)

For multiplying very large numbers using the Karatsuba algorithm, make x=10 and construct appropriate polynomial from the numbers.

Master Theorem

Screenshot from 2017-06-13 22-00-54.png

Sorting

  1. Maximum number of leaves in a tree of depth d ==> d>=log(2) L,  where L is the number of leaves
  2. log(n!) = Omega( n* log n)

Dynamic Programming

  1. String similarity using reward, penalty for mismatch and insertions
  2. Longest Common Subsequence
  3. Edit Distance problem
    1. Minimizing edit distance= Maximizing Alignment Score
  4. Knapsack Problem
    Screenshot from 2017-07-02 03-15-59.png

HOMEWORK LEFT

  1. Polynomial Multiplication- Naive and Karatsuba
  2. Solve UNIONSET- JUNE17 question using Bit Masking
  3. Develop Intro Sort–> Develop Heap Sort
  4. Watch Coding Blocks Seminar, revise Greedy vs DP
  5. Revise Divide and Conquer paradigm
  6. Implement Doubly Linked Lists
  7. Section 10.1 and 10.2 CLRS for Data Structures.
Advertisements