CSC2520

Data Structures and Applications, Spring 1998

Department of Computer Science and Engineering
The Chinese University of Hong Kong
Shatin, New Territories

This course formally examines the relationship between abstract data types and data structures. The implementation o fabstract data type using various data structures will be discussed. Sample abstract data types including vector, list, stack, queueand tree will be introduced and illustrated with applications such as searching, sorting, etc.

Dr. Irwin King, HSH 908, +(852) 2609-8398, king@cse.cuhk.edu.hk
Official newsgroup: cuhk.cse.2520

Table of Contents

• Office Hours
  
• Lecture Hours
  
• Tutorial Hours
  
• TAs and Tutorial Sessions
  
• Syllabus
  
• Homework Assignments
  
• Grade Assessment
  
• Required Background
  
• Reference Books
  
• Book Sources
  
• Class Notes

• Other Important Links

Office Hours

• Dr. Irwin King
  • Monday 2:00 pm - 3:00 pm
  • Tuesday 10:00 am - 11:00 am
  • By appointment

Lecture Hours

1. M9 Monday 4:30 pm - 5:15 pm, KHB G1
2. W3-4 Wednesday 10:30 pm - 12:15 pm, KHB G1

Note: This class will be taught in English. Homework assignments and examinations will be conducted in English.

Tutorial Hours

1. Thu. 12:30 pm - 1:15 pm, SHB 507
2. Fri. 10:30 am - 11:15 am, SHB 507

TAs and Tutorial Sessions

1. Mr. Hu Qixian qxhu@cse.cuhk.edu.hk
2. Mr. Cheung Shing-kwong skcheung@cse.cuhk.edu.hk

Syllabus

1. Week 1 - Introduction to the course
2. Week 2 - Analysis of Algorithms (HW #1)
3. Week 3 - Arrays, Link Lists, Stacks and Queues I
4. Week 4 - Arrays, Link Lists, Stacks and Queues II
5. Week 5 - Searching I (HW #2)
6. Week 6 - Trees, Searching II
7. Week 7 - Sorting I (Midterm)
8. Week 8 - Sorting II (HW #3)
9. Week 9 - Graphs I
10. Week 10 - Graphs II (HW #4)
11. Week 11 - Graphs III
12. Week 12 - Misc.

Homework Assignments

   Assignment         Topic            Issue Date      Due Date
==================================================================
      1      Analysis of Algorithm     Week 2          Week 4
      2      Arrays, link list, stacks & queues 
                                       Week 5          Week 7
      3      Searching & Sorting       Week 8          Week 10
      4      Trees & Graphs            Week 10         Week 12

Grade Assessment

1. 4 Assignments (7.5% each)
   • Written assignment
   • Programming assignment
   • Optional in-class quiz
2. Midterm (20%)
3. Final examination (50%)

Required Background

Pre-requisites

• Computer Organization
• Operating System \& Programming Environment: Unix systems, C, or Pascal

Reference Books

1. Data Structures and Algorithm Analysis in C, Second Edition by Mark Allen Weiss, The Benjamin/Cummings Publishing Company, Inc., 1997
2. Data Structures and Program Design in C by Robert L. Kruse, Bruce P. Leung, and Clovis L. Tondo, Prentice Hall, Englewood Cliffs, NJ, 1991.

Other Books

• Data Structures and AlgorithmsAlfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Addison Wesley Publisher, 1983.

Book Sources

• Academic & Professional Book Centre, 1H Cheong Ming Bldg., 80-86 Argyle St., Kowloon, 2398-2191, 2391-7430 (fax)
• Caves Books (H. K.), 4B Ferry St., G/F., Yaumatei, Kowloon, 2780-0987, 2771-2298
• Man Yuen Book Company, 45 Parkes street, Jordan Road, Kowloon, Hong Kong, 2366-0594
  Not very large, Asian edition books, fair price, wide range, some 10% discount.
• Swindon Book Co. Ltd, 13-15 Lock Road, Tsim Sha Tsiu, Kowloon, 2366-8001
  One of the largest book stores in Hong Kong, exchange rate is not favorable.
• Hongkong Book Centre, 522-7064
  A branch of the Swindon book shop
• Leed & Wood Co. Ltd., 2/F Shop D2A Star House, 3 Salisbury Road, Kowloon.
  A very good store for books of application software only. It is not a good store for Computer Science. Some of the books are useful. The price is a bit high.

Class Notes

1. Class notes will be reserved in the central library.
2. An electronic version (without figures) is available at http://137.189.91.72/csc2520.html
3. It is highly recommended that you take notes in the class. Please do not depend solely on the reserved notes.

Other Important Links

1. CUHK Registration
   
2. CUHK Almanac