Bev Facey Community High

CSE 3340: Dynamic Data Structures 3

Students enhance their knowledge of abstract data types that utilize dynamic data structures by expanding their repertoire to include hierarchically linked data structures. Students study general trees, binary trees, binary search trees and heaps. They learn how to use binary search trees to implement sorted sets, sorted maps and heaps to implement priority queues.

• Prerequisite: CSE3330: Dynamic Data Structures 2

Theory

Analyze and represent the nature, structure and utility of tree data structures

1. explain and represent the nature and mechanics of tree data structures including:
   • the role of tree data structures as containers for abstract data types
   • the abstract data type each tree data structure is best suited to
   • the logical structure of tree data structures; e.g., general trees, binary trees, binary search trees, heaps
2. explain and represent the standard operators associated with tree data structures including:
   • create the data structure
   • copy the data structure; e.g., cloning and deep copy
   • preorder, in-order, post-order and level order traversals
   • search, insert, remove and modify data elements
   • list data elements accumulated by a tree transversal
   • list the pop and heapify operation for heaps
   • delete the data structure
3. explain the advantages and disadvantages of tree data structures with consideration to their complexity

Practical

Create and/or modify algorithms that use various tree data structures to solve problems

• demonstrate the use of appropriate general design techniques to draft algorithms that use tree data structures
• analyze and decompose the problem into appropriate subsections using the decomposition techniques appropriate for the chosen design approach
• evaluate subsections and identify any that may require tree data structures, based on the nature of the data to be processed and type of processing operations
• identify which tree data structures are appropriate or required to manipulate data
• sequence the various subsections appropriately
• test and modify the developing algorithm with appropriate data using a “fail-on-paper” process

Create and/or modify programs based on appropriate algorithms that use various tree data structures

• convert algorithms calling for tree data structures into programs that reflect the algorithm’s design
• use original (user-created) or pre-existing tree data structures appropriate to the data being manipulated
• utilize the appropriate operators, methods, functions or procedures required to use tree data structures
• use internal and external documentation

Compare program operation and outcomes with the intent of the algorithm and modify, as required

• use appropriate error-trapping mechanisms built into the programming environment, as well as programmer-directed error-trapping techniques, to eliminate logic errors and debug the program
• compare the congruency between the outcomes of the debugged program and the original intent of the algorithm and modify both, as required

Competencies and Skills

You will also be evaluated on your basic competencies such as your ability to:

• communicate
• manage information
• use numbers
• think and solve problems
• demonstrate positive attitudes and behaviours
• be responsible
• be adaptable
• learn continuously
• work safely
• work with others
• participate in projects and tasks

This site is open source. Improve this page.