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
.
. .
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%
Mark Allen Weiss, Data Structures and Algorithm
Analysis in
Java (Second Edition), Addison-Wesley, 2007, ISBN: 0-321-37013-9.
see author's home page: http://www.cs.fiu.edu/~weiss/
for
errata
and
source
code.
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.
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