Instructor: Dr. Xiaolin Wu, ITB-A315
Lectures: Monday, Wednesday, Thursday 10:30-11:20, ITB/137
Tutorials: T01: Thursday 8:30-10:20 JHE/326H
T02: Friday 14:30-16:20 T13/125
T03: Wednesday 14:30-16:20 JHE/326H
office hours: Mon. 2~4pm, ITB A302
office hours: Tue. 2~4pm, ITB A302
office hours: Wed. 10am~12pm, ITB A103
office hours: Thur. 2~4pm, ITB A302
office hours: Fri. 2:30~4:30pm, ITB A302
Tutorials start in the week of January 14
To provide a foundation of the concepts of data abstraction, algorithm design and performance estimation. The main topics to be discussed are:
1) Algorithm performance estimation using asymptotic complexity analysis.
2) The use and implementation of elementary data structures such as lists, stacks, queues, trees, binary search trees and hash tables.
3) Eﬃcient algorithms for searching and sorting.
Textbook: M.A. Weiss, Data Structures & Problem Solving Using JAVA, 3rd or
4th ed., Addison Wesley, (ISBN 0-321-32213-4).
Additional References - not required:
1) M. T. Goodrich, R. Tamassia, Data structures & Algorithms in Java
2) A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data structures and algorithms, Addison-Wesley,
3) T. E. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd or 3rd ed., MIT Press and McGraw-Hill.
4) Any good references on program design and on the Java programming language.
Java programming language review, brief math review.
✸ Algorithm Complexity Analysis:
Space and time complexity, asymptotic notation, examples.
Recursive algorithms, their space and time complexity analysis, divide and
Basic operations, array-based implementation, linked lists.
✸ Stacks and Queues:
Operations, array and linked-list implementations, applications.
Operations, pointer-based and array-based implementations.
✸ Searching and Hashing:
Linear search, binary search, binary search trees, hash tables.
✸ Sorting Algorithms:
Insertion sort, bubble sort, merge sort, quicksort, heaps, heap sort.
✸ (Time permitting) Graphs. Algorithms on Graphs:
Representation of graphs, paths, spanning trees, Dijkstra’s Algorithm, Prim’s
Assignments – 20% (3 individual programming assignments)
Midterm Test – 25%
Quizzes – 5%
Final Exam – 50%.
Midterm Sample Questions: