CSC2100B

Data Structures

Spring 2006

 Lecture Date

Time

Venue

 Monday

M7, M8 (2:30 pm - 4:15 pm)

 SC L4

 Tuesday

T2 (9:30 pm - 10:15 am)

 ERB LT

 Tutorial Date

Time

Venue

 Tuesday

T10

LSB LT2

 Thursday

H9

SC LG23

The Golden Rule of CSC2100B: No member of the CSC2100B community shall take unfair advantage of any other member of the CSC2100B community.

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

Latest News

[ Course Description | Personnel | Syllabus | Examination Schedule |
Grade Assessment | Required Background | Reference Books | Book Sources | Frequently Asked Questions (FAQ) | Resources ]

Course Description

The concept of abstract data types and the advantages of data abstraction are introduced. Various commonly used abstract data types including vector, list, stack, queue, tree, and set and their implementations using different data structures (array, pointer based structures, linked list, 2-3 tree, B-tree, etc.) will be discussed. Sample applications such as searching, sorting, etc. will also be used to illustrate the use of data abstraction in computer programming. Analysis of the performance of searching and sorting algorithms. Application of data structure pinciples.

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

Personnel

Lecturer Tutor 1 Tutor 2

 Tutor 3
Tutor 4
Tutor 5
Name
Patrick Lau
Xiang Peng
WeiXiong Rao
    
Email
tplau@cse.cuhk.edu.hk
xpeng@cse.cuhk.edu.hk
 wxrao@cse.cuhk.edu.hk
    
Office
SHB 908
SHB 1026
SHB 1013
   
Telephone
x8398
x8430
 
    
Office Hour(s)
  1. Monday 10:30 am - 11:30 am
  2. Tuesday 10:30 am - 11:30 am
W4, W7
M3, F6
TBA
TBA
TBA

Syllabus

The pdf files are created in Acrobat 4.0. Please obtain the correct version of the Acrobat Reader from Adobe.

Week

Date

Topics

Tutorials

[ Homepage ]

Homework & Events

Score Page [ inside CSE (most updated) | outside CSE ]
[Submission Guidelines]

Resources
1 9/1, 10/1
  1. Introduction (2004/1/5) [ b&w pdf | color pdf ]
  1. The C language.
  
2 16/1, 17/1
  1. Algorithm Analysis (2003/1/6) [ b&w pdf | color pdf ]
    1. ACM'97 World Finals Problem Set--Jill Rides Again (2003/1/6) [ pdf ]
  1. How to handle file I/O.

Reading Assignments

  • Read Chapter 1 and 2.
3 23/1, 24/1
  1. List, Stacks, and Queues (2003/1/13) [ b&w pdf | color pdf ]
  2. Recurrence (2003/1/20) [ b&w pdf | color pdf ]
  1. Recurrence examples.

Homework Assignments

  • HW#1 (version 1.04): (06/01/26) There are two parts to the assignment--written and programming.
  • Written Assignment
    • 1.1 (2) and (9); 1.2 (1) and (4); 1.3 (3) and (4); 1.4; 1.5 (4) and (6); 1.8.
    • The written assignment is due on or before 6:00 pm, Friday, February 10, 2006.
  • Programming Assignment
    • The programming assignment is 1.9 and 1.10. A total of 2 programming assignment problems.
    • The programming assignment is due on or before 11:59 pm, Friday, February 10, 2006.

Reading Assignments

  • Read Chapter 3.
4 30/1, 31/1
  1. Chinese New Year Holiday
HAVE A VERY HAPPY CHINESE LUNAR NEW YEAR!
5 6/2, 7/2
  1. Tree Data Structures and Algorithms (2003/1/27) [ b&w pdf | color pdf ]

Reading Assignments

  • Read Chapter 4.
6 13/2, 14/2
  1. Tree Data Structures and Algorithms

 

 
7 20/2, 21/2
  1. Hash Functions (2003/2/24) [ b&w pdf | color pdf ]

 

