Department of Electrical Engineering

CS243: Data Structures and Algorithms

Course Instructor: Momina Azam Dated: 22nd Dec, 2019

Lab Engineer: Tabish Manzoor Semester: 3rd

Session: 2018-2022 Batch: BSEE2018

Lab Project. Implementing and using TRIEs

Lab Report
Name Roll No Viva Marks/5 Total Marks/45
Marks/40

IBTIHAJ SYED BSEE-18026

Checked on: _______________________________

Signature: __________________________________
1.1 Objective
The goal of this handout is to observe and implement a TRIEs Structure

1.2 Equipment and Component

Component Description Value Quantity
Computer Available in lab 1

1.3 Conduct of Lab

1. Students are required to perform this experiment individually.
2. In case the lab experiment is not understood, the students are advised to seek help from the course
instructor, lab engineers, assigned teaching assistants (TA) and lab attendants.

1.4 Theory and Background

In computer science, a trie, also called digital tree or prefix tree, is a kind of search tree—an ordered
tree data structure used to store a dynamic set or associative array where the keys are usually strings.

You are expected to build a dictionary in a TRIE. Every TRIE node will hold pointers to some
letters of the english alphabet and a flag that says whether that node stores a valid english word or
not.

Your TRIE node structure should have the following members

1. An array of TRIE node pointers. In order the pointers should point to the following
characters A B C I E F H O R S T only.
2. A flag that says if the node holds a valid english word
3. A char array that stores this english word that ends in that node.

Your dictionary should store the following words:

 artist
 art
 artificial
 effort
 effect
 torch
 barret

Implementation of AddWord Function : This function will be used to add a new word to
the TRIE.
Input: Word to be added.
AddWord: This function should add a word to the TRIE. One node for every letter of the word (if
no nodes for any letters exist already).
Assumption: You can expect that all words added will be formed from the letters in your TRIE
node list. ()

.
implementation of PrintWordSuggestions Function : This function should take a sub-string as
an argument and print a list of valid words from the dictionary that start with that sub-string.
For Example if the user types ‘to’ the function PrintWordSuggestions when called with ‘to’ should
print a list
toss
torch
torchere

Please note that the list of words are printed in order of word sizes with the smallest
word first.

Your application should take input from the user in a dialogue box (which can be a simple
rectangle)
As the user is typing the string you should display a list of correct english word as suggestions for
the same sub-string.

Q1. Code Review and presentation [30 Mark]

Q2. Please write a small report on presenting and explaining your logic in the code [10 Mark]

The logic used in this code is the same like the logic in linked list but in this case we have multiple links

of each alphabet.

For example we have a word "Apple". The logic used is that the code will find the ascii value of the

alphabet A and will give us an index on which we will add that A, the alphabet will now have

multiple links. Now we will add p into the multiple links of A using the same method of finding

index and creating multiple links, this process will be repeated for all the alphabets of the word.
Lab Rubrics: CS243 Data Structures and Algorithms Lab Project
Student Name: IBTIHAJ SYED Registration #: BSEE-180 26 Batch: EE 2018

Method: Lab reports and instructor observation during Lab sessions

Outcome Assessed:
a. Ability to conduct experiments, as well as to analyze and interpret Problem Statement (P).
b. Ability to function on multi-disciplinary teams (A).
c. Ability to use the techniques, skills, and modern programing tools necessary for
programing practice (P).

Does not meet

Exceeds Meets expectation expectation
Performance Marks
expectation
(3-2) (1)
(5-4)

1. Code Format Code Format is good, Code Format is good but Code is not
the names of the the variables names are understandable. No
[a, b]
variables and functions not understandable. classed were
are reasonable. The
not used
code has been done in
classes and objects

2. Optimized Logic The logic that was The code is working and The code output is
and understanding designed is good and giving expected output but wrong and the code is
the problem [a , c] optimized. and all the the code logic is not throwing exceptions
aspects are covered in optimized and the code
all the problems does not cover all aspects
of the problems

Total

Lab Engineer: Faculty:

Name: Tabish Manzoor Name: Momina Azam

Signature: Signature:
Date: Date:

wwwwwwwwwwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwwww
wwwwwwwwwww wwww
wwwwwwwwwww wwwwwwwwwwwwwwwwwww
wwww wwwwwwwwwwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwwww
w
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwwww
w
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwww
wwwwwwwwwww
w wwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwwwwwwwwww
wwwwwwwwwww
wwwwwwwwwww wwwwwwwwwwwwwwwwwww

wwwwwwwwwww wwwwwwwwwwwwwwwwwww

wwwwwwwwwww wwwwwwwwwwwwwwwwww

w wwwwwwwwwwwwwwwwwww

wwwwwwwwwww wwwwwwwwwwwwwwwwwww

wwwwwwwwwww wwwwwwwwwwwwwwwwww

wwwwwwwwwww