Algorithm

CS3001302

Hsing-Kuo Pao 鮑興國

National Taiwan University of Science and Technology

Fall  2004

期末考教室改為 IB-501 及 IB-502

Class lectures: Monday 15:30~17:20  &  Thursday 15:30~16:20 (IB 702)

Instructor: Hsing-Kuo Pao 鮑興國 , 綜合研究大樓 RB-503-1 , 2730-1065

Teaching Assistants:

• 陳慶豪 (M9315018)

• 李育翔 (M9315062)

Text Book:

• Introduction to Algorithms, 2/e         Thomas H. Cormen, Charles E. Leiserson, 2001

Prerequisite:

• Any high-level languages (C/C++, Java, etc), data structure

Grading:

• 30 %  homework

• 30 %  midterm (Dec. 2)

• 40 %  final (Dec. 6)

Homework

(No copying, any reference should be clearly cited!)

1. Please write a short code to do bottom-up merge sort.

    The bottom-up style means no recursive calls should be used in your program.

    Of course, your program should be like a merge sort, instead of an insertion sort or anything else.

    The input can be any size, like 59 or 38 which is not equal to 2^k, k³1.

    You can test your program by several not too large inputs.

    To submit the homework, please print out your program, with at least 3 input sequences.

2. Please give asymptotically tight solution to the following recurrence equations.

    (i)     T(n) = T(9n/10) + n

    (ii)    T(n) = 7T(n/2) + n²

    (iii)   T(n) = 2T(n/4) + n^0.5

    (iv)   T(n) = 4T(n/2) + n^2.5

    (v)    T(n) = T(n -1) + lgn

    (vi)   T(n) = T(n -2) + 2lgn

Slides in the Class

                1. The Role of the Algorithms in Computer

                2. Getting Started

                    3. Growth of Functions

                4.  Recurrences

                5. Elementary Sorting

                6. Heap sort

                7. Quick sort

                8. Sorting in Linear Time

                9. Hash Table

                10.  Dynamic Programming

                11.  Disjoint Sets

                12.  Elementary Graph Algorithms

                13.  Minimum Spanning Tree

Midterm

                    Dec. 2 (Thursday)

                期中考教室改為 IB-501 及 IB-502

Final

                    Jan. 6 (Thursday)

                期末考教室改為 IB-501 及 IB-502