Homework Assignments

  • HW#2 (version 1.04): (06/02/21) There are two parts to the assignment--written and programming.
  • Written Assignment
    • 3.1 (4); 3.2 (4); 3.3 (4); 3.6 (4); 3.7; 3.10; 3.11.
    • The written assignment is due on or before 6:00 pm, Friday March 3, 2006.
  • Programming Assignment
    • The programming assignment is 2.2, 2.5 and 3.21. A total of 3 programming assignment problems.
    • The programming assignment is due on or before 11:59 pm, Monday March 6, 2006.

Reading Assignments

  • Read Chapter 5.
8 27/2, 28/2
  1. Hash Functions
  2. Midterm course evaluation
  • Hash function.

Reading Assignments

  • Read Chapter 6.
9 6/3, 7/3
  1. Heaps (2004/2/23) [ b&w pdf | color pdf ]
  2. Sorting Algorithms (2003/3/10)[ b&w pdf | color pdf ]
    1. quicksort.ppt
  • Heaps function.

Homework Assignments

  • HW#3 (version 1.04): (06/03/06)There are two parts to the assignment--written and programming.
  • Written Assignment
    • 4.1; 4.4; 4.5; 4.10, 4.14, 5.1, 5.2, 5.5, 5.6
    • The assignment is due on or before 6:00 pm, Thursday March 16, 2006.

Reading Assignments

  • Read Chapter 7.
10 13/3, 14/3
  1. Sorting Algorithms
  
11 20/3, 21/3
  • Midterm Examination (Written) on Thursday, 06/03/23 from 7:30 pm to 9:30 pm, LSB LT1 and LT4.
    • No calculator is needed.
    • Closed book and closed notes.
    • Includes HW#1 and HW#2.
  1. Sorting Algorithms

 

Homework Assignments

  • HW#4 (version 1.04): (06/03/20) There are two parts to the assignment--written and programming.
  • Written Assignment
    • 6.1; 6.2; 6.3; 6.4; 6.6.2. A total of 5 written assignment problems.
    • The assignment is due on or before 6:00 pm, Monday, April 3, 2006.
  • Programming Assignment
    • The programming assignment is 6.10. A total of 1 programming assignment problem.
    • The programming assignment is due on or before 11:59 pm, Wednesday, April 5, 2006.
12 27/3, 28/3
  1. Graph Data Structures and Algorithms (2003/4/8)[ b&w pdf | color pdf ]

Optional Assignment

  • HW#4.5 (version 1.04): (06/03/29) There are one part to the assignment--programming.
  • Programming Assignment
    • The programming assignment is 3.25. A total of 1 programming assignment problem.
    • The programming assignment is due on or before 11:59 pm, Friday, April 7, 2006.

Reading Assignments

  • Read Chapter 8.
13 3/4, 4/4
  1. Graph Data Structures and Algorithms
  • Midterm Examination (Programming) on Saturday, 06/04/08, 10:30 am - 11:00 am for testing, 11:00 am to 2:00 pm midterm, PC Lab (Room 924).

Homework Assignments

  • HW#5 (version 1.04): (06/03/29) There are two parts to the assignment--written and programming.
  • Written Assignment
    • 7.1; 7.3; 7.4; 7.5; 7.7. A total of 5 written assignment problems.
    • The assignment is due on or before 5:00 pm, Tuesday, April 18, 2006.
  • Programming Assignment
    • The programming assignment is 7.8 (c). A total of 1 programming assignment problem.
    • The programming assignment is due on or before 11:59 pm, Tuesday, April 18, 2006.
14 10/4, 11/4
  • ACM ICPC World Finals, San Antonio, USA
  • Check out the exciting contest and other related information from the 2006 ACM ICPC World Finals site here.
  1. No class this week.
      
15 17/4, 18/4
  1. Course summary and final examination pointers (2003/4/23) [ b&w pdf | color pdf ]
    

 

  

