Ad hoc

0) Not fall into standard categories with well-studied solutions (Can't classify as other standard types).

1) Each one is different.

2) No specific or general techniques.

3) Fun, Each one present a new challenge!

4) Sometimes new data structures, unusual sets of loops/conditionals or rare special combinations. 

5) Careful reading!

6) Carefully sequencing the instructions given.

7) Reasonable optimization and a degree of analysis (E.g. avoid loops nested 5 deep).

8) More than other kinds!

Greedy Algorithm

Notes:

0) Making the locally optimum choice at each stage with the hope of finding the global optimum.

1) Greedy algorithms do not consistently find the globally optimal solution, because they usually do not operate exhaustively on all the data. e.g. graph coloring problem, NP-complete.

2) But it's useful because they are quick to think up and give good approximations to the optimum.

3) If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice. e.g. Kruskal and Prim for finding MST, optimum Huffman trees, Matroids theory.

4) They have 5 pillars:
    ♦ A candidate set, from which a solution is created
    ♦ A selection function, which chooses the best candidate to be added to the solution
    ♦ A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
    ♦ An objective function, which assigns a value to a solution, or a partial solution
    ♦ A solution function, which will indicate when we have discovered a complete solution

5) Basic Idea: "build large solutions up from smaller ones"

6) Keeps only the best solution, unlike other approaches!

7) Fast, Linear to quadratic, Little memory, Easy to code and debug, Run quickly, Defining a good Algorithm.

8) DON'T WORK FOR ALL PROBLEMS!!! (They usually aren't correct)

9) TWO basic problems:
    1- How to Build? How does one create larger solutions from smaller ones?
          THIS IS A FUNCTION OF THE PROBLEM.
    2- Does it work?
          DOESN'T ALWAYS WORK. (even if it works for sample input, random input and all the
          cases...there's a case - at least one case where it won't work!)

10)  Greedy algorithms can be proven by Reductio Argument.

11) Greedy doesn't work for Coin Change problems. THEY AREN'T GREEDY! (It just works one the U.S. coin system with coins 1, 5, 10, 25!)

12) Topological Sort can be solved with Greedy: 
      1- Create a DAG (Directed Acyclic Graph) 
      2- Find a node with in-degree of 0 
          (there's no topological sort for the DAG, if there isn't any node with in-degree of 0)
      3- Place it on the end of ordering 
      4- Delete all of its out-arcs
      5- Go to step 2

13) If a greedy solution exists, USE IT!

Sample Problems:

Barn Repair

 Sorting a three-valued sequence

Minimal Coverage

 All in All

Ferry Loading II 

Recursion

Notes:

0) Many algorithms need to be implemented recursively, like backtracking.

1) It's a function/procedure/method, calls itself again with a smaller range of arguments (break it into simpler problems) or with different arguments (useless if use recursion with the same arguments).

2) keeps calling itself until something so simple or simpler than before (base case), can be solved easily or until an exit condition occurs.

3) Recursion must stop. so, a valid base case or end-condition must be reached, else leads to stack overflow error.

4) When a method/function/procedure is called:

        – caller is suspended,
        – "state" of caller saved,
        – new space allocated for variables of new method.

5) Powerful and elegant technique, uses "solving a smaller problem of the same type" method to solve.

6) Examples: Factorial, Fibonacci, etc.

    Q: Recursive or Iterative?        A: Iterative

    Q: Why?                                 A:It's Faster and doesn't consume a lot of memory.

7) But some problems:

      - can only be solved in recursive, or

      - more efficient in recursive, or

      - iterative solutions are difficult to conceptualize.

   Examples: Tower of Hanoi, Searching (DFS, BFS), etc.

To be continued...

Complete Search

Notes:

0) Utilizing the fact that computer is actually very fast.

1) Exploits the brute force, straight-forward, try-them-all method of finding the answer.

2) Should almost always be the first algorithm/solution you consider.

3) If this works within time and space constraints, then do it.

4) Easy to code and usually easy to debug.

5) Many seemingly hard problems is eventually solvable using brute force.

Sample Problems:

Party Lamps

The Clocks