###### 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 notation
- Computation of Complexity
**Algorithm design techniques****Divide and Conquer**- “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.” - Examples
- Binary search
- Merge sort
- Quick sort

- Solving recurrence relations
- Determining thresholds
- When not to use divide and conquer

- “Divide recursively an instance of a problem into
**Dynamic Programming**- “Establish
**a recursive property**and then solve an instance of the problem by**solving smaller instances first**.” - Examples
- 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

- “Establish
**Greedy Approach**- “Arriving at a solution by making
**a sequence of choices**, each of which**simply looks the best at the moment**.” - Examples
- 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

- “Arriving at a solution by making
**Backtracking**- “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” **State space tree**- Examples
- N queens problem
- M coloring problem
- The 0-1 knapsack problem

- “Backtracking is used to solve problems in which a sequence of objects is chosen from a specified
**Branch and Bound**- “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**“. - State space tree
- Examples
- The 0-1 knapsack problem
- Traveling Salesperson Problem

- “Compute a number (bound) at a node to determine whether the node is

- 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

- “What about the
- 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
- Divide and conquer
- Dynamic programming
- Greedy approach
- Backtracking
- 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
- input size
- 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