Algorithms Course Notes - Part II

Algorithms Course Notes from Coursera

Binary Search Trees

• Binary Tree in Symmetric order (Nodes - Contain info, two links)
• Each node has left and right tree, both can be null
• Every Node Key Larger than keys in left sub tree
• Every Node key smaller than keys in right sub tree
• Inserts - Find a null link by search eligible position and insert it there

B Trees

• General Model for external storage
• Internal node key guide search
• External node has client key
• Insert at Bottom null node
• If Nodes are full it will split to allow insert
• Variants of BTree is used in DBs (B+ Tree, B* Tree)

RBT - Red Black Tree Tracks every simple path from a node to a descendant node with same number of black nodes
Red Black Trees

• Internal Left Leaning links to glue 3 nodes
• No Nodes have two red links connected
• Every path from root to null link has same number of black links
• Use a flag color to denote red or black link in implementation

Heap Sort

• Largest of all keys is the root

Reposting Important Summary Slides

Happy Learning!!!

Algorithm Analysis - Basics

This post is based on notes after attending Algorithms I classes at Coursera. Lecture on Analysis of Algorithms is very good. Couple of interesting snapshots/ questions captured during the course posted below

This can be computed to 1000000 / log (1000000) = 100000/6 = 1,66,6666. This should be the right answer I believe.

Another interesting slide - Order of Growth

• Big-O is an upper bound.
• Big-Theta is a tight bound, i.e. upper and lower bound.Link

Another Interesting Question

 

Good Explanation of Answer - Dropping Eggs from a Building - 100 Story Building Famous Google Puzzle

 

 

Happy Learning!!! 

Alogorithm Problems

Alogorithm Problems
Question #1 - Given an array of N integers in which each element from 1 and N-1 occurs once and one occurs twice. Write an algorithm to find duplicate integer. Note- You may destroy the array.
Solution1:
Example Array is {1,2,4,7,8,9,4}
Use Negation to Identify the duplicate one. When you negate every element when you parse it would be like
{0,0,4,0,0,0}. Since 4 occurs more than once for the second time it would be 0-(-4). The resulting <> 0 number in the array is the duplicate occurence.
Note: Same logic can be used to count number of unique elements in an array.

Solution 2: Use XOR for solving this problem
Question#2 - Write a function to reverse a word in place O(n) time and O(1) space.
Solution:
void ReverseWord( char *t, int len)
{
  if(len<=1) return 1;
  Swap(&s[0],&s[len-1]);
  ReverseWord(s+1,len-2);
}

Question#3- Find Longest Sequence Palindrome in a String "abcabcad"
This is a Dynamic Programming problem.
Answer: Link1, Link2

Dynamic Programming
Good problems and answers
From the above link posting the solution
Let us define the maximum length palindrome for the substing x[i,...,j] as L(i,j)
Procedure compute-cost(L,x,i,j)

Input: Array L from procedure palindromic-subsequence; Sequence x[1,...,n] i and j are indices
Output: Cost of L[i,j]
if i = j:
    return L[i,j]
else if x[i] = x[j]:
    if i+1 < j-1:
        return L[i+1,j-1] + 2
    else:
         return 2
else:
return max(L[i+1,j],L[i,j-1])

Read Quote of Michal Danilák's answer to Dynamic Programming: Are there any good resources or tutorials for Dynamic Programming besides TopCoder tutorial? on Quora

More Reads
Are there any good resources or tutorials for Dynamic Programming besides TopCoder tutorial ?

What are few must-do DP problems and why?

Happy Learning!!!!

Trees – Revisited

• A Tree with N Nodes has N-1 Edges
• Nodes with No Children are called leaves
• Depth for Node N – Length of Unique path from Root to Node N. Root is of depth 0
• Height of the root is equal to height of the tree

• 
  
  For above tree Height is 3. E is at Depth 1
• Binary Tree – No node can have more than two children
• AVL Tree is identical to BST. Height of left and right subtree differ by 1
• Tree Traverals - Depth First Traversals of Binary Trees

 I need to catch up with good problem set I learnt from Algorithmica. 8 Queen Problem Analysis I will do it soon.

More Reads

Hash Tables notes

DFS Vs BFS

Depth First Search Vs Breadth First Search
DFS

• A depth-first search (DFS) explores a path all the way to a leaf before backtracking and exploring another path
• For example, after searching A, then B, then D, the search backtracks and tries another path from B
• Node are explored in the order A B D E H L M N I O P C F G J K Q
• N will be found before J  

DFS -

• Takes less memory
• The disadvantages are that it takes longer, and will not always find the shortest path
• Can get struck if Tree has loops

 BFS

• A breadth-first search (BFS) explores nodes nearest the root before exploring nodes further away
• For example, after searching A, then B, then C, the search proceeds with D, E, F, G
• Node are explored in the order A B C D E F G H I J K L M N O P Q
• J will be found before N 

BFS

• Will Always find shortest path
• Can Deal with Looping Structures
• Takes lot of memory

Algorithm - Pseudo Code
Depth-first searching:

Put the root node on a stack;
while (stack is not empty)
                       {
                              remove a node from the stack;
                              if (node is a goal node) return success;
                              put all children of node onto the stack;
                       }
return failure;

Breadth-first searching:

Put the root node on a queue;
while (queue is not empty)
                        {
                            remove a node from the queue;
                            if (node is a goal node) return success;
                            put all children of node onto the queue;
                        }
return failure;

Note: Queue (FIFO), Stack(LIFO) 
8 Queen problem using DFS Approach link
Reference - Study Material from Site

Algorithm Types

Many Algorithm types are to be considered:

Simple recursive algorithms
Example – Factorial Algorithm
unsigned int factorial(unsigned int n)
{
     if (n <= 1)
    {
        return 1;
    }
    else
   {
          return n * factorial(n-1);
   }
}

Backtracking algorithms
• Backtracking algorithms are based on a depth-first recursive search
• A backtracking algorithm:

• Tests to see if a solution has been found, and if so, returns it; otherwise
• For each choice that can be made at this point,
• Make that choice
• If the recursion returns a solution, return it
• If no choices remain, return failure
• Example – 8 Queen Problem

Divide and conquer algorithms
o Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem
o Combine the solutions to the subproblems into a solution to the original problem
o Example – QuickSort, BinarySearch

Dynamic programming algorithms
o Like divide and conquer, DP solves problems by combining solutions to subproblems.
o Unlike divide and conquer, subproblems are not independent.

• Subproblems may share subsubproblems,
• However, solution to one subproblem may not affect the solutions to other subproblems of the same problem.

o DP reduces computation by
o Solving subproblems in a bottom-up fashion.
o Storing solution to a subproblem the first time it is solved.
o Looking up the solution when subproblem is encountered again.
o At this moment two dynamic programming hallmarks are stated:

• Optimal substructure: an optimal solution to a problem contains optimal solutions to subproblems.
• Overlapping subproblems: a recursive solution contains a “small” number of distinct subproblems repeated many times.

o Examples -Dynamic Programming Practice Problems - Video Tutorial

Greedy algorithms
o A greedy algorithm works in phases. At each phase:
o You take the best you can get right now, without regard for future consequences
o You hope that by choosing a local optimum at each step, you will end up at a global optimum
o Examples
o Dijkstra’s algorithm for finding the shortest path in a graph - Always takes the shortest edge connecting a known node to an unknown node
o Kruskal’s algorithm for finding a minimum-cost spanning tree - Always tries the lowest-cost remaining edge
o Prim’s algorithm for finding a minimum-cost spanning tree - Always takes the lowest-cost edge between nodes in the spanning tree and nodes not yet in the spanning tree

• Branch and bound algorithms
• Brute force algorithms
• Randomized algorithms

Reference – I relied purely on web search to refer to multiple sites and learn above details. My next plan is to take up one example at a time and learn and analyze the algorithm.

