Universidad Carlos III de Madrid

Define the concept of tree (Bloom 1*)

Define the components of a tree: node, edge (Bloom 1)

Define the possible relations between nodes: ancestors, descendants, parent, child, sibling (Bloom 1)

Differentiate the types of nodes: internal and external, root, leaves (Bloom 1)

Define the properties of a tree: height, width, size (Bloom 1*)

Define the concept of binary search tree (Bloom 1*)

Define the concept of balanced tree (Bloom 1)

Define the concept of binary heap (Bloom 1*)

Give examples of data structures suitable to be modeled with trees. (Bloom 2)

Use a tree for representing a given information which can be interpreted hierarchically (e.g. a mathematical formula, a grammatical sentence, a family tree, etc.) (Bloom 2*)

Calculate the height of a given tree (Bloom 2)

Given a binary search tree, draw the resultant tree after applying a set of insertion operations. (Bloom 2)

Describe the actions done by the binary search algorithm in order to retrieve a given element (Bloom 2*)

Explain how an element is inserted in a (non balanced) binary search tree (Bloom 2*)

Given the code of a method working with a tree, identify its effect when applied with a certain set of values (known the initial state of the tree and the input parameters of the method). (Bloom 2*)

Implement the algorithm for calculating the height of a tree. (Bloom 3)

Implement the algorithm for determining the number of nodes in a tree. (Bloom 3)

Implement an algorithm which implies traversing a generic tree in preorder (e.g. printing the content stored in every node). (Bloom 3)

Implement an algorithm which implies traversing a generic tree in postorder (e.g. printing the content stored in every node). (Bloom 3)

Implement an algorithm which implies traversing a binary tree in inorder (e.g. printing the content of every node). (Bloom 3)

Implement the insertion algorithm for a (non-balanced) binary search tree. (Bloom 3)

Implement the binary search algorithm for a binary search tree. (Bloom 3)

Implement a program which uses a tree for storing information which can be interpreted hierarchically (e.g. a mathematical formula, a grammatical sentence, a family tree, etc.). (Bloom 3)

Implement the insertion algorithm for a binary heap. (Bloom 3)

Implement the deletion algorithm for a binary heap. (Bloom 3)

Given two sequences of (non-balanced) insertion operations, determine which of the two resulting binary search trees will be more efficient in general. (Bloom 4)

Identify the tree as the rightest data structure for modelling the information in problems involving data organized according to some hierarchy. (Bloom 4)

Resolve simple problems involving hierarchically organized data, including: selection of a tree as the rightest data structure for modelling the information, definition of the data structure according to one of the explained choices, and implementation of processing algorithms which work with such data structure (insertion, search, determining basic characteristics such as the height). (Bloom 5)

Compare and justify the adecuacy of different implementations in function of the characteristics of the information to be modelled (e.g. node-based implementation vs. array-based implementation for heaps). (Bloom 6)