2SI4 Web Page

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


Teaching Assistants:  


H. Hassanein   

office hours:  Mon. 2~4pm, ITB A302


N. Iftikhn   

office hours: Tue. 2~4pm, ITB A302


Y. Shen

office hours: Wed. 10am~12pm, ITB A103


A. Hammad   

office hours: Thur. 2~4pm, ITB A302


A. Khezriam   

office hours: Fri. 2:30~4:30pm, ITB A302




Tutorials start in the week of January 14




Course Objectives:

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) Efficient algorithms for searching and sorting.


Required materials:

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

conquer method.


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:


Lecture Notes:


            Lecture Notes Sept. 11-18

Lecture Notes Link Lists

Lecture Notes Pointers


Lecture Notes Stacks


Lecture Notes Search Trees


Lecture Notes Hashing


Lecture Notes Heap


Lecture Notes Union-and-Find


Lecture Notes on Graph Algorithms