Trees


    9.1   Introduction

    9.2   Terminology and Characterizations of Trees

            Problem-Solving Corner: Trees

    9.3   Spanning Trees

    9.4   Minimal Spanning Trees

    9.5   Binary Trees

    9.6   Tree Traversals

    9.7   Decision Trees and the Minimum Time for Sorting

    9.8   Isomorphisms of Trees

    9.9   Game Trees(Skipped)




Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree.

 

***

 

Table of Contents


​(DM Ch. 1, Sets and Logic, Lecture Note) 

 http://matrix.skku.ac.kr/2018-DM/Ch-1/ 
DM-Ch-1-Lab  http://matrix.skku.ac.kr/2018-DM/DM-Ch-1-Lab.html   (Use Chrome browser, not IE)
    (DM Ch. 1, 동영상강의) 
Discrete Math 이산수학 Ch 0 Introduction 
https://youtu.be/9ahFnOFTWNQ 
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions 
https://youtu.be/QgdKqmCFW2Y 
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference 
https://youtu.be/92siPfThf0M 
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers 
https://youtu.be/7M7w9eX5D0Q


​(DM Ch. 2, Proofs, Lecture Note) 

 http://matrix.skku.ac.kr/2018-DM/Ch-2/
DM-Ch-2-Lab  http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html 

     (DM Ch. 2, 동영상강의) 


​DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem   https://youtu.be/xEMkHb2AkYk
​DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and Well-Ordering Property 
https://youtu.be/areatkjOjcg 

​(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note) 

 http://matrix.skku.ac.kr/2018-DM/Ch-3/
DM-Ch-3-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html 

     (DM Ch. 3, 동영상강의) 
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 1  https://youtu.be/MhM_9ZuGAis 
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 2  
https://youtu.be/ZjAtN9HkZwM
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 3  
https://youtu.be/Uuwsx2aiEPI

 

Ch 4, Algorithms,


Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-4/


DM-Ch-4-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html 
    (DM Ch. 4, 동영상강의)
 https://youtu.be/Dtv-9ykjFFA 
   ​DM 이산수학 Ch 4,
...

  

[Week 6] Ch 5, Introduction to Number Theory (if time permits)

- Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-5/  

DM-Ch-5-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html 
    (DM Ch. 5, 동영상강의) 

​DM 이산수학 Ch 5,

 
Ch 6, Counting Methods and the Pigeonhole Principle (lightly covered)

 - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-6/  

DM-Ch-6-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html 
    (DM Ch. 6, 동영상강의) 

​DM 이산수학 Ch 6,


Ch 7, Recurrence Relations,   - Lecture Note 
http://matrix.skku.ac.kr/2018-DM/Ch-7/  

DM-Ch-7-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-7-Lab.html 
    (DM Ch. , 동영상강의) 

​DM 이산수학 Ch ,


Ch 8, Graph Theory (if time permits),  - Lecture Note 
http://matrix.skku.ac.kr/2018-DM/Ch-8/  

DM-Ch-8-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-8-Lab.html 
    (DM Ch. , 동영상강의) 

Ch 9, Trees (if time permits), Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-9/  

DM-Ch-9-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-9-Lab.html 
    (DM Ch. , 동영상강의) 


10 Network Models (if time permits)  http://matrix.skku.ac.kr/2018-DM/Ch-10/  
11 Boolean Algebras and Combinatorial Circuits (if time permits)
12 Automata, Grammars, and Languages (if time permits)
13 Computational Geometry (if time permits)
Appendix

       DM  Lecture Note & Lab & 동영상강의 

******

 

 

     9  Trees

 

 

9.1 Introduction


        

                    

                   Figure 1.2 The tree.

 


 Definition  1.1

 

 

                               

 


 Rooted tree

 

A rooted tree is a tree in which one vertex has been designated as the root.

 

 

 

Example  1.2

 

 In Figure, is the root.

 Figure is a rooted tree.

 The unique simple path from to is .

 

 


 

In graph theory rooted trees are typically drawn with their roots at the top.

The simple path from the root to any given vertex is unique, each vertex is on a uniquely determined level.

We call the level of the root level .

The vertices under the root are said to be on level , and so on. 



Level of a Vertex

 

The level of a vertex is the length of the simple path from the root to .


Height

 

The height of a rooted tree is the maximum of all level number of its vertices.



Example  1.3

 

 

   Level of vertex

 

   Level of vertex

   Level of vertex

                     Figure 1.4 Th tree with the root at the top.



Example  1.4

 

 


Example  1.5

 

 A rooted tree is often used to specify hierarchical relationships.

 If vertex is on a level one less than the level of vertex and and are adjacent,   then is “just above” and a logical relationship exists between and :           dominates or is subordinate to .


An example of such a tree, which is the administrative organizational chart of a hypothetical university, is given in Figure 1.6.

           

 

 


Example 1.6

 

 

       

      Figure 1.8 The structure of Figure 1.7 shown as a rooted tree.


Example  1.7

  Hierarchical Definition trees

 Such trees are used to show logical relationships among records in a database.

 The tree of Figure 1.9 might be used as a model for setting up a database to maintain   records about books housed in several libraries.

 

       

     Figure 9.1.9 A hierarchical definition tree.


 

Example  1.8

 Huffman codes

 

             

 


 Algorithm  1.9

Constructing an Optimal Huffman Code

 

Example  1.10

 

 

The algorithm beings by repeatedly replacing the smallest two frequencies with the sum until a two-element sequence is

 

The algorithm then constructs tree working backward beginning with two-element sequence , in Figure 1.13.

For example, the second tree is obtained from the frist by replacing the vertex label by the tree of Figure 1.14.

   is the sum of and .

Finally, to obtain the optimal Huffman coding tree, we replace each frequency by a character having that frequency.

 


 

 

 

9.2  Terminology and Characterizations of Trees

     Problem-Solving Corner: Trees


 Definition  2.1

 


An internal vertex is a vertex that has at least one child

A terminal vertex is a vertex that has no children

The tree in the example has internal vertices and terminal vertices

 

        

 

     

 


                

 


