UNIVERSITY OF THE WITWATERSRAND			Tel.:  011 717 6177
Department of Computer Science			Fax.:  011 339 3513
Dr. Yinong Chen	email: 				yinong@cs.wits.ac.za

Computer Science Higher Diploma 2000

Data and Data Structures

Yinong Chen

Overview

The Higher Diploma Data and Data Structures course is designed to build your background to the point where you are ready for Applications of Algorithms, part of Computer Science II. HDip-DDS introduces you to major components of computer systems, and programming methods. Areas covered are designed to give you an appreciation of issues behind the design of programs: algorithms and data structures, particularly as implemented in an object-oriented language. To keep examples simple, Java is used. The emphasis in HDip-DDS is on data structures, especially use of an object-oriented class library, Java's Collections.

Aims

Material covered is designed to give you a basic understanding of

• programs
• virtual machines and why we think of computers as layers of abstract machines
• object-oriented concepts
• algorithm and data structure analysis
• data structures: alternatives and choices

Objectives

By the end of the course you should understand general issues in program design and performance evaluation, particularly to:

• be able to do elementary algorithm and data structure analysis
• be able to work with classes and objects
• be able to use a programming environment including compiler, linker and debugger
• understand issues in choosing between data structures, algorithms and object-oriented components from a library, including:
• time complexity
• space complexity
• trading time for space
• reuse versus coding from scratch
• issues in selecting an appropriate data structure from a library
• design issues for data structures
• translating an algorithm either to code or to selected classes or objects from a library

Structure

Although there is only one tutorial per week, you are encouraged to use the time effectively, especially in the first 2 weeks when you will not be doing other courses. The course has 6 contact sessions per week for the first 3 weeks followed by 4 contact sessions for each of the remaining 3 weeks.

Assignments and Tests

Assignments consist of labs and tutorials. Assessment is in the form of tests after specific objectives are achieved in the labs and tutorials. You are qualified to write tests only if you have completed your assignemnts.

Consultation Time (office SH1016)

Two hours consultation time per week has been reserved for the course, that is

Outside this time period you are also welcome to see me, and I shall try to help you if I am free.

Mark Breakdown

The mark breakdown is as follows:

• class work -- 40% broken down as follows:

• exam: remaining 60%

Prescribed Book and Notes

Notes are provided, but there is no prescribed book. Java information is provided in the lab, but you can look up Java books in the library and bookshops. You may also want to look at books referred to in the notes as an introduction to later courses.

Acknowledge

The outline is based on the outline prepared by Philip Machanick in the framework of the course curriculum designed by the Department of Computer Science.

This document is available at

http://www.cs.wits.ac.za/~yinong/teaching/hdip/dds_outline.html