CS3334Data Structures

What you will study

Course overview

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.

Official PDF, page 2 · Abstract

Course content

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, B-trees. Game Trees. Hash tables. Disjoint sets. Graphs. Syllabus: • Program correctness and complexities Techniques for proving program correctness, e.g., loop invariant and induction. Asymptotic notations for program complexities. Summation and recurrence formulas. Complexities of common programming constructs, e.g., loops and recursive programs. Average and worst case analysis. • Sorting algorithms Selected sorting algorithms, such as merge sort, heap sort, quicksort, bucket sort, radix sort, as examples to illustrate the previous concepts and analysis techniques. Algorithms for order statistics. • Review of abstract data types Principles of abstract data types. Examples: stacks, queues, heaps. • Search trees Binary search trees. Balanced search trees: AVL trees, splay trees, red-black trees, B-trees. • Game trees Minimax Rules. Alpha-Beta Pruning. Reducing searching depth. • Hash tables Hash functions. Collision resolution. Rehashing • Disjoint Set Disjoint set operations. Path compression. Ackermann’s function. • Graphs Adjacency Matrix, Depth First Search, Breadth First Search • Selected advanced topics in Data Structures

Official PDF, page 5 · Keyword Syllabus

Intended learning outcomes

View official learning outcomes and conditions

CILOs                                             Weighting (if DEC-A1          DEC-A2            DEC-A3
                                                                  app.)
1               Implement common data structures and                                            x
                algorithms.
2               Analyse efficiency and correctness of algorithms                                  x
                using mathematical techniques.
3               Evaluate and compare similar data structures                        x           x
                and algorithms.
4               Design and apply appropriate data structures to                     x           x
                solve problems.

Official PDF, page 2 · Course Intended Learning Outcomes (CILOs)

Before you take this course

Check prerequisites, precursors and corequisites separately, together with equivalence and exclusion conditions. “and” means conditions must be met together; “or” marks alternatives. Read combined conditions in the groupings shown in the original text below.

Prerequisites

CS2310 Computer Programming or CS2311 Computer Programming or CS2312 Problem Solving and Programming or equivalent

Official PDF, page 1 · Prerequisites

Precursors

Nil

Official PDF, page 1 · Precursors

Corequisites

This edition of the official syllabus does not state this item.

Additional course requirements

This edition of the official syllabus does not state this item.

Equivalent courses and conditions

Nil

Official PDF, page 1 · Equivalent Courses

Exclusive courses and conditions

CS2334 Data Structures for Data Science

Official PDF, page 1 · Exclusive Courses

Assessment and passing the course

Assessment

Continuous Assessment (%): 40; Examination (%): 60; Examination Duration (Hours): 2

View the original assessment table and instructions

ATs           CILO No.        Weighting (%)   Remarks ("-" for    Allow Use of
                                                                    nil entry)          GenAI?
1                     Assignments   1, 2, 3, 4      25              Students are         Yes
                                                                    required to work
                                                                    on assignments at
                                                                    least once every
                                                                    four weeks.
                                                                    1. Students may
                                                                    use GenAI tools
                                                                    to assist with
                                                                    understanding
                                                                    concepts or
                                                                    generating ideas,
                                                                    but all submissions
                                                                    must reflect their
                                                                    own understanding
                                                                    and effort. Directly
                                                                    copying and
                                                                    pasting answers
                                                                    generated by
                                                                    GenAI into
                                                                    assignments is
                                                                    strictly prohibited.
                                                                    2. Uploading
                                                                    entire assignment
                                                                    questions, datasets,
                                                                    or other course
                                                                    materials directly
                                                                    to GenAI tools to
                                                                    obtain answers is
                                                                    not allowed.
                                                                    3. If significant
                                                                    assistance is
                                                                    obtained from
                                                                    GenAI tools,
                                                                    students must
                                                                    clearly document
                                                                    the nature and
                                                                    scope of its use in
                                                                    their submissions.
2                     Quiz          1, 2, 3, 4      15              -                   No

Official PDF, page 3 · Continuous Assessment (%),Examination (%),Examination Duration (Hours)

Passing requirements

Minimum Examination Passing Requirement (%): 30 Additional Information for ATs: For a student to pass the course, at least 40% of the maximum mark for the continuous assessment and 30% of the maximum mark for the examination must be obtained.

Official PDF, page 4 · Minimum Examination Passing Requirement (%),Additional Information for ATs