Example 2.2

 

 (a) The parent of Eros is Aphrodite.

 (b) The ancestors of Hermes are Zeus, Kronos and Uranus.

 (c) The children of Zeus are Apollo, Athena, Hermes and Heracles.

 (d) The descendants of Kronos are Zeus, Poseidon, Hades, Ares, Apollo, Athena,              Hermes and Heracles.

 (e) Aphrodite and Prometheus are siblings.

 (f) The terminal vertices are Eros, Apollo, Athena, Hermes, Heracles, Poseidon, Hades,       Ares, Atlas and Prometheus.

 (g) The internal vertices are Uranus, Kronos and Zeus.

 (h) The subtree rooted at Kronos is shown in Figure .

 

                

 


A subtree of a tree is a tree such that

 and


A tree cannot contain a cycle.


A graph with no cycles is an acyclic graph.


 Theorem  2.3

 

Let be a graph with vertices. The following are equivalent.

 (a) is a tree.

 (b) is connected and acyclic. (“acyclic”= having no circles)

 (c) is connected and has edges.

 (d) is acyclic and has edges.

 



9.3 Spanning Trees


Finding a subgraph of a graph such that is a tree containing all of the vertices of . This tree is spanning tree.

 


 Definition  3.1

 

 Tree is a spanning tree of a graph if is a subgraph of that contains    all of the vertices of .

 

 

Example  3.2

 

 A spanning tree of the graph of Figure 3.1 is shown in black.

 

 

Example  3.3

 

 In general, a graph will have several spanning trees.

 Another spanning tree of the graph of Figure 3.1 is shown in Figure 3.2.

 


A graph has a spanning tree .

Let and be vertices of .

Since and are vertices in and in a tree, there is a path from to .

However serves as a path from to in ; thus is connected.

The converse is true.

 

 Theorem  3.4

 

 


Example  3.5

 


 

                              


 Algorithm  3.6

 Breath-First Search for a Spanning Tree

 This algorithm finds a spanning tree using the breadth-first search method.

     Input: A connected graph with vertices ordered

   Output: A spanning tree

 

      vertices ordered edges

      vertices of spanning tree edges of spanning tree

      is the root of the spanning tree

      is an ordered list

     

     

     

     while (true)

          for each , in order,

             for each , in order,

                if( is an edge)

                   add edge to and to

          if (no edges were added)

             return

           children of ordered consistently with the original vertex ordering

      

   

 

                 

 

An alternative to breadth-first search is depth-first search, which proceeds to successive levels in a tree at the earliest possible opportunity.

 


 Algorithm  3.7

  Depth-First Search for a Spanning Tree

 This algorithm finds a spanning tree using the depth-first search method.

     Input: A connected graph with vertices ordered

   Output: A spanning tree

  

      vertices of spanning tree edges of spanning tree

      is the root of the spanning tree

     

     

     

     while (true)

       while(there is an edge that when added to does not create a cycle in

          choose the edge with minimum that when added to

             does not create a cycle in

          add to

          add to

          

      

       if

          return

       parent of in // backtrack

   

 


       

 

    Depth-First Search,

 Idea : proceeds to successive levels in a tree at the earliest possible opportunity.

 


Example  3.8

depth-first search=backtracking

 

                                  

 


Example  3.9

 Four-Queens Problem

 

 Algorithm  3.10

 Solving the Four-Queens Problem Using Backtracking

 The algorithm uses backtracking to search for an arrangement of four tokens on a      grid so that no two tokens are on the same row, column or diagonal.

      Input: An array row of size

    Output: true, if there is a solution false, if there is no solution

            [If there is a solution, the queen is in column , ]

 four-queens(row)

     // start in column

    // start in row

    // since row is incremented prior to use, set row to

    row

    while

       row row

       // look for a legal move in column

      while(rowcolumn , row conflicts)

         // try next row

            row row

      if (row)

         if

            return true

         else // next column

           

           row

          

         else // backtrack to previous column

           

       

        return false // no solution

   

 

The tree that Algorithm generates is shown in Figure .

 

The numbering indicates the order in which the vertices are generated. The solution is found at vertex .

The queens problem is to place tokens on a grid so that no two tokens are on the same row, column or diagonal.

Checking that there is no solution to the two- or three -queens problem is straightforward.

Many constructions have been given to generate solutions to queens problem for all .

 

 

 

9.4   Minimal Spanning Trees


Given a weighted graph , a minimal spanning tree is a spanning tree of the sum of whose weights is a minimum.

 

           

      Figure 4.1 Six cities and the costs of building roads between certain pairs of them.


       

 


 Definition  4.1

 

 is a weighted graph.

Minimal spanning tree of is a spanning tree of with minimum weight.


Example  4.2

 


The algorithm to find a minimal spanning tree that we will discuss is known as Prim’s Algorithm.

 

 

 Algorithm  4.3

 Prim’s Algorithm

 This algorithm finds a minimal spanning tree in a connected, weighted graph. 

  Input: A connected, weighted graph with vertices and start vertex .

        If is an edge, is equal to weight of : if is not an edge,          is equal to (a value greater than any actual weight).

  Output: The set of edges in a minimal spanning tree (mst)

       prim

         // if vertex has been added to mst

         // if vertex has not been added to mst

1.   for to

2.     

     // add start vertex to mst

3.  

     // begin with an empty edge set

4.  

     // put edges in the minimal spanning tree

5.   for to

        // add edge of minimum weight one vertex in mst and one vertex

        // not in mst

6.     

7.      for to

8.         if // if is a vertex in mst

9.             for to

10.               if

11.                   add_vertex

12.                  

13.                  

14.               

            // put vertex and edge in mst

15.        

16.        

17.    

18.     return

19. 


Example  4.4

 

 

Solution

 

The start vertex is .

At line we add vertex to the minimal spanning tree.

The first time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

 

Edge

Weight

 

The edge with minimum weight is selected.

 

At line and , vertex is added to the minimal spanning tree and edge is added to .

Edge

Weight

 

The next time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

The edge with minimum weight is selected.

At line and , vertex is added to the minimal spanning tree and edge is added to .

 

Edge

Weight

 

The next time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are


This time two edges have minimum weight .

A minimal spanning tree will be constructed when either edge is selected.

Edge is selected.

At line and , vertex is added to the minimal spanning tree and edge is added to .

The next time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

 

Edge

Weight

 

The edge with minimum weight is selected. At line and , vertex is added to the minimal spanning tree and edge is added to .

The last time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

 

Edge

Weight

The edge with minimum weight is selected.

 

At line and , vertex is added to the minimal spanning tree and edge is added to . The minimal spanning tree constructed in shown in Figure 4.3.


                      

Figure 4.4 A graph that shows that selecting an edge having minimum weight incident on the most recently added vertex does not necessarily yield a shortest path. Starting at , we obtain , but the shortest path from to is .


Prim’s Algorithm furnishes an example greedy algorithm.

A greedy algorithm is an algorithm that optimizes the choice at each iteration.

The principle can be summarized as “doing the best locally.” In Prim’s Algorithm, since we want a minimal spanning tree, at each iteration we simply abb an available edge with minimum weight.  

 

 Theorem  4.5

 

Prim’s Algorithm (Algorithm 4.3) is correct; that is, at the termination of Algorithm     4.3, is a minimal spanning tree.

 

 

9.5 Binary Trees


Every vertex in a binary tree has at most two children.

Each child is designed as either a left child or a right child.

When a binary tree is drawn,

  a left child is drawn to the left or

  a right child is drawn to the right.


 Definition  5.1

 

A binary tree is a rooted tree in which each vertex has either no children, one        child, or two children.

 A vertex has one child, that child is designated as either a left child or a right          child(but not both).

 A vertex has two children,

     one child is designated a left child and

     the other child is designated a right child.


Example  5.2

 

 In the binary tree of Figure 5.1,

 Vertex is the left child of vertex .

 Vertex is the right child of vertex .

 Vertex is the right child of vertex ; vertex has no left child.

 Vertex is the left child of vertex ; vertex has no right child.

Figure 5.1 A binary tree.


Example  5.3

 

 A tree that defines a Huffman code is a binary tree.

 The Huffman coding tree of Figure 1.10,

  moving from a vertex to a left child corresponds to using the bit ,

  moving from a vertex to a right child corresponds to using the bit .

Figure 1.10 A Huffman code.



A full binary tree is a binary tree in which

each vertex has two children or zero children. 

 


 Theorem  5.4

 

 


There are internal vertices (, , and ) and terminal vertices (, , , and ) for a total of vertices. 

 



Example  5.5

 Single-elimination tournament

 The graph of a single-elimination tournament is a full binary tree.

 The contestants’ name are listed on the left.

 Winner programs to the right.

 Eventually, there is a single winner at root.

 If the number of contestants is not a power of , some contestants receive byes.

 In Figure 5.2, contestant has a first-round bye.

 There are contestants in a single-elimination tournament, a total of matches    are played.

 

Solution

The number of contestants is the same as the number of terminal vertices, and the number of matches is the same as the number of internal vertices.

By Theorem 5.4,

so that .

                       

                               Figure 5.2 The graph of a single-elimination tournament.

 


About binary trees relates the number of terminal vertices to the height.


 Theorem  5.6

 

 


 and

Then  



Example  5.7

 

 The binary tree in Figure 5.3 has height and the number of terminals .

 For this tree, the inequality becomes an equality.

 

Figure 5.3 A binary tree of heigh with terminals. For this binary tree, .


If all terminal vertices of a full binary tree have the same level heigh of , then

.  

 


Binary Search Trees

 

If data item is stored in vertex and data item is stored in vertex , then if is a left child(or right child) of , some ordering relationship will be guaranteed to exist between and . This is binary search tree.


 Definition  5.8

 

A binary search tree is a binary tree in which data are associated with the      vertices. The data are arranged so that, for each vertex in , each data item in the   left subtree of is less than the data item in , and each data item in the right        subtree of is greater than the data item in .

 


Alphabetical Order

 

Alphabetical or lexicographic order is the order of the dictionary:

a) start with an ordered set of symbols . can be infinite or finite.

