CS3334

CS3334 Data Structures

Part I

Course Duration: One Semester

Credit Units: 3

Level: B3

Medium of Instruction: English

Pre-requisites:
CS2311 Computer Programming; or
CS2331 Problem Solving & Programming; or
CS2332 Object-Oriented Programming

Pre-cursors: Nil

Equivalent Courses: Nil

Exclusive Courses: Nil

Part II

Course Aims:

This course aims to provide students an appreciation to the fundamentals of computer science. Models and applications of data structures including heaps, search trees, hash tables and disjoint sets are introduced and evaluated. Mathematical tools for analysis of algorithms and data structures are discussed and applied. Students are given the opportunity to develop and implement applications of the data structures and their derivatives.

Course Intended Learning Outcomes (CILOs):
Upon successful completion of this course, students should be able to:

No.	CILOs	Weighting (if applicable)
1.	implement operations of basic data structures;
2.	analyse efficiency of basic data structures;
3.	identify applications of basic data structures;
4.	apply mathematical analysis to similar data structures and algorithms;
5.	apply mathematical techniques to prove correctness of algorithms;
6.	design and evaluate appropriate data structures to solve problems.

Teaching and learning Activities (TLAs):
(Indicative of likely activities and tasks designed to facilitate students' achievement of the CILOs. Final details will be provided to students in their first week of attendance in this course)

Teaching pattern:
Suggested lecture/tutorial/laboratory mix: 2 hrs. lecture; 1 hr. tutorial.

The course will focus on enabling students to understand and apply basic data structures in computer science. Basic characteristics of each data structure will be given in lectures and students are required to identify the steps in implementing the data structures. Mathematical tools to evaluate complexities of algorithms will then be introduced to students. Based on students' thorough understanding of the behaviour of data structures learnt, teacher will demonstrate how to use the tools to evaluate the efficiency of data structures. Students are then required to apply their knowledge on solving a problem.

Based on the course ILOs, the teaching/learning activities of this course may include:

CILO No	TLAs	Hours/week (if applicable)
CILO 1, 2, 5	Exercises – To enable students to get familiarised with characteristics of data structures and mathematical techniques for evaluating algorithm complexity and correctness, a series of small exercises are designed by teacher. Through working on example cases, students follow the algorithms through to recognise the operations of basic data structures and practise on mathematical analysis. (support ILO #1,2,5)
CILO 3	Survey Report – Students are asked to explore printed and web literature and products as example applications of the data structures learnt in the course. They are required to compile a report to share their findings. (support ILO #3)
CILO 2, 4, 6	Programming Project – The project is to provide an opportunity for students to design and evaluate new data structures to solve a problem. It should include algorithm design, proper use of data structures, learning new data structures and programming. Students should apply mathematical analysis to their own solution. (support ILO #2,4,6)

Assessment Tasks/Activities:
(Indicative of likely activities and tasks designed to assess how well the students achieve the CILOs. Final details will be provided to students in their first week of attendance in this course)

The Course ILOs are assessed using the following approach:

CILO No	Type of assessment tasks/activities	Weighting (if applicable)	Remarks
CILO 1	Implement operations of basic data structures. Coursework – Students are required to bring answers of exercises to tutorials for discussions. For algorithm implementation, students show their programs in the Project. Class test/Exam – Questions will include example cases to test students' understanding of the behaviour of data structures.
CILO 2	Analyse efficiency of basic data structures. Coursework – Students are required to demonstrate their understanding in the Project report. Class test – Questions will include example cases to test students' understanding of the mathematical analysis.
CILO 3	Identify applications of basic data structures. Coursework – The quality of the survey report should reflect the students' ability to identify the applications of data sturctures and how much they are aware of the usefulness and importance of data structures.
CILO 4	Apply mathematical analysis to analyse similar data structures and algorithms. Coursework – Students should demonstrate their ability to apply the technique in the Project. Exam – Questions will be set to test how well students can evaluate complexity.
CILO 5	Apply mathematical techniques to prove correctness of algorithms. Exam – Questions will be included to test if students are able to prove correctness of an algorithm.
CILO 6	Design and evaluate appropriate data structures to solve problems. Coursework – In the programming project, the performance of the students can be shown from their design of data structures and their justification. Exam – Questions may be set to test how well students can apply the knowledge and analytical thinking to design and evaluate appropriate data structures to solve a given problem.

Grading of Student Achievement:

Examination duration: 2 hours
Percentage of coursework, examination, etc.: 30% CW; 70% Exam
Grading pattern: Standard (A+AA-…F)
For a student to pass the course, at least 30% of the maximum mark for the examination must be obtained.

Part III

Keyword Syllabus:

Program correctness. Complexities of programs: notation, average and worst case analysis, complexities of common programming constructs. Sorting algorithms: merge sort, heap sort, quicksort, bucket sort. Algorithms for order statistics. Abstract data types: stacks, queues, heaps. Balanced search trees: AVL trees, red-black trees, 2-3 trees, B-trees. Hash tables. Merge-find sets.