Examination Schedule

Date and Time Venue
Midterm Examination
  1. Saturday, 06/04/08
  • PC Lab Room 924

 
Final Examination Examination Timetable for CSC examinations
TBA

Grade Assessment
  1. Assignments (25%)
  2. Midterms (10 + 15 = 25%)
  3. Final Examination (50%)
  4. Extra Credit (There is no penalty for not doing the extra credit problems. Extra credit will only help you in borderline cases.)

Note: One must solve at least one problems in either of the midterms to pass the course.

Required Background

Pre-requisites

Reference Books

  1. Data Structures and Algorithm Analysis in C, Mark Allen Weiss, Addison Wesley, second edition, 1997.
  2. Data Structures and Algorithm Analysis in C++, Mark Allen Weiss, Addison Wesley, second edition, 1999.

Other Books

  1. Data Structures and Algorithms, Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Addison Wesley, 1983.
  2. Introduction to Algorithms, Thoas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press, 1990.
  3. Data Structures and Their Algorithms, Harry R. Lewis and Larry Denenberg, HarperCollins Publisher, 1991.
  4. Data Structures Using C and C++, Aaron M. Tenenbaum, Yedidyah Langsam, and Moshe J. Augenstein, Prentice Hall, 1995.

Book Sources

Frequently Asked Questions (FAQ)

  1. Q: What is departmental guideline for plagiarism?
    A:     If a student is found plagiarizing, his/her case will be reported to the Department Discipline Committee. If the case is proven after deliberation, the student will automatically fail the course in which he/she committed plagiarism. The definition of plagiarism includes copying of the whole or parts of written assignments, programming exercises, reports, quiz papers, mid-term examinations. The penalty will apply to both the one who copies the work and the one whose work is being copied, unless the latter can prove his/her work has been copied unwittingly. Furthermore, inclusion of others' works or results without citation in assignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caught plagiarizing during tests or examinations will be reported to the Faculty Office and appropriate disciplinary authorities for further action, in addition to failing the course.
  2. Q: What is ACM ICPC?
    A:     Association of Computer Machinery International Collegiate Programming Contest. Teams from CUHK have done quite well in the previous years. More information on the CSE's programming team can be found at http://www.cse.cuhk.edu.hk/~acmprog.
  3. Q: What are some of the common mistakes made in online and real-time contest?
    A: There are a few common mistakes. Please check out this site for more information.

Resources

  1. Learn C/C++ Today
  2. Addison Wesley's Computer and Engineering Book Catalog and Programming Codes
  3. Matlab Homepage
    This site is the creator of Matlab. You will be able to obtain much Matlab-related information.
  4. CSE's ACM Programming Contest Homepage
  5. C Programming
  6. Arrays and Pointers
    pweb.netcom.com/~tjensen/ptr/pointers.htm
  7. The 'gcc' compiler gnu.ist.utl.pt/software/gcc/onlinedocs/gcc_2.html#SEC2
  8. The 'gdb' debugger www.cslab.vt.edu/manuals/gdb/gdb_toc.html
  9. The 'make' utility mlo-stealth.mtn.hawaii.gov/qnxman/make.html
  10. Programming C under Linux, provided by RedHat www.redhat.com/developer/whitepapers/intro_dev/
  11. Sorting Algorithm Animation Demo http://www.scs.carleton.ca/~morin/misc/sortalg/
  12. Analysis of Algorithms Home Page http://pauillac.inria.fr/algo/AofA/
  13. Mathematical Programming Glossary http://www.cudenver.edu/~hgreenbe/glossary/intro.html
  14. Algorithm Anaimation Links http://www.cs.oswego.edu/~birgit/html/diplom/links.html
  15. The Pickle Story: http://www.alistapart.com/articles/pickle/

Last modified on Tue, 4 April, 2006 6:41 PM . Please send your comments and suggestions to Irwin King.