b) Let and be strings over .

   Then define if

     

      or if for all , ,

      for some such that and

      or if and for all , .



Example of Alphabetical Order

 

Let set of letters of the alphabet ordered according to precedence, i.e.

Let and .

In this case,

   

   

   .

So we go the fourth letter: and .

Since we have that

 


Example  5.9

 

The words

                       OLD  PROGRAMMERS  NEVER  DIE

THEY  JUST  LOSE  THEIR  MEMORIES

 may be placed in a binary search tree as shown in Figure 5.4.

 Notice that for any vertex ,

   each data item in the left subtree of is less than the data item in and

   each data item in the right subtree of is greater than the data item in .

 

                  

                                    Figure  5.4 A binary search tree.


OLD PROGRAMMERS NEVER DIE THEY JUST LOSE THEIR MEMORIES

 

 

 Algorithm  5.10

Constructing a Binary Search Tree

 This algorithm constants a binary search tree. The input is read in the order           submitted. After each words is read, it is inserted into the tree.

  Input: A sequence of distinct words and the length of the sequence

 Output: A binary search tree

   make_bin_search_tree

      let be the tree with one vertex, root

      store in root

      for to

          root

         search true // find spot for

         while(search)

             word in

             if

                if( has no left child)

                  add a left child to

                  store in

                  search false // end search

               

                else

                   left child of

             else //

                if( has no right child)

                  add a right child to

                  store in

                  search false // end search

               

                else

                   right child of

        // end while

     // end for

      return

   

 

                             



9.6   Tree Traversals


Breadth-first search and depth-first search provide ways to “walk” a tree, that is, to traverse a tree in a systematic way so that vertex is visited exactly once. In this section we consider three additional tree-traversal methods.


 Algorithm  6.1

 Preorder Traversal

 This recursive algorithm processes the vertices of a binary tree using preorder          traversal.

       Input: PT, the root of a binary tree, or the special value null to indicate than no 

               trees is input

       Output: Dependent on how “process” is interpreted in line

     preorder(PT)

 1.       if

 2.          return

 3.       process PT

 4.       left child of PT

 5.       preorder()

 6.       right child of PT

 7.       preorder()

    

 


The input consists of a tree with a single vertex.

We set to the root and call preorder().

Since is not equal to null, we proceed to line , where we process the root.

At line , we call preorder with equal to null since there is no left child.

We just saw that when no tree is input to preorder, thing is processed.

At line , when no tree is input to preorder, again nothing is processed.

Thus when the input consists of a tree with a single vertex, we process the root and return.

 

                             

The input is the tree of Figure 6.1.

 

We set to the root and call preorder().

Since is not equal to null, we proceed to line , where are process the root.

At line we call preorder with equal to the left child of the root.

The tree input to preorder consists of a single vertex, preorder processes that vertex.

We next process vertex .

At line , we process vertex .

The vertices are processed in order .

 

                                     

 


Example  6.2

 

 In what order are the vertices of the tree of Figure 6.3 processed if preorder traversal   is used?

 

