# 2143203 Fundamental Data Structure and Algorithm

1st semester 2010
Section 1  Wed    13-14:30,  Fri  13-14:30   room 2304/2
Prabhas Chongstitvatana

contact me at:  prabhas at chula dot ac dot th
office:  Engineering Building 4, floor 18, room 13
phone:   02-218-6982

. . .

## Topics

Week

1    Analysis of algorithms   Java refresh
2    Intro to algorithms  Asymptotic notation    Recurrence    Analysis of algorithm: how to
2.1     Intro to data structure  & Algo   (ppt   modified-Vishnu)
3    List   ( ListStackQueue   ppt Vishnu)
4    Stack
5    Queue   (queue Somchaip ppt)  NEW
6    Trees  and Binary Search Trees  (  Tree   ppt Vishnu )
7    ---
8   AVL trees  ( ppt Vishnu )
9    Hash  ( ppt Vishnu
10    Heap (1)      ( ppt  Jaruloj
11    Heap (2)
12    Sorting (1)    sorting    Weiss code   BasicSort.java
13    Sorting (2)
14    Spare    Application of Data Structure (ppt Somchaip) NEW
15     Summary and Revision

Midterm Exam      40%
Final Exam            40%
Homework            20%

## Reference Textbook

Mark Allen Weiss, Data Structures and Algorithm Analysis in Java (Second Edition), Addison-Wesley, 2007, ISBN: 0-321-37013-9.

Java code from the textbook  version Summer 2008 (zip file )

Java code for sorting     BasicSort.java    SelectionSort.java  InsertionSort.java  quickSort.java
You can cut and paste these codes into Java IDE (such as Eclipse) and try them.

## Homework

1  Write Java code to copy list.
2   . .
3   12 Nov 2010,  Write two versions of mergeSort
1)   as shown in class
2)   divide the array unequally, the first one is 1/3, the second one is 2/3
Run the experiment to compare these two.   Is the second version better of worse?

4   19 Nov 2010,  Write two versions of quicksort
1)    as shown in class  (pick the right most element as pivot)
2)    random pick pivot
Run experiment to compare two versions, measuring the number of calls to quicksort, with the data size
10, 100, 1000, 10000, 100000

last update  26 Nov 2010