WRITING ASSIGNMENT IV
ASSIGNMENT IV REPORT
SUBJECT: USE OF TREES AND GRAPHS IN PROBLEM SOLVING. ALGORITHMIC TIME COMPLEXITY.
In the following, you will be presented with different problems.
1) Perform the coding in a development IDE corresponding to them in the C++ language using the Object Oriented Paradigm (OOP).
2) Calculate the algorithmic complexity of each function of the problem and in general.
EXERCISES USING TREES
Yellow Teams Blue Teams Orange Teams
Product Tree by Category Family Tree Prime Number Tree
Develop a binary product tree where each node Create a Person class that represents a family up to the Construct an ABB with the first 15 prime numbers.
represents a product with code, name and category. grandparent level. Implement a tree that allows inserting Implement functions to:
Insert products and display them in alphabetical order family relationships and traversing it in preorder to a) Display the primes in inorder.
by name. display the family tree. b) Calculate the number of leaf nodes.
a) Also implement the search by category. Determine the height of the tree.
Student Grade Tree Decision Tree - Medical Diagnosis Word Tree for Search Engine
Each node contains an enrollment, name and average. Constructs a binary tree that simulates basic diagnostic Implements an ABB to store keywords. Enable:
The tree must allow: decisions. a) Insert words
a) Insert student Example: b) Suggest words alphabetically (in order)
b) Show students sorted by GPA Do you have a fever? → Yes → Do you have a cough? c) Search for exact matches
c) Show those with GPA over 85 → ... Show how many words there are per level
d) Count how many are at risk (average < 70)
Uses preorder path to print the decision flow.
In addition, it must allow the user to traverse the running
tree, as if answering yes/no.
EXERCISES USING GRAPHS
Yellow Teams Blue Teams Orange Teams
Friends Network Dependent Modules Computer Network
Models a simple social network where each user is a Represents the modules of a system (such as classes Models a computer network as an undirected graph.
node and friendships are undirected edges. Allows: or functions) and their dependencies as a directed Implements:
network. Allows: a) Connection between computers.
a) Add users (vertexes)
b) Add friends a) Insert dependency A → B b) BFS path to detect propagation of an update
c) Show all friends of a user b) Show load order (DFS path)
Calculation of the minimum number of hops between
d) In addition, it must implement BFS path to c) Detect dependency cycles (if they exist).
two nodes (BFS distance).
suggest new friends (friends of friends).
Weighted Cost Network Document Distribution in an Office Network
Recommendation System
Represent the internal document distribution network as
Represents routes between warehouses with Each vertex is a product. An edge indicates that the a graph, where each office is a node and each direct
transportation costs. Implements the network with products were purchased together. Allows: route is an undirected edge.
weights:
a) Aggregate purchase relationships Implements:
a) Insert route with cost b) Suggest products starting from a given one
b) Show possible routes a) Graph creation from user-input office
(BFS at depth 2). connections (adjacency list).
c) Find cheapest route from one node to the others
using Dijkstra (basic version or with b) BFS from the central office (node 0) to simulate
pseudocode) delivery order.
Display the adjacency list and the BFS traversal
result.
Practice the contents of each unit in an Integrated Development Environment (IDE):
❖ Visual Studio: [Link]
❖ Online compiler for C++: [Link]
❖ C++ Dev Compiler: [Link]
Criteria for evaluation:
1) Correct definition of data structures.
2) Implementation of functions using trees and networks.
3) Functional coding of the system in an IDE.
4) Proper use of repetitive structures
4.1) Nested conditionals are applied if the problem requires it.
5) Timely delivery of the project and compliance with the instructions (C++ code; Annexes with the coding and compilation of the program).
Success!
Zoila E. Morales Tabares
Directora de la Escuela de Ingeniería y Tecnología/Agrimensura
Teléfono: (809) 724-0266 Ext.: 430
[Link]