Brief Information

• Name : Algorithm
• Lecturer : Kim Yonghyuk
• Semester : 2014 Fall
• Course : BE. Computer Science and Engineering

Trace lectures

Listing themes I learned in the lecture in time order.

• Evaluation of algorithms: Big O, Small o, Omega $latex Omega$ notation
• Computation of Complexity
• Algorithm design techniques
  1. Divide and Conquer
     1. “Divide recursively?an instance of a problem into small instances as small as to readily solve them, and then combine small instances to the top instance.”
     2. ?Examples
        1. Binary search
        2. Merge sort
        3. Quick sort
     3. Solving recurrence relations
     4. Determining thresholds
     5. When not to use divide and conquer
  2. Dynamic Programming
     1. “Establish a recursive property and then solve an instance of the problem by solving smaller instances first.”
     2. ?Examples
        1. Calculating a binomial coefficient
        2. Floyd’s algorithm for the shortest paths problem
        3. Constructing an?optimal binary search tree
        4. Finding the shortest route for Traveling Salesperson Problem
  3. Greedy Approach
     1. “Arriving at a solution by making a sequence of choices, each of which simply looks the best at the moment.”
     2. ?Examples
        1. Giving change for a purchase
        2. Prim’s algorithm for constructing a minimum spanning tree
        3. Kruskal’s algorithm for constructing a minimum spanning tree
        4. Constructing a Huffman code
        5. The 0-1 knapsack problem
  4. Backtracking
     1. “Backtracking is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion. After each choice has been made and added to a partial solution, it can be retracted from the solution set later by backtracking”
     2. State space tree
     3. Examples
        1. N queens problem
        2. M coloring problem
        3. The 0-1 knapsack problem
  5. Branch and Bound
     1. “Compute a number (bound) at a node to determine whether the node is promising, and then if the bound is no better than the value of the best solution found so far, the node is non-promising“.
     2. State space tree
     3. Examples
        1. The 0-1 knapsack problem
        2. Traveling Salesperson Problem
• Computational Complexity Analysis
  • “What about the lower bound on the efficiency of all algorithms?for a given problem?”
  • Problem: Sorting – an example
    • Insertion sort
    • Selection sort
    • Heap sort
  • Decision trees
• Intractability: Theory of NP

Summarize?themes

• Evaluation of algorithms
  • Big-O, Omega, small-o notations
  • Time complexity: input size and basic operation
• Methods to design algorithms
  1. Divide and conquer
  2. Dynamic programming
  3. Greedy approach
  4. Backtracking
  5. Branch and bound
• Specific algorithms
  • Sequence search
  • Binary search
  • Fibonacci algorithms: recursive or iterative
  • Calculating a binomial coefficient
  • Floyd’s algorithm for the shortest paths problem
  • Constructing an?optimal binary search tree
  • Finding the shortest route for Traveling Salesperson Problem
  • Giving change for a purchase
  • Prim’s algorithm for constructing a minimum spanning tree
  • Kruskal’s algorithm for constructing a minimum spanning tree
  • Constructing a Huffman code
  • The 0-1 knapsack problem
  • N queens problem
  • M coloring problem
  • Insertion sort
  • Selection sort
  • Heap sort
• Program = Data structures + Algorithms
• Problems and Algorithms
• Types of cases of algorithms
  • Every case algorithms
  • Non every case algorithms
    • The Worst/Best/Average case of algorithms
• Two parameters for evaluating time complexity of an algorithm
  1. input size
  2. basic operation

Glossary

• Dynamic programming
• Greedy?algorithm
  • ?an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum