Discrete Structures

COMP S263, Discrete Structures, is adapted from the new OUUK course M263. It is primarily designed for students who intend to specialize in computing. The main aim of the course is to introduce you to some concepts underlying a systematic approach to software. The course contains four blocks of material, each containing four units. In Blocks 1 and 2, we discuss various forms of data (data structures) commonly used in software, such as sequences and trees. These are organized into data types and classes. We introduce a course code, which is a programming language to express instructions in a form suitable for execution by a computer. (The course code is implemented in a software package supplied as part of the course materials, which we refer to as the WorkPad.) The course code is not a specific programming language that you might meet elsewhere, but it does have features that are often found in certain programming languages (such as C++ or Java). It does not by any means have all the features present in such languages, though. Our aim is to deal with principles relating to the use of such languages, rather than with large-scale practical software development.

We emphasize abstraction: the separation of the behaviour of a software element (given as a specification) and code to achieve that behaviour (an implementation of the specification). A few ideas from mathematics are introduced, where they assist in understanding software features.

In Block 3, we introduce some ideas from symbolic logic, which is widely used in the expression of software requirements. We look also at some ideas relating to the structure of databases, and at a case study drawing on these ideas. Block 4 introduces recursion, a powerful tool for approaching certain problems. This final block also provides brief introductions to efficiency, and to methods to prove that an implementation is correct.

COMP S263 is in the Bachelor of Computing or Bachelor of Science in Applied Computing programmes. However, if your intended degree is Bachelor of Science in Computing and Networking, you need to use your free choice credits to study this course. If you do not have or have used up your free choice credits, you also need to consider a course change.

This course forms an excluded combination with its predecessor M261. Students intending to use M261 towards a degree (or a qualification) cannot use this course in the same qualification. There is no recommended prerequisite for this course.

3.1 Hardware

A PC-compatible computer ready for connecting to the Internet is essential. The minimum configuration of the computer is:

• IBM compatible PC with an x86 CPU or equivalent;
• 512 MB RAM;
• a harddisk;
• a CD or DVD drive;
• a sound card with speakers;
• Internet connection.

You need to be familiar with the basic use of a computer including keyboard, mouse, printer and word processing software.

3.2 Software

MS Windows and MS Word are needed. Other software is provided or downloadable from the Internet.

3.3 Internet connection

Access to the Internet is needed and students are recommended to subscribe to an Internet Service Provider.

4.1 Web pages

You should visit the course news page on the Online Learning Environment (http://ole.hkmu.edu.hk) through the Web at least twice a week to see if there is any news. Important notice will be posted on OLE News of this course. Please see the OLE User Guide to learn how to log in and see the news. There will be different types of items to be downloaded from the Web including:

• Assignments (tutor-marked assignments)
• Specimen Examination Paper and Answer

4.2 Printed units

The course is divided into four blocks which are of equal length. Each block, which consists of four printed units, is studied over eight weeks, together with some practical computing work. You are suggested to spend about two weeks on each unit. The 16 units are:

* more difficult unit

Each course unit is divided into sections. Most of the sections are of similar length, although some are shorter than others. An average section should take around two hours to study. Each course unit has a summary and index (for reference purposes and as an aid to revision).

The text includes examples and activities. The examples should be treated as part of the text: just read them when you come to them (and refer to them later if you need to). The activities are for you to attempt, but do not spend a long time on them. If you cannot see how to do an activity, then go on and read the discussion following it, which will show you what was expected. However, you will gain more value from the activities if you at least attempt them before reading the discussion. This will help you to be aware of what you have and have not understood so far, and what to concentrate on when reading the discussion.

Each section gives objectives at the end. These summarize the knowledge and skills that were introduced in the section and on which you may be assessed. There are exercises at the end of each section. These are provided as practice of the objectives of the section. In many cases, the practical computing sessions will provide you with further practice.

Within some units, you will find pieces of text marked out as Asides. The Asides contain discussions included to help you to relate the work in this course to things you may have read elsewhere, or to elucidate subtle points. You will not be assessed on the material in the Asides. We recommend that you read them, as they may help you to resolve some point that is worrying you, but do not spend time trying to understand them if their meaning is not immediately clear.

You will see the code 'M263' instead of 'COMP S263' in the printed materials since we are not allowed to change them.

4.3 Set book

No set book is required.

4.4 CDROM

A CD-ROM containing the software for this course is provided.

4.5 WorkPad

WorkPad is the environment specially designed for writing code of this course. It is in the CD-ROM provided.

4.6 Online Learning Environment (OLE)

We are using OLE, the standard online platform of HKMU. There are many components described in the OLE User Guide. One component of OLE which many students find useful is the Discussion Board. They allow their users to post messages at different times for discussions.

4.7 Email

You can communicate with your tutor or your classmates through Internet email.

You will be allocated a tutor at the beginning of the course to whom you must send your assignments. Your tutor will not only mark them for assessment purposes, but will also use them as a piece of teaching material by pointing out to you how to correct errors, giving further explanation to any points of difficulty, and suggesting alternative or better methods.

5.1 Tutorial

The course materials allow you to study independently. This 'distance teaching' is supplemented by 'face-to-face' teaching at tutorials. You should take along any notes you have made, to remind yourself of points from the course materials which you would like to discuss with your tutor. The dates and venues of your tutorial sessions will be sent to you in a Stop Press.

5.2 Surgery

You can obtain help individually at surgeries. During these sessions a tutor will be available to see students to discuss their own problems and difficulties. This service will be provided on a first-come-first-served basis, although the number of tutors involved will be increased if demand justifies it.

5.3 Telephone tutoring

Apart from handling your assignments, your tutor is also available on the telephone to give you immediate advice and help on any problems with the course. You should feel free to contact your tutor for any academic assistance, although you are asked to be reasonable about the times when you contact your tutor.

5.4 Email

You can also send emails to your tutor for advice. Since email does not require both sides to be present at the same time for discussion, it is a good way to ask questions.

5.5 Discussion group

If there are some questions related to the whole tutorial group, you may like to discuss them with your group-mates/tutor using the discussion group in the OLE.

The final score of the course will depend on the performance of Tutor-marked Assignments (assignments) and a final examination. The weightings of them are listed below:

1. the best three (out of four) assignments: 30%, and
2. the final three-hour written examination: 70%.

The grade of the course depends on the final score. To get a passing grade, both average TMA score and the examination score should not be less than 40. For general information about assessment, please refer to your Student Handbook.

6.1 Assignment

Your will be required to download the soft copy of the assignment questions in PDF (or other format, if applicable) on the Web. Your answers to the assignments should be sent directly to your tutor who will mark them and provide feedback to you. Either a soft copy or a hard copy should be submitted to your tutor. Soft copy should be uploaded to the OLE and hard copy should be sent by post. Each block has an associated assignment.

Each assignment has a cut-off date, which is the date by which your tutor should receive your assignment.  For further details on the late submission of assignments, please refer to the Student Handbook.

Sometimes, despite your best efforts, a program will not run satisfactorily. If this happens, do submit your incomplete program since partial credits can be given for your working steps. It will also enable your tutor to give you better feedback.

6.2 Examination

There will be a three-hour written examination at the end of the course. A Specimen Examination Paper and its answers will be available on the Web so that you will have a good idea of the format of the paper and the type of questions you are likely to be asked.

The course involves some practical computing work. This is an essential aspect of the course, and the assignments will involve some questions that require use of a computer. Overall, you should expect to spend around 15% of your study time working on a computer. The amount of practical work will vary between units, but you should not spend more than a quarter of your study time for any unit on practical computing work.

There is practical computing work associated with many (but not all) of the units. This work is organized into sessions. Each computing session assumes that you have studied up to a certain point in the printed units. However, your study of the printed units does not depend on your practical work. So you can treat the practical work in a variety of ways, depending on what you find convenient.

1. You can do practical work in parallel with your study of the printed units.
2. You can study each session of practical work immediately after completing the relevant section of the unit.
3. You can do all the practical work for a unit after you have completed study of the unit.
4. You can do all the practical work for the block (including any for the assignment) together, when you have finished study of the entire block.

Of these, either option 2 or option 3 is most likely to suit the majority of students, but choose whatever suits you! There is a close relationship between the material covered in the practical computing sessions and the material in the unit texts, so you may find it helpful to study the computing as soon as possible after you have studied the corresponding material in the units. But it is not necessary to do this. You can do the practical work some time later if your circumstances require that.

The practical computing work requires use of the WorkPad. This is a software package that enables instructions written in the course code to be executed on a computer. The WorkPad software is provided on a CD supplied as part of the course materials, which should arrive in your first mailing. Instructions for installing the WorkPad are as follows. Place the M263 CD in the CD-ROM drive, double-click on My Computer then on the CD icon and finally on the file called M263-setup or M263-setup.exe, and then follow the onscreen instructions. You may need to apply updates to installed content. See the readme.txt files under the software-updates folder in the CD-ROM.

You should install the WorkPad software as soon as convenient after you receive the course materials. The first part of assignment 01 involves a question relating to use of the WorkPad. This question asks you to perform a couple of simple tasks to check that you have successfully installed the WorkPad and that it is working correctly.

The material for the practical computing sessions that form part of your study for the course is also on the course CD. These are provided in the form of html documents, which can be read by a Web browser such as Internet Explorer. There is a reference document relating to the use of the WorkPad, which is also provided on the CD. There is a separate printed sheet that provides basic information for quick reference.

There are software files relating to assignments that will vary from year to year. These will be supplied as part of the course materials, and will contain instructions on how to install them. Watch out for these, and make sure that you have the files for the current year installed before you attempt each assignment.

There are no significant differences between COMP S263 and M263 except we choose the best three out of four in the assignments while OUUK uses a 'substitution rule' (ours is more generous).

The course code (COMP S263 vs M263), the course guide (this one vs the OUUK version) and the software platform (OLE vs UK Web site) are some of the minor differences.

Assuming that you have Windows and MS Word installed in your PC, you are recommended to install the course software. You can use the period allocated to 'Preparation and Course Familiarization' for computer/Internet setup and having a first look of the components of the course. There is no specific unit assigned to it.

Then you can start this course by the following steps:

1. Read News on the OLE periodically (to get most up-to-date information about the course)
2. Find the unit to read from the Presentation Schedule and read it (This is the time-table for this course and you should follow it as far as possible).