Solution

Following lines (root/left/right) of Algorithm 6.1, the traversal proceeds as shown in Figure 6.4. Thus the order of processing is .

 

                           

 

Inorder traversal and postorder traversal are obtained by channing the position of line (root) in Algorithm 6.1. “Pre,” “in” and “post” refer to the position of the root in the traversal; that is “preorder” means root first, “inorder” means root second and “postorder” means root last. 

 


 Algorithm  6.3

  Inorder Traversal

 This recursive algorithm processes the vertices of a binary tree using inorder traversal.

  Input: PT, the root of a binary tree, or the special value null to indicate than no 

               trees is input

       Output: Dependent on how “process” is interpreted in line

     inorder(PT)

 1.       if

 2.          return

 3.       left child of PT

 4.       inorder()

 5.       process PT

 6.       right child of PT

 7.       inorder()

    


Example  6.4

 

 In what order are the vertices of the binary tree of Figure 6.3 processed if inorder      traversal is used?

 

Solution

Following lines (left/root/right) of Algorithm 6.3, we obtain the inorder listing

 



 Algorithm  6.5

 Postorder Traversal

This recursive algorithm processes the vertices of a binary tree using postorder traversal.

  Input: PT, the root of a binary tree, or the special value null to indicate than no 

               trees is input

       Output: Dependent on how “process” is interpreted in line

     postorder(PT)

 1.       if

 2.          return

 3.       left child of PT

 4.       postorder()

 5.       right child of PT

 6.       postorder()

 7.       process PT

    

 


           Preorder traversal                     Inorder traversal

              Root-Left-Right                          Left-Root-Right

             


        Postorder traversal

           Left-Right-Root

 

Example  6.6

 

 In what order are the vertices of the binary tree of Figure 6.3 processed if postorder    traversal is used?

 

Solution

Following lines (left/root/right) of Algorithm 6.5, we obtain the postorder listing .


       

Figure 6.5 Preorder traversal.           Figure 6.6 Reverse postorder traversal.


 

Figure 6.7 The binary tree representation of the expression



The variables and are referred to as operands.

The operators , , * and operate on pairs of operands or expression.

infix form of an expression

fully parenthesized form of the express

postfix from of the expression(or reverse Polish notation) *

  

               

                   


prefix from of the expression(or Polish notation) * 



9.7   Decision Trees and the Minimum Time for Sorting


Decision Tree

 Definition

 

 A binary tree containing an algorithm to decide which course of action to take.

Use

  to specify algorithms

  to obtain lower bounds on the worst-case time for sorting



Example  7.1

 Five-Coins Puzzle

 Five coins are identical in appearance, but one coin is either heavier or lighter than the    others, which all weigh the same.

The problem is

 to identify the bad coin and

 determine whether it is heavier or lighter than the others

 using only a pan balance, which compares the weights of two sets of coins.

 

Solution

 

An algorithm to solve the puzzle is given Figure as a decision tree.

The coins are labeled , , , , .

As shown, we begin at the root place coin in the left pan and coin in the right pan.  At edge labeled means that left side of the pan balance is heavier than the right side.

Edge labeled means that right side of the pan balance is heavier than the left side.

Edge labeled means that the two side balance.

For example , at the root when we compare with ,

if the left side is heavier than the right side,

we know that either is the heavy coin or  is the light coin.

In this case, as shown in the decision tree, we next compare with (which is known to be a good coin) and immediately determine whether the bad coin is or and whether it is heavy or light.

The terminal vertices give the solution.

For example, when we compare with and the pans balance, we follow the edge to the terminal vertex labeled . The bad coin is .

 

The coin is light than the others coin.

Figure 9.7.2 A pan balance for comparing weights of coins.

Figure 9.7.3 An algorithm to solve the five-coins puzzle.



The five-coins puzzle has outcomes:

,,          ,,          ,,          ,,          ,,

,,          ,,          ,,          ,,          ,.

Figure 9.7.4 A five-coins puzzle algorithm that uses at most two weightings.



Figure 9.7.5 A four-coins puzzle algorithm that begins by comparing two coins against two coins.


Figure 9.7.6 A four-coins puzzle algorithm that begins by comparing one coin against one coin.



The sorting problem is easily described: Given items

,

arrange them in nondecreasing(or nonincreasin) order. We  restrict our attention to sorting algorithms that repeatedly compare two elements and based on the result of the comparison, modify the original list. 


 

Example  7.2

 

 

An algorithm to sort , , is given by the decision tree of Figure . Each edge is labeled with the arrangement of the list based on the answer to the question at an internal vertex. The terminal vertices give the sorted order.

Let us define the worst-case time to sort to be the number of comparisons in the worst case. The height of a decision tree that solves a sorting problem is equal to the worst-case time.

But the problem of sorting three items has six possible outcomes(when the items are distinct), corresponding to the ways that three items can be arranged:

,,,        ,,,        ,,,        ,,,        ,,,        ,,.

This is a contradiction. Therefore, no algorithm that sorts three items has worst-case time less than , and the algorithm of Figure is optimal.

 


Figure 9.7.7 An algorithm to sort , ,

Figure 9.7.8 A sorting algorithm that makes at most two comparisons.

 


Since , there are possible outcomes to the problem of sorting four items(when the items are distinct). To accommodate terminal vertices, we must have a tree of height at least (see Figure ). Therefore, any algorithm that sorts four items requires at least five comparisons in the worst case.

 

Level

Number of Vertices

Figure 9.7.9 Level compared with the maximum number of vertices in that level in a binary tree.



Figure 9.7.9 Level compared with the maximum number of vertices in that level in a binary tree. 

 



 Theorem  7.3

 

If is the number of comparisons needed to sort items in the worst case by a    sorting algorithm, then .

Proof 

 is the decision tree that represents the algorithm for input of size .

 denoted the height of .

Then the algorithm requires comparisons in the worst case, so

(7.1)                                  .

The tree has at least terminal vertices, so by Theorem ,

(7.2)                                  .

Shows that ; for some positive constant ,

(7.3)                              

for all but finitely many integer .

Combining (7.1) through (7.3), we obtain

for all but finitely many integer .

Therefore

 


 


9.8   Isomorphisms of Trees


The simple graphs and are isomorphic if and only if there is a one-to-one, onto function from the vertex set of to the vertex set of that preserves the adjacency relation in the sense that vertices and are adjacent to if and only if the vertices  and are adjacent in .