Practicing Programming
You Should Write Blogs

More Reads

Programming Paradigms

View more presentations from Directi Group.

Algorithms - Time Complexity

Time Complexity of For Loops
=========================
1. Sum = 0;
    for(i=0; i>n; i++)
        Sum++;
  Complexity is O(N)  - Since the loop is executed only once

2. Sum = 0;
    for(i=0; i<n; i++)
         for(j=0; j<n; j++)
               Sum++;
 Complexity is O(N Square) - Two For loops

3. Sum = 0;
    for(i=0; i<n; i++)
        for(j=0; j<n*n; j++)
 Complexity is O(N3) - N Power3

'O' Notation

• O(g(n)) is a set of functions, f, such that
• f(n) < cg(n) - g is an upper bound of f
• f is O(g) is transitive. If f is O(g) and g is O(h) then f is O(h)
• Exponential functions grow faster
• Lograthmic functions grow slower

Omega notation

• set of functions such that f(n) > cg(n) - g is lower bound of f

Theta notation
theta(g) = O(g) and Omega (g). g is both lower and upper bound of f

Good Tutorial Link

Class P - Set of Problems which will have solutions with polynomial time complexity. E.g - Euler's Problem

Class NP - (Non Deterministic Polynomial) - Problem which can be solved by a series of guessing (non-deterministic) steps but whose solution can be verified as correct in polynomial time is said to lie in class NP. E.g Hamilitonian Problem

Sort Algorithms Time Complexity

• Insertion Sort - O(N Square)
• Bubble Sort - O(N Square)
• Heap Sort - O(NlogN)
• Quick Sort - O(NlogN)
• Radix Sort - O(N)

Algorithms - Maximum of sub sequence numbers

Question - Find max subsequence of 3 numbers in an array of 10 numbers

A little console app
==============
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
     static void Main(string[] args)
    {
          Console.WriteLine("Test Output");
          int[] a = { 21, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
          int maxsum=0,currentsum = 0;
          //max subsequence of 3 numbers
         for (int i = 0; i < 10; i++) //N times
        {
            currentsum = 0;
            for (int j = i; j < i+3 && j <10 ; j++) //3N
             {
                    currentsum = currentsum + a[j];
             }
             if (currentsum > maxsum)
             maxsum = currentsum;
        }
       Console.WriteLine("Max Sum Value is ", maxsum);
    }
}
}

It is O(N Square)

Next problem Set
Write a program which prints array of numbers 1 - 100 as multiples of 3 with A's i.e.(3A,6A,9A.....) , multiples of 5 with B(5B, 10B, 20B....) and multiples of 3 and 5 with AB(15AB, 150AB.....)

TSQL Code Here - SQL 2008 R2
use TEMPDB

DECLARE @I INT
DECLARE @RESULT VARCHAR(5)
SET @I = 1
SET @RESULT = NULL
WHILE 1 = 1
BEGIN
              SET @RESULT =
                                   CASE
                                   WHEN (@I%5 = 0 AND @I%3 = 0) THEN (CONVERT(VARCHAR(10),@I)+'AB')
                                    WHEN @I%3 = 0 THEN (CONVERT(VARCHAR(5),@I)+'A')
                                    WHEN @I%5 = 0 THEN (CONVERT(VARCHAR(5),@I)+'B')
                                    END
               IF @RESULT IS NOT NULL
                     SELECT @RESULT
               SET @I = @I+1
               SET @RESULT = NULL
               IF @I > 100
               BREAK;
END

Write a program to shuffle pack of cards without using math.random....

Given an array containing zeros,+ve and -ve numbers, write a function which pushes all the zeros to the end of the array.

Write a function which takes a string and a substring as input and which deletes the substring in the main string.eg: mainstr=abcxyghixy sub=xy result should be mainstr=abcghi

Testing atoi function

Prime number in TSQL from 1 to 100

The prime number challenge – great waste of time!

Many different solutions here in link