New Course Proposal - CMPT 225-3 Data Structures and Programming

G. Baker, B. Bart, T. Dixon, Q. Gu, A. Lavergne, D. Mitchell, Syllabus Working Group, School of Computing Science

Revision A - January 18, 2004

Calendar Information

Course Number: CMPT 225

Course Title: Data Structures and Programming

Credit Hours: 3 Vector: 3-0-0

Course Description

Introduction to a variety of practical and important data structures and methods for implementation and for experimental and analytical evaluation. Topics include: stacks, queues and lists; search trees; hash tables and algorithms; efficient sorting; object-oriented programming; time and space efficiency analysis; and experimental evaluation.

Prerequisite: CMPT 101, 104, 125, 126, or 128. MACM 101.

Recommended: None.

Corequisite: None.

Special Instructions: None.

Course(s) to be dropped if this course is approved:

CMPT 101-4 and CMPT 201-4 are proposed to be replaced by the new three-course sequence CMPT 120-3, CMPT 125-3, CMPT 225-3.

Rationale for Introduction of this Course

This is a direct replacement for CMPT 201-4, building on the new CMPT 120/125 sequence that replaces CMPT 101-4.

Will this be a required or elective course in the curriculum; probable enrolment when offered?

Required; enrolment estimated at 600 per year.

Scheduling and Registration Information

Indicate Semester and Year this course would be first offered and planned frequency of offering thereafter.

2005-1 and every semester thereafter.

Which of your present CFL faculty have the expertise to offer this course? Will the course be taught by sessional or limited term faculty?

Almost all present faculty could teach this course. Sessionals or limited term faculty may on occasion teach a parallel section to that taught by a CFL faculty member serving as course champion.

Are there any proposed student fees associated with this course other than tuition fees?

No.

Is this course considered a `duplicate' of any current or prior course under the University's duplicate course policy? Specify, as appropriate.

Students with credit for CMPT 201 may not take this course for further credit.

Resource Implications

Note: Senate has approved (S.93-11) that no new course should be approved by Senate until funding has been committed for necessary library materials. Each new course proposal must be accompanied by a library report and, if appropriate, confirmation that funding arrangements have been addressed.

Provide details on how existing instructional resources will be redistributed to accommodate this new course. For instance, will another course be eliminated or will the frequency of offering of other courses be reduced; are there changes in pedagogical style or class sizes that allow for this additional course offering.

This course will use instructional resources currently used for CMPT 201 as well as new resources made available through the Double the Opportunity (DTO) program.

Does the course require specialized space or equipment not readily available in the department or university, and if so, how will these resources be provided?

No.

Does this course require computing resources (e.g. hardware, software, network wiring, use of computer laboratory space) and if so, describe how they will be provided.

This course will use instructional resources currently used for CMPT 201 as well as new resources made available through the Double the Opportunity (DTO) program.

Outline of CMPT-225 Syllabus

Data structures: Stacks, queues, decks (formal definition of methods, implementation options), trees, hash tables, head and priority queues.
Recursion: callback stack, transforming recursive to iterative.
Information hiding
Time and memory efficiency
Basic algorithms: paser, tree traversal, binary search tree, quick sort, heap sort
External data storage and sorting
OOP: Applets, swing, polymophism, inheritance, references, operator overloading.
Self-learning: A new OOP langauge, UNIX/LINUX.
Prequisite: CMPT125(CMPT101/104), MACM101.

Sample Course Outline

Unit	Weeks	Computing Science	Algorithms	Programming Language	Lab/Assignment/Examples
1.	1	125 review	125 review, basic ADT	Applets, swing	Fundamental Unix/Linux, C++
2.	2	Information hiding, running time analysis	basic ADTs: stacks, queues, decks. Formally (methods defined, implementation options)	References (for data structs), operator overloading	Fundamental Unix/Linux, C++ Implementation of stacks, queues, in Java and C++, Paser program
4.	3	Recursion concepts: callback stack, transforming recursive -> iterative	Trees: binary, traversals, general trees, BSTs	Java interface	Implementation of trees: binary, traversals, general trees, BSTs, in Java and C++
4.	1	Hash functions	Hash tables and algorithms	GUI	GUI Implementation of hash tables in Java and C++
5.	2	Heaps, priority queues	Heaps, priority queues	Polymophism, inheritance	Implementation and applications of heaps and priority queues, linking object code.
6.	2	Time and memory efficiency	Sorting: quicksort, heapsort, mergesort, in-place sorting	Polymophism, inheritance	Implementation of sorting algorithms, project.
7.	1	External storage and sorting	External storage and sorting		Implementation of external sorting, project.