Since a tree is a simple graph, tree and are isomorphic if and only if there is a one-to-one, onto function from the vertex set of to the vertex set of that preserves the adjacency relation; that is, vertices and are adjacent to if and only if the vertices  and are adjacent in


Example  8.1

 


That two trees are not isomorphic if we can exhibit an invariant that the trees do not share.


Example  8.2

 

 

                         


 


 Theorem  8.3

 

There are three nonisomorphic trees with five vertices.

 

Proof

 


For two rooted trees and are isomorphic, there is a one-to-one, onto function from to that preserves the adjacency relation and that preserves the root. The latter condition means that



 


 Definition  8.4

 

 


Example  8.5

 

 


Example  8.6

 

 


 Theorem  8.7

 

There are four nonisomorphic rooted trees with four vertices. These four rooted trees    are shown in Figure 8.9.

 

                                             

                     (a)                (b)              (c)            (d)

             Figure 8.9 The four nonisomorphic rooted trees with four vertices.

 

 


 Definition  8.8

 


Example  8.9

 


 



                                                           

                              

                                                    


Example  8.10

 

 

        

The trees and of Figure 8.11 are isomorphic as rooted trees and as free trees.

As rooted trees, either of the trees of Figure 8.11 is isomorphic to the rooted tree of Figure 8.9(c). 

 



 Theorem  8.11

 

There are five nonisomorphic binary trees with three vertices.

 These five binary trees are shown in Figure .

 

                                             

          (a)                (b)              (c)             (d)               (e)

       Figure 8.12 The five nonisomorphic binary trees with three vertices.



If is a set of trees of a particular type( is a set of free trees or is a set of rooted trees or is a set of binary trees) and we define a relation on by the rule if and are isomorphic, is an equivalence relation. Each equivalence class consists of a set of mutually isomorphic trees. 

 


 Theorem  8.12

 

There are nonisomorphic binary trees with vertices where    is the Catalan number.

 

                                           

Figure 8.13 The two nonisomorphic binary trees with two vertices.

 


          


 and is nonemptyset, after which we check that left subtrees of and are isomorphic and that the right subtrees of and are isomorphic. 



Algorithm  8.13

Testing Whether Two Binary Trees Are Isomorphic

        Input: The roots and of two binary trees.

            (If the first tree is empty, has the special value null.

            If the second tree is empty, has the special value null.)

    Output: true, if the trees are isomorphic

            false, if the trees are not isomorphic

        bin_tree_isom

 1.           if

 2.             return true

        // now one or both of or is not null

 3.           if

 4.             return false

        // now neither of or is null

 5.      left child of

 6.      left child of

 7.      right child of

 8.      right child of

 9.      return bin_tree_isom

    



 Theorem  8.14

 

The worst-case time of Algorithm 8.13 is , where is the total number of       vertices in the two trees.

 



 


Exercises

 

 (이 강의록은 성균관대 김응기 박사님, 이영수 박사님, 김장수 교수님 등의 기존 강의록과 교재 및 참고자료를 바탕으로 이상구 교수가 새로 만든 2018년 1학기 용 강의록입니다.)

(강의록에 실습실을 추가하여 이론과 실습을 같이 할 수 있는 새로운 수학 강의 의 모델입니다)

Copyright by SGLee, SKKU  sglee@skku.edu


http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm

 

     

*** References   (Calculus)

 

 

< Calculus 미적분학 1, 2 >

http://matrix.skku.ac.kr/Cal-Book/

(Lecture Movie 동영상 강의) SKKU 성균관대

- Calculus with Sage Lectures (Youtube 동영상 강의)

 

<미적분학 동영상 강의이상구 교수성균관대

- Calculus with Sage Lectures (Youtube 동영상 강의)

 

1.1 History of Calculus : http://youtu.be/ODfMaHgIhAc

Calculus with Sage Week 1

how to manage our class Review : http://youtu.be/XWEQFlv4jKc

Chapter 1. Functions

http://youtu.be/cl8GqIWIRD0 (동영상 강의)

1.1 Functions and its graph

1.2 Symmetry (문제 풀이)

1.3 Common Functions

1.4 Translation, Stretching and Rotation of Functions

1.5 A Few Basic Concepts

 

Chapter 2. Limits and Continuity

2.1 Limits of functions : http://youtu.be/VBCeAllP1M0 (동영상 강의)

2.2 Continuity : http://youtu.be/zGxx3PUCTnM (동영상 강의)

 

Chapter 3. Theory of Differentiation

3.1 Definition of Derivatives, Differentiation : http://youtu.be/A-vDsF9ulTs (동영상 강의)

3.2 Derivatives of Polynomials, Exponential Functions, Trigonometric Functions, The product rule: http://youtu.be/XXMnCESesfQ

3.3 The Chain Rule and Inverse Functions : http://youtu.be/HfScHEsPfKI

3.4 Approximation and Related Rates : http://youtu.be/ViRwEJ0Wfkw

 

Chapter 4. Applications of Differentiation

4.1 Extreme values of a function : http://youtu.be/mXVU8OqIHJY (동영상 강의)

4.2 The Shape of a Graph : http://youtu.be/cZrAF_77On4

4.3 The Limit of Indeterminate Forms and L’Hospital’s Rule :

http://youtu.be/vp-gck5-gKE

4.4 Optimization Problems : http://youtu.be/k0NtkmZFnh8

4.5 Newton’s Method : http://youtu.be/VxCfl2JzMYU

 

Chapter 5. Integrals

 

5.1 Areas and Distances : http://youtu.be/mT_oxlD6RSA (동영상 강의)

5.2 The Definite Integral : http://youtu.be/GIm3Oz58Ti8

5.3 The Fundamental Theorem of Calculus : http://youtu.be/Zf1HT2H2fbA

5.4 Indefinite Integrals and the Net Change Theorem : http://youtu.be/E6I3EDzAVuU

5.5 The Substitution Rule : http://youtu.be/h7tmvmNOliU

5.6 The Logarithm Defined as an Integral : http://youtu.be/kD0Z9PqetsA

 

 

Midterm Exam : 4월 24일 수요일 4시에 강의실

 

미적분학 with Sage Midterm Exam, http://youtu.be/QAEI7A2DMMM

Chapter 6. Applications of Integration

미적분학 with Sage Sec-6-1 Areas between Curves, http://youtu.be/o53phm5cqJE

미적분학 with Sage Sec-6-2 Volumes, http://youtu.be/4-ChOAFbJAs

미적분학 with Sage Sec-6-3 Volumes by Cylindrical Shells,

http://youtu.be/qM1izf8qeX8 (동영상 강의)

미적분학 with Sage Sec-6-4 Work : http://youtu.be/u3ZaJWhKy6k

미적분학 with Sage Sec-6-5 Average Value of a Function

http://youtu.be/zmEeGmwQTB0

 

Chapter 7. Techniques of Integration

미적분학 with Sage Sec-7-1 Integration by Parts http://youtu.be/WX-6C9tCneE

미적분학 with Sage Sec-7-2 Trigonometric Integrals http://youtu.be/sIR0zNGQbus

미적분학 with Sage Sec-7-3 Trigonometric Substitution http://youtu.be/avTqiEUi8u8

미적분학 with Sage Sec-7-4 Integration of Rational Functions by the Method of Partial Fractions http://youtu.be/KLTHp_7G4cI

미적분학 with Sage Sec-7-5 Guidelines for Integration http://youtu.be/Fgn8U4We60o

미적분학 with Sage Sec-7-6 Integration Using Tables http://youtu.be/tn9jLkgTMp8

미적분학 with Sage Sec-7-7 Approximate Integration http://youtu.be/hg2pw1n1cZI

미적분학 with Sage Sec-7-8 Improper Integrals http://youtu.be/rquxbYrC0Yc

 

Chapter 8. Further Applications of Integration

미적분학 with Sage Sec-8-1 Arc Length http://youtu.be/7OVqI20z_Bw

미적분학 with Sage Sec-8-2 Area of a Surface of Revolution

http://youtu.be/Eq4i2A8eKxA

미적분학 with Sage Sec-8-3 Applications of Integral Calculus

http://youtu.be/1ZAJeP16pAQ

*미적분학 with Sage Sec-8-4 Differential equations http://youtu.be/uHfOjz8I4-s

 

Chapter 9. Parametric Equations and Polar Coordinates

9.1 Parametric Equations

9.2 Calculus with Parametric Curves

9.3 Polar Coordinates

9.4 Areas and Lengths in Polar Coordinates

9.5 Conic Section

Chapter 10. Infinite Sequences and Infinite Series

10.1 Sequences and Series

10.2 Tests for convergence of series with positive terms

10.3 Alternating Series and Absolute Convergence

10.4 Power Series

 

강의에 앞서 http://youtu.be/YtxYZW3Enko (동영상 강의)

 

Chapter 11. Vectors and the Geometry of Space

11.1 Three-Dimensional Coordinate Systems

11.2 Vectors

11.3 The Dot Product

11.4 The Vector or Cross Product

11.5 Equations of Lines and Planes

11.6 Cylinders and Quadric Surfaces

 

Chapter 12. Vector Valued Functions

12.1 Vector-Valued Functions and Space Curves http://youtu.be/0pvywjBjsQw

12.2 Calculus of Vector Functions

12.3 Arc Length and Curvature

*12.4 Motion Along A Space Curve: Velocity and Acceleration

 

Chapter 13. Partial Derivatives

13.1 Multivariate Functions

13.2 Limits and Continuity of Multivariate Functions

13.3 Partial Derivatives http://youtu.be/LR89Ct3cEDY (동영상 강의)

13.4 Differentiability and Total Differentials

13.5 The Chain Rule http://youtu.be/r3dGYL1vkEU

13.6 Directional Derivatives and Gradient http://youtu.be/o8L_ShRANjo

13.7 Tangent Plane and Differentiability http://youtu.be/uOf-5YHKGI4

13.8 Extrema of Multivariate Functions http://youtu.be/oDZUkOEszOQ

13.9 Lagrange Multiplier

 

Chapter 14. Multiple Integrals

14장 앞부분 복습 내용http://youtu.be/5eCO2GjlJHs (동영상 강의)

Chapter 14. Multiple Integrals

14.1 Double Integrals http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-1-Sol.html

14.2 Double Integrals in Polar Coordinates

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-2-Sol.html

14.3 Surface Area http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-3-Sol.html

14.4 Cylindrical Coordinates and Spherical Coordinates http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-4-Sol.html

14.5 Triple Integrals

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-5-Sol.html

14.6 Triple Integrals in Cylindrical and Spherical Coordinates

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-6-Sol.html

14.7 Change of Variables in Multiple Integrals

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-7-Sol.html

 

14.1 Double Integrals http://youtu.be/jZ2pAmPZYOE (동영상 강의)

14.2 Double Integrals in Polar Coordinates http://youtu.be/olQgihl5aZg

14.3 Surface Area http://youtu.be/p9R0TTLfBzk

14.4 Cylindrical and Spherical Coordinates http://youtu.be/q3FKd2UxV_I

14.5 Triple Integrals http://youtu.be/r1tzH9Ibbqk

14.6 Triple Integrals in Cylindrical &Spherical Co http://youtu.be/xd0U4_C2ePY

14.7 Change of Variables in Multiple Integrals http://youtu.be/INn-bkgXYNg

 

Chapter 15. Vector Calculus

Chapter 15. Vector Calculus

15.1 Vector Differentiation

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-1-Sol.html

15.2 Line Integrals http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-2-Sol.html

15.3 Independence of the Path

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-3-Sol.html

15.4 Green’s Theorem in Plane

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-4-Sol.html

15.5 Curl and Divergence

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-5-Sol.html

15.6 Surface and Area

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-6-Sol.html

15.7 Surface Integrals

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-7-Sol.html

15.8 Stokes’ Theorem

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-8-Sol.html

15.9 Divergence Theorem

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-9-Sol.html

15.1 Vector Differentiation http://youtu.be/q0aVmUCXgTI (동영상 강의)

15.2 Line Integrals http://youtu.be/wHINlpNXYaU

15.3 Independence of the Path http://youtu.be/jGGOL3QDj1Y

15.4 Green’s Theorem in Plane http://youtu.be/WxdTbaSb_ZI

15.5 Curl and Divergence http://youtu.be/IswmJUCTeNA

15.6 Surface and Area http://youtu.be/xX6tNVpegbs

15.7 Surface Integrals http://youtu.be/nrzIrM4doLo

15.8 Stokes’ Theorem http://youtu.be/t4skc_PzJvg

15.9 Divergence Theorem http://youtu.be/3BmcFr81kuQ

 

(SKKU 선형대수학 Jordan 표준형, SGLee : http://youtu.be/Dn4qBxgUJcA )

 

**************************************************

<Calclus 미적분학 1, 2>

http://matrix.skku.ac.kr/Cal-Book/

(동영상) <성균관대 학생 문제 풀이 설명 (by Students)>

 

 

Chapter 1. Functions

미적분학 with Sage Sec-1-1 Functions and Graph, Problem, 문제풀이 by 황인철 http://youtu.be/rQ2CB8EvkoE

미적분학 with Sage Sec-1-2 Symmetry, Problem, 문제풀이 by 곽주현 http://youtu.be/BNKUzSohiD8

미적분학 with Sage Sec-1-3 Common Functions, Problem, 문제풀이 by 장찬영 http://youtu.be/x0E0ZMxZ3Og

미적분학 with Sage Sec-1-4 Translation, Stretching and Rotation of Functions, Problem, 문제풀이 by 임효정 http://youtu.be/vx7GCWY68Zw

 

Chapter 2. Limits and Continuity

미적분학 with Sage Sec-2-1 Limits of functions, Problem, 문제풀이 by 장재철-이훈정 http://youtu.be/LZSmRPAAXME

미적분학 with Sage Sec-2-2 Continuity, Problem, 문제풀이 by 이훈정 http://youtu.be/azrkT1RP4-c

미적분학 with Sage Sec-2-2 Continuity, Epsilon-Delta Proof, by 황인철 http://youtu.be/hj8d-j_DGf4

 

Chapter 3. Theory of Differentiation

미적분학 with Sage Sec-3-1 Definition of Derivatives, Differentiation, Problem, 문제풀이 by 김태현 http://youtu.be/7wTBWuk2CzU

미적분학 with Sage Sec-3-2 Derivatives of Polynomials, Exponential Functions, Trigonometric, Problem, 문제풀이 by 조건우 http://youtu.be/Ei5KGW9vZhE

미적분학 with Sage Sec-3-3 The Chain Rule and Inverse Functions, Problem, 문제풀이 by 유휘의 http://youtu.be/aSKm12922FE

미적분학 with Sage Sec-3-4 Approximation and Related Rates, Problem, 문제풀이 김종민 http://youtu.be/JmBOv6_D6qA

 

Chapter 4. Applications of Differentiation

미적분학 with Sage Sec-4-1 Extreme values of a function, Problem, 문제풀이 by 김태영 http://youtu.be/_V4MryNEzWY

미적분학 with Sage Sec-4-2 The Shape of a Graph, Problem, 문제풀이 by 김태영 http://youtu.be/SVOWADHlzV8

미적분학 with Sage Sec-4-3 Indeterminate Forms and L'Hospital's Rule, Problem, 문제풀이 by 신종희 http://youtu.be/gR2luDDPsMY

미적분학 with Sage Sec-4-4 Optimization, Problem, 문제풀이 by 이승철 http://youtu.be/AELEV2ElaeQ

미적분학 with Sage Sec-4-5 Newton's Method, Problem, 문제풀이 by 이승철http://youtu.be/fdBHQ46g9RE

 

Chapter 5. Integrals

미적분학 with Sage Sec-5-1 Area and Distance, Problem, 문제풀이 by 남택현 http://youtu.be/Y_nCn76RPmY

미적분학 with Sage Sec-5-2 Definite Integral, Problem, 문제풀이 by 남택현http://youtu.be/iUsf1h_hTAE

미적분학 with Sage Sec-5-3 and 5-4 Fun Theorem of Calculus Net Change Theorem, Problem, 문제풀이 by 정승찬 & Kim http://youtu.be/Pa4Z38KkDVY

(미적분학 with Sage Sec-5-4 Net Change Theorem, Problem, 문제풀이 by Kim *** )

미적분학 with Sage Sec-5-5 Substitution, Problem, 문제풀이 by 이한울 http://youtu.be/0TMbpCPO4Uc

미적분학 with Sage Sec-5-6 Log and Exponential, Problem, 문제풀이 by 이한울 http://youtu.be/ymDImdIQ90c

 

Chapter 6. Applications of Integration

미적분학 with Sage Sec-6-2 Volumes, 문제풀이 by 김종민 http://youtu.be/Fd4Mguf2dbU

미적분학 with Sage Sec-6-3 Volumes by Cylindrical Shells, Problem, 문제풀이 by 신영찬 http://youtu.be/gNaKkA0UNHg

미적분학 with Sage Sec-6-4 Work, Problem, 문제풀이 by 김건호 http://youtu.be/SmIo2yaxNsY

미적분학 with Sage Sec-6-5 Average Value of a Function, Problem, 문제풀이 by 신종희 http://youtu.be/BVahd-DJoe8

 

Chapter 7. Techniques of Integration

미적분학 with Sage Sec-7-1 Integration by Parts, 문제풀이 by 이인행 http://youtu.be/jKCAGJ4HqvQ

미적분학 with Sage Sec-7-2 Trigonometric Integrals, 문제풀이 by 김태현 http://youtu.be/ytETYf1wLbs

미적분학 with Sage Sec-7-3 Trigonometric Substitution, Problem, 문제풀이 by 이훈정 http://youtu.be/utTQHIabTyI

미적분학 with Sage Sec-7-4 Integration of Rational Functions by the Method of Partial Fractions, Problem, 문제풀이 by 장재철 http://youtu.be/SkNW_bax0YI

미적분학 with Sage Sec-7-5 Guidelines for Integration, Problem, 문제풀이 by 김대환 http://youtu.be/-N9Fe_Arp2c

미적분학 with Sage Sec-7-6 Integration Using Tables, Problem, 문제풀이 by 조건우 http://youtu.be/EnEQ9ZS3B_k

미적분학 with Sage Sec-7-8 Improper Integrals, Problem, 문제풀이 by 이인행 http://youtu.be/dfSkjvmSXYo

 

Chapter 8. Further Applications of Integration

미적분학 with Sage Sec-8-1 Arc Length, 문제풀이 by 남택현 http://youtu.be/A8N-mDD0ja8

미적분학 with Sage Sec-8-2 Area of a Surface of Revolution, 문제풀이 by 정승찬 http://youtu.be/yZFJDJgTJfw

(미적분학 with Sage Sec-8.3 Center of Mass

(미적분학 with Sage Sec-8.4 Differential equations

 

Chapter 9. Infinite Sequences and Infinite Series

미적분학 with Sage Sec-9-1 Sequences and Series, 문제풀이 by 이원준 http://youtu.be/O6y1v5fJA0k

미적분학 with Sage Sec-9-2 Tests for convergence of series with positive terms, 문제풀이 by 김범윤 http://youtu.be/1flKAnlv9LA

미적분학 with Sage Sec-9.3 Alternating Series and Absolute Convergence ?

(미적분학 with Sage Sec-9.4 Power Series ?

(미적분학 with Sage Sec-9.5 Taylor, Maclaurin, and Binomial Series ?

 

Chapter 10. Parametric Equations and Polar Coordinates

미적분학 with Sage Sec-10-1 Parametric Equations, 문제풀이 by 임효정 http://youtu.be/Ybs68e0iMZI

미적분학 with Sage Sec-10-2 Calculus with Parametric Curves, 문제풀이 by 장찬영 http://youtu.be/yF5oZOQVnCE

미적분학 with Sage Sec-10-3 Polar Coordinates, Problem, 문제풀이 by 황인철 http://youtu.be/4hoVKvk8dq0

미적분학 with Sage Sec-10-4 Areas and Lengths in Polar Coordinates, Problem, 문제풀이 by 곽주현 http://youtu.be/LRmasW9uqYY

미적분학 with Sage Sec-10-5 Conic Section, Problem, 문제풀이 by 이한울 http://youtu.be/CZ9SHMtqVy4

 

Chapter 11. Vectors and the Geometry of Space

미적분학 with Sage Sec-11.1 Three-Dimensional Coordinate Systems, 문제풀이 by 김태현 http://youtu.be/_s_2T1VVob8

미적분학 with Sage Sec-11.2 Vectors, 문제풀이 by 오교혁 http://youtu.be/BFgh6irMqsc

(미적분학 with Sage Sec-11.3 The Dot Product ?

(미적분학 with Sage Sec-11.4 The Vector or Cross Product ?

미적분학 with Sage Sec-11.5 Equations of Lines and Planes, 문제풀이 by 구본우 http://youtu.be/lxuGE_Erthg

(미적분학 with Sage Sec-11.6 Cylinders and Quadric Surfaces ?

 

Chapter 12. Vector Valued Functions

 

미적분학 with Sage Sec-12.1 Vector-Valued Functions and Space Curves, 문제풀이 by 최양현 http://youtu.be/jvMI6OzdR_I

미적분학 with Sage Sec-12.2 Calculus of Vector Functions , 문제풀이 by 김동윤 http://youtu.be/VS5rPyOjP2I

(미적분학 with Sage Sec-12.3 Arc Length and Curvature ?

(미적분학 with Sage Sec-12.4 Motion Along A Space Curve: Velocity and Acceleration ?

 

Chapter 13. Partial Derivatives

미적분학 with Sage Sec-13.1 Multivariate Functions, 문제풀이 by 구본우 http://youtu.be/As_0AYApHlM

(미적분학 with Sage Sec-13.2 Limits and Continuity of Multivariate Functions, 문제풀이 by 김건호?

(미적분학 with Sage Sec-13.3 Partial Derivatives, 문제풀이 by 김동윤?

미적분학 with Sage Sec-13.4 Differentiability and Total Differentials, 문제풀이 by 김범윤 http://youtu.be/qDmCWBiXbIA

미적분학 with Sage Sec-13.5 The Chain Rule, 문제풀이 by 김유경 http://youtu.be/vzN5By6qzvM

미적분학 with Sage Sec-13.6 Directional Derivatives and Gradient, 문제풀이 by 김태현 http://youtu.be/2_7TOUuzJoE

미적분학 with Sage Sec-13.7 Tangent Plane and Differentiability, 문제풀이 by 서용태 http://youtu.be/GDkE8OqUvsk

미적분학 with Sage Sec-13.8 Extrema of Multivariate Functions, 문제풀이 by 오교혁 http://youtu.be/FWmk_MasIjE

미적분학 with Sage Sec- 13.9 Lagrange Multiplier, 문제풀이 by 이원준 http://youtu.be/YMGdQWBzyrI

 

Chapter 14. Multiple Integrals

미적분학 with Sage Sec-14.1 Double Integrals, 문제풀이 by 이인행 http://youtu.be/w8g9fgcEP4A

미적분학 with Sage Sec-14.2 Double Integrals in Polar Coordinates, 문제풀이 by 이지석 http://youtu.be/jpsObxtZ50A

(미적분학 with Sage Sec-14.3 Surface Area, 문제풀이 by 이한울?

(미적분학 with Sage Sec-14.4 Cylindrical Coordinates and Spherical Coordinates, 문제풀이 by 최양현?

미적분학 with Sage Sec-14.5 Triple Integrals, 문제풀이 by 이인행 http://youtu.be/Voq67ooqQJs

(미적분학 with Sage Sec-14.6 Triple Integrals in Cylindrical and Spherical Coordinates, 문제풀이 by 구본우?

(미적분학 with Sage Sec-14.7 Change of Variables in Multiple Integrals, 문제풀이 by 김건호 최양현?

 

Chapter 15. Vector Calculus

(미적분학 with Sage Sec-15.1 Vector Differentiation, 문제풀이 by 김동윤?

미적분학 with Sage Sec-15.2 Line Integrals, 문제풀이 by 김범윤 http://youtu.be/ZdRjCfJeHM8

미적분학 with Sage Sec-15.3 Independence of the Path, 문제풀이 by 김유경 http://youtu.be/TreCe8ESEiU

(미적분학 with Sage Sec-15.4 Green’s Theorem in Plane, 문제풀이 by 김태현?

미적분학 with Sage Sec-15.5 Curl and Divergence, 문제풀이 by 서용태 http://youtu.be/wLTHYaANwtI

미적분학 with Sage Sec-15.6 Surface and Area, 문제풀이 by 오교혁 http://youtu.be/j7F3xVNdHvA

미적분학 with Sage Sec-15.7 Surface Integrals, 문제풀이 by 이원준 http://youtu.be/s_MRgW2By38

(미적분학 with Sage Sec-15.8 Stokes’ Theorem, 문제풀이 by 이인행?

미적분학 with Sage Sec-15.9 Divergence Theorem, 문제풀이 by 최주영 http://youtu.be/vGMLoGWF1Is

 

 

Copyright by SGLee, SKKU  sglee@skku.edu

http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm