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

UVa Online Judge - 11110 - Equidivisions

Problem Statement:        11110 - Equidivisions

Solutions:

I solve this problem with help of DFS.
At first I stored the problem data in a 2-Dimension array, that represents N*N table. In this table I showed each partition with a number from 0 to N-1.
I used an array with the name "mark" that marks each partition when it checked and for mark each cell of table, I used -1 for that cell.
Then I started to move on the table cells.
If a cell isn't equal to -1 it means it didn't check yet. So It can be a partition that didn't check. But if we marked that partition in the mark array before, means that we checked that partition and the answer for this problem is "wrong". Else, we should search the neighbors of this cell to finding another cells of this partition and mark them with -1 to don't check them again, and finally mark this partition as visited partition in the mark array.
Eventually, if we couldn't find "wrong", it means that the answer is "good".
Here is my ACCEPTED code for this problem:

11110 - Equidivisions.cpp

2003 TCCC Semifinals 3 - Division I, Level One - ZigZag

Problem Statement:        ZigZag

Solutions:

I solve this problem with help of One-Dimension DP.

I used two one-dimension array with name dp and dif.
dp[i] stores the length of longest zigzag sub sequence that ended to element i of our input sequence.
dif[i] stores the difference between 2 last element for that longest zigzag sub sequence that ended to element i and set dif[i] for each i to 0.

Each element of input sequence can be a zigzag sequence lonely. So the initial state of my solution is to set each element of dp to 1, that means the minimum length for zigzag sub sequences that ended to each element is 1, included only that element.
But how to get the result for dp[i] and dif[i]?

Element i could come as the last element for the longest sequences that ended to element 0,1,..., i-1. So we should check:

1) If the element i could continue the zigzag sequence that ended to element 0,1,...,i-1?
2) If this new zigzag sub sequence is longer than before?

Then we can update dp[i] and dif[i].
After that we should find the biggest number in dp as the answer for this problem.

Here's my code for this problem:

ZigZag_DP.cpp

2004 TCCC Online Round 1 - Division I, Level Two - FlowerGarden

Problem Statement:        FlowerGarden

Useful Links:        TopCoder Forum

Solutions:

For this problem I have 2 solutions:

1) I look at this problem as a Graph:

Each type of flowers is a node.

If there is an edge between node u and v (u ---> v), means that flower v could block flower u. It's obvious that height[v] is greater than height[u].

So in this problem we have a DAG. For solve this problem I think about 2 way:

1- Topological Sort

2- Use in-degree for each node

Topological Sort can solve this problem and produce an answer for it but it may not be the answer that problem wants. Just because of this:

"...and you also want to have the tallest flowers as far forward as possible.

It means that if for example both 1,2,3 and 2,1,3 be the answers for the problem, then we should choose 2,1,3.

Therefore I used the second way to solve. In each step, in the DAG, I search for a suitable node with ZERO in-degree to remove from DAG and add it to the answer. Then mark that node as visited and try to update the other nodes' in-degree. Here's my code for this solution:

FlowerGarden_Graph.cpp

2) I tried to use DP to solve this problem:

We have n row for flowers, so for each row try to find the most suitable flower for the row!

I had tow idea for it:

1- Bottom-Up:

        I've tried to set the row from the back row to the front one. "The Most Suitable Flower" means "The flower with the minimum height possible that the flowers from the later rows couldn't block it". "The flowers from later rows" means that "Flowers that don't used for any row".

2- Top-Down:

        I've tried to set the row from the front row to back one. "The Most Suitable Flower" means "The Flower with the maximum height suitable that doesn't block any flower from the previous rows". "The flowers from the previous rows" means that "Flowers that don't used for any row".

So, when use a flower for a row, we should mark it as used to don't check again for blocking!

I've coded both of them but the first one failed for this test case:

height = {355, 141, 84, 432}

bloom = {251, 324, 87, 18}

wilt = {293, 344, 234, 200}

Here are my codes for both of them:

FlowerGarden_DP_Bottom-Up.cpp

FlowerGarden_DP_Top-Down.cpp