Project Data Structure CS240

College of Computing and Informatics

Project
Deadline: Tuesday 02/12/2025 @ 23:59
[Total Mark is 14]
Student Details:

CRN:

Name:
Name:
Name:

ID:
ID:
ID:

Instructions:

• You must submit two separate copies (one Word file and one PDF file) using the Assignment Template on
Blackboard via the allocated folder. These files must not be in compressed format.

• It is your responsibility to check and make sure that you have uploaded both the correct files.
• Zero mark will be given if you try to bypass the SafeAssign (e.g. misspell words, remove spaces between
words, hide characters, use different character sets, convert text into image or languages other than English
or any kind of manipulation).

• Email submission will not be accepted.
• You are advised to make your work clear and well-presented. This includes filling your information on the cover
page.

• You must use this template, failing which will result in zero mark.
• You MUST show all your work, and text must not be converted into an image, unless specified otherwise by
the question.

• Late submission will result in ZERO mark.
• The work should be your own, copying from students or other resources will result in ZERO mark.
• Use Times New Roman font for all your answers.

Restricted – ‫مقيد‬

Description and Instructions

Pg. 01

Description and Instructions
On this project, each group of students will solve a problem to assess their
understanding of data structure. Students will work in groups of 2-3 students
then collect their work in one report to be submitted with the other project
materials.

Project Description
Welcome, zookeepers! You have been “hired” by the prestigious (but poorly
organized) City Zoo. Your mission is to design and implement “ZooKeeper’s
Pathfinder,” a software application that will model the zoo’s operations using
fundamental data structures. The goal is to evaluate your understanding of how
Arrays, ArrayLists, Stacks, Queues, Trees, and Graphs can be applied to solve
real-world problems, and to analyze the efficiency of your solutions. Successfully
completing this project will demonstrate your proficiency in implementing,
utilizing, and analyzing these core concepts.

Project Milestones
The project is divided into five core milestones. You must complete each
milestone sequentially.

Milestone 1: The Zoo Layout (Arrays & ArrayLists)
Objective: Model the physical layout of the zoo.

Restricted – ‫مقيد‬

Description and Instructions

Pg. 02
•

Create a Zone class with properties zoneName (e.g., “African
Savannah”) and zoneId.

•

Create an Enclosure class with properties enclosureName, animalType,
and capacity.

•

Inside the Zone class, maintain a list of its enclosures using
an ArrayList.

•

In your main program, create an Array (or ArrayList) of Zone objects to
represent the entire zoo. Populate it with at least 3 zones, each
containing at least 2 enclosures.

Complexity Analysis: In your code comments or report, state the time
complexity (Big O) for finding a specific enclosure by name in your zoo
layout. Justify your answer based on the data structure used.
Milestone 2: The Visitor Queue (Queues)
Objective: Simulate a fair waiting system for a popular exhibit.
•

Create a Visitor class with a visitorName and ticketId.

•

Model the queue for the “Panda House” exhibit using a Queue interface
implemented with a LinkedList.

•

Implement functions to:
o

joinQueue(Visitor v): Adds a visitor to the end of the queue.

o

admitNextVisitor(): Removes and returns the visitor from the front
of the queue.

•

Complexity Analysis: What is the time complexity of
both joinQueue() and admitNextVisitor()? Explain why.

Restricted – ‫مقيد‬

Description and Instructions

Pg. 03

Milestone 3: The Keeper’s Task List (Stacks)
Objective: Model a Last-In-First-Out (LIFO) task management system.
•

Create a Task class with taskDescription and isUrgent flag.

•

Model the zookeeper’s task list using a Stack.

•

Implement functions to:
o

addNewTask(Task t): Pushes a new task onto the stack.

o

completeNextTask(): Pops and returns the task from the top of
the stack.

•

Complexity Analysis: What is the time complexity of
both addNewTask() and completeNextTask()? Explain why.

Milestone 4: The Animal Family Tree (Binary Search Trees)
Objective: Represent hierarchical data for animal genealogy.
•

Create an AnimalNode class with animalName, birthYear, leftChild,
and rightChild references.

•

Build a Binary Search Tree (BST) where each node is an animal. The
BST should be ordered based on the birthYear (older animals on the
left, younger on the right).

•

Implement a function findOldestAnimal() that traverses the tree to find
and return the animal with the smallest (oldest) birthYear.

•

Complexity Analysis: What is the time complexity of
the findOldestAnimal() function in the best-case and worstcase scenarios? Justify your answer by describing the structure of the
BST in each case.

Restricted – ‫مقيد‬

Description and Instructions

Pg. 04

Milestone 5: The Friendship Web (Graphs)
Objective: Map the connections between enclosures to enable pathfinding.
•

Model the zoo as a graph where each enclosure is a vertex (node).

•

Represent the paths between enclosures as edges. Use an Adjacency
List (e.g., a HashMap where the key is an
enclosure name and the value is a list of directly connected enclosures).

•

Implement a Breadth-First Search (BFS) algorithm to find and print a
valid path from the “Zoo Entrance” to a user-specified animal enclosure.

•

Complexity Analysis: What is the time complexity of your BFS
pathfinding algorithm? Explain your reasoning in terms of the number of
vertices (V) and edges (E) in the graph.

Core Deliverable: The Integrated Application
Objective: Combine all milestones into a single, interactive program.

Restricted – ‫مقيد‬

•

Create a main menu in the console that allows the user to select and run
each of the five functionalities (Layout, Queue, Stack, Tree, Graph).

•

The program should not crash on invalid input and should provide clear
instructions.

Description and Instructions

Pg. 05
4. What to submit?

You must submit a single file containing:
1. All well-commented source code.
2. Screen captures of all code functionality. (grade will be deducted if no
screen cap provided)
3. Complexity analysis for each milestone.

Marking Criteria
#

Marks

1

Milestones Source code (1 for each Milestone code and 1 for
integration)

6

2

Complexity with explanation of each milestone (1 for each
milestone)

5

3

Screen Captures for each functionality

3

Total

Restricted – ‫مقيد‬

Criteria

14

‫ر‬
‫الجامعة السعودية االلكتونية‬

‫ر‬
‫االلكتونية‬
‫الجامعة السعودية‬

‫‪26/12/2021‬‬
‫‪1‬‬

College of Computing and Informatics
Data Structure

2

Data Structure

Module 1
Introduction to Data Structures

1.
2.
3.
4.

Why Data Structure?
Mathematics Review
Implementing Generic Components Pre-Java 5
Implementing Generic Components Using Java
5 Generics
5. Algorithms as a technology

Contents

4

Weekly
Learning
Outcomes

1.

Recall the major mathematics concepts

2.

Review the basic of Java Primitive data types, classes,
objects and Interface
Introduce the concept of Algorithm design

3.

5

Required Reading
1. Chapter 1 (Data structures and algorithm analysis in Java
by Mark Allen Weiss)
Recommended Reading
1. Chapter 1 (al, Cormen Thomas H et. Introduction to Algorithms.
Cambridge, MA: MIT Press, 2009)

2. Beyond Basic Arithmetic:

6

• Why Data Structure?

7

Why Data Structure?
• “Why not just use a big array?”
• Example problem
Search for a number k in a set of N numbers

• Solution
Store numbers in an array of size N
Iterate through array until find k
Number of checks
Best case: 1 (k=29)
Worst case: N (k=25)
Average case: N/2
8

Why Data Structure?
• Suppose you have a group of N numbers and would like to
determine the kth largest. This is known as the selection
problem.
• One way to solve this problem would be to read the N numbers into
an array, sort the array in decreasing order by some simple algorithm,
and then return the element in position k.
• A somewhat better algorithm might be to read the first k elements
into an array and sort them (in decreasing order).
• Next, each remaining element is read one by one.
• As a new element arrives, it is ignored if it is smaller than the kth element in
the array.
• Otherwise, it is placed in its correct spot in the array, bumping one element
out of the array

• A simulation using a random file of 30 million elements and k
= 15,000,000 will show that neither algorithm finishes in a
reasonable amount of time;
9

Why Data Structure?

• Does it matter?
• The Message

• Appropriate data structures ease design and improve
performance

• The Challenge

• Design appropriate data structure and associated algorithms
for a problem
• Analyze to show improved performance

10

• Mathematics Review

11

Mathematics Review
• Exponents

12

Mathematics Review
• Logarithms

• In computer science, all logarithms are to the base 2 unless specified
otherwise.
• Definition 1.1.
XA = B if and only if logX B = A
Several convenient equalities follow from this definition.

• Review Page 3 in Chapter 1 (Required Book) for more revision.

13

Mathematics Review
• Series

• The easiest formulas to remember are

• Also, suppose:

•
S = 1 + A + A2 + A3 + A4 + A5 + · · ·
• Then:
AS = A + A2 + A3 + A4 + A5 + · · ·
• If we subtract these two equations
•
S – AS = 1
• Thus:

14

Mathematics Review
• Brief Revision to Recursion

• A function that is defined in terms of itself is called a recursive function.
• f(x) = 0, if x = 0
= 2f(x – 1) + x2, otherwise

• From this definition we see that:
•
•
•
•
•

f(0) = 0
f(1) = 1
f(2) = 6
f(3) = 21
f(4) = 58

15

Mathematics Review
• Brief Revision to Recursion
• Lines 3 and 4 handle what
is known as the base case.
• Line 6 is the recursive call

16

Mathematics Review
• Brief Revision to Recursion
Following are the first two fundamental rules of
recursion:
1. Base cases. You must always have some base cases,
which can be solved without recursion.

2. Making progress. For the cases that are to be
solved recursively, the recursive call must always be
to a case that makes progress toward a base case.

17

Mathematics Review
• Brief Revision to Recursion

• Printing Out Numbers Example:

• Suppose we have a positive integer, n, that we wish to print
out.
• Recursion provides a very clean solution to this problem. To
print out 76234, we need to first print out 7623 and then
print out 4.
• The second step is easily accomplished with the statement
printDigit(n%10)

18

Mathematics Review
• Design rule for Recursive Function
1. Base cases.

• You must always have some base cases, which can be solved without
recursion.

2. Making progress.

• For the cases that are to be solved recursively, the recursive call must always
be to a case that makes progress toward a base case.

3. Design rule.

• Assume that all the recursive calls work.

4. Compound interest rule.

• Never duplicate work by solving the same instance of a problem in separate
recursive calls.

19

• Implementing Generic Components Pre-Java 5

20

Implementing Generic Components Pre-Java 5

A generic implementation can be used to describe the basic
functionality.

For instance, a method can be written to sort an array of items; the
logic is independent of the types of objects being sorted, so a
generic method could be used.

21

Implementing Generic Components Pre-Java 5
• Using Object for Genericity

A generic MemoryCell class (pre-Java 5)

22

Implementing Generic Components Pre-Java 5
• Using Object for Genericity
• To access a specific method of the
object, we must downcast to the
correct type.
• primitive types cannot be used. Only
reference types are compatible with
Object

23

Implementing Generic Components Pre-Java 5
• Wrappers for Primitive Types
• Wrapper class: One typical use is to
store a primitive type, and add operations
that the primitive type either does not
support or does not support correctly.
• Java provides a wrapper class for each
of the eight primitive types. For instance,
the wrapper for the int type is Integer.
• Each wrapper object is immutable
(meaning its state can never change)

24

• Implementing Generic Components Using Java 5
Generics

25

Simple Generic Classes and Interfaces
• Description

• When a generic class is specified, the class
declaration includes one or more type parameters
enclosed in angle brackets after the class name.
• Line 1 shows that the GenericMemoryCell takes one
type parameter.
• In this instance, there are no explicit restrictions on
the type parameter, so the user can create types
such
as
GenericMemoryCell
and
GenericMemoryCell
but
not
GenericMemoryCell.
• Inside the GenericMemoryCell class declaration, we
can declare fields of the generic type and methods
that use the generic type as a parameter or return
type.
26

Simple Generic Classes and Interfaces
• The Diamond Operator
• Line 5 is annoying because since m is
of type GenericMemoryCell,
it is obvious that object being created
must also be
GenericMemoryCell; any
other type parameter would generate
a compiler error.
• Java 7 adds a new language feature,
known as the diamond operator, that
allows line 5 to be rewritten as

• GenericMemoryCell m =
new GenericMemoryCell( );

27

Simple Generic Classes and Interfaces
• The Diamond Operator

28

Simple Generic Classes and Interfaces
• Auto-Boxing/Unboxing between Primitives and their Wrapper Objects
• A Java Collection (such as List and Set) contains only objects. It cannot holds
primitives (such as int and double).
• On the other hand, arrays can hold primitives and objects, but they are not
resizable.
• To put a primitive into a Collection (such as ArrayList), you have to wrap the
primitive into an object using the corresponding primitive wrapper class.
// Pre-JDK 5 Integer intObj = new Integer(5566); // wrap an int to Integer by
constructing an instance of Integer
int i = intObj.intValue(); // unwrap Integer to int
Double doubleObj = new Double(55.66); // wrap double to Double
double d = doubleObj.doubleValue(); // unwrap Double to double

29

Reference:

Simple Generic Classes and Interfaces
• Auto-Boxing/Unboxing between Primitives and their Wrapper Objects
• The pre-JDK 5 approach involves quite a bit of codes to do the wrapping and
unwrapping.
• JDK 5 introduces a new feature called auto-boxing and auto-unboxing to
resolve this problem, by delegating the compiler to do the job. For example,
// JDK 5
Integer intObj = 5566; // auto-box from int to Integer by the compiler
int i = intObj; // auto-unbox from Integer to int by the compiler
Double doubleObj = 55.66; // auto-box from double to Double
double d = doubleObj; // auto-unbox from Double to double

30

Reference:

Simple Generic Classes and Interfaces
• Enhanced for-each Loop (JDK 5)
import java.util.List;
import java.util.ArrayList;
public class J5ForEachLoopTest {
public static void main(String[] args) {
// Use for-each loop on Array
int[] numArray = {11, 22, 33};
for (int num : numArray) System.out.println(num);
//11 //22 //33 //
Same as:
for (int idx = 0; idx void printArray( E[] inputArray ) {
// Display array elements
for(E element : inputArray) {
System.out.printf(“%s “, element);
}
System.out.println();
}
public static void main(String args[]) {
// Create arrays of Integer, Double and Character
Integer[] intArray = { 1, 2, 3, 4, 5 };
Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 };
Character[] charArray = { ‘H’, ‘E’, ‘L’, ‘L’, ‘O’ };
System.out.println(“Array integerArray contains:”);
printArray(intArray);
// pass an Integer array
System.out.println(“\nArray doubleArray contains:”);
printArray(doubleArray);
// pass a Double array
System.out.println(“\nArray characterArray contains:”);
printArray(charArray);
// pass a Character array
}
}

33

Reference:

Examples on Generic
• Bounded Type
Parameters

Reference:

34

Examples on Generic
• Generic Classes

Reference:

35

• Algorithms as a technology

36

Algorithms as a technology
• Algorithm

• is any well-defined computational procedure that takes some value, or set of
values, as input and produces some value, or set of values, as output.
• An algorithm is thus a sequence of computational steps that transform the
input into the output.

Reference:

37

Algorithms as a technology
• Characteristics of an Algorithm

Reference:

38

Algorithms as a technology
Algorithm Example:
• Example: Consider the example to add three numbers and print the sum.
• Step 1: Fulfilling the pre-requisites
As discussed above, in order to write an algorithm, its pre-requisites must be fulfilled.
•
•
•
•
•

The problem that is to be solved by this algorithm: Add 3 numbers and print their sum.
The constraints of the problem that must be considered while solving the problem: The numbers must contain only digits
and no other characters.
The input to be taken to solve the problem: The three numbers to be added.
The output to be expected when the problem the is solved: The sum of the three numbers taken as the input.
The solution to this problem, in the given constraints: The solution consists of adding the 3 numbers. It can be done with the
help of ‘+’ operator, or bit-wise, or any other method.

• Step 2: Designing the algorithm
Now let’s design the algorithm with the help of above pre-requisites:
Algorithm to add 3 numbers and print their sum:
•
•
•
•
•
•
•

START
Declare 3 integer variables num1, num2 and num3.
Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively.
Declare an integer variable sum to store the resultant sum of the 3 numbers.
Add the 3 numbers and store the result in the variable sum.
Print the value of variable sum
END

• Step 3: Testing the algorithm by implementing it.
39

Algorithms as a technology
• Algorithms and Data structures

• A data structure is a way to store and organize data
in order to facilitate access and modifications.
• No single data structure works well for all purposes,
and so it is important to know the strengths and
limitations of several of them.

40

Algorithms as a technology
• Suppose computers were infinitely fast and computer
memory was free. Would you have any reason to study
algorithms?

• The answer is yes, if for no other reason than that you would still
like to demonstrate that your solution method terminates and does
so with the correct answer.

1. Computers may be fast, but they are not infinitely fast
2. Memory may be inexpensive, but it is not free.

• Computing time is therefore a bounded resource.
• So is space in memory is bounded.
• You should use these resources wisely, and algorithms that are
efficient in terms of time or space will help you do so.

41

Algorithms as a technology
• Algorithm Efficiency
• Different algorithms devised to solve the same problem often
differ dramatically in their efficiency.
• These differences can be much more significant than differences
due to hardware and software.

42

Algorithms as a technology
• Algorithms and other technologies

• You might wonder whether algorithms are truly that important on
contemporary computers in light of other advanced technologies, such
as:
• easy-to-use, intuitive, graphical user interfaces (GUIs),
• integrated Web technologies.

• The answer is yes.

• For example, consider a Web-based service that determines how to
travel from one location to another.
• Its implementation would rely on :
• fast hardware
• a graphical user interface
• wide-area networking

• However, it would also require algorithms for certain operations, such as:
• finding routes (probably using a shortest-path algorithm)
• rendering maps

43

References
1. Data structures and algorithm analysis in Java by Mark Allen Weiss

44

Smart data structures, good algorithm and dumb
code works a lot better than the other way around.

Eric Raymond

45

Thank You

46

‫ر‬
‫الجامعة السعودية االلكتونية‬

‫ر‬
‫االلكتونية‬
‫الجامعة السعودية‬

‫‪26/12/2021‬‬
‫‪1‬‬

College of Computing and Informatics
Data Structure

2

Data Structure

Module 10
Sorting II

3

1. Mergesort
2. Quicksort
3. External Sorting

Contents

4

Weekly
Learning
Outcomes

1. Understand the problem of sorting elements
2. Analyze various sorting algorithms and their complexity
3. Implement various sorting algorithms such as Mergsort and
Quicksort .
4. Learn how to sort large amount of data

5

Required Reading
1. Chapter 7: Sorting. (PP: 288 – 321)
(Data structures and algorithm analysis in Java by Mark Allen
Weiss)
Recommended Reading
1. Chapter 6, 7, 8 (al, Cormen Thomas H et. Introduction to
Algorithms. Cambridge, MA: MIT Press, 2009)

6

This Presentation is mainly dependent on the textbook: Data Structures and Algorithm Analysis in Java by Mark Allen Weiss

• Mergesort

7

Mergesort
• Mergesort is an example of a recursive algorithm.
• The worst-case running time of Mergesort is O(N log N).
• The basic operation in this algorithm is merging two sorted lists.
• Merge sort orders values by recursively dividing the list in half. The
recursion stops when each sub-list has one element, then
recombining.
• Steps for conducting Mergesort:
1. divide the list into two parts of approximately equal length.
2. recursively divide each part into two parts of approximately equal length.
Stop when each part contains only one element.
3. merge each two parts into one sorted list.
4. continue to merge parts until merging all parts into one sorted list
8

Mergesort (Sorting Example 1)
• Sort the following array items using Mergesort {66, 17, 69, 63, 22, 57,
32, 50, 7, 90}.
Step 1: divide the list into two parts of approximately equal length.

9

Mergesort (Sorting Example 1)
Step 2: recursively divide each part into two parts of approximately
equal length. Stop when each part contains only one element.

10

Mergesort (Sorting Example 1)
Step 3: merge each two parts into one sorted list.

11

Mergesort (Sorting Example 1)
Step 4: continue to merge parts until merging all parts into one sorted list

12

Mergesort (Sorting Example 2)
To understand how the merging algorithm works, suppose we have two sorted
arrays; X{8, 12, 14, 17} and Y{9, 16, 19, 20}. We want to combine the two arrays
into array Z{}.
First, compare 8 from X with 9 from Y: 8 is smaller.
Z{8}
Then, compare 12 from X with 9 from Y: 9 is smaller.
Z{8, 9}
Then, compare 12 from X with 16 from Y: 12 is smaller.
Z{8, 9, 12}
Then, compare 14 from X with 16 from Y: 14 is smaller.
Z{8, 9, 12, 14}
Continue until all items in both array X and array Y are added to array Z.
Z{8, 9, 12, 14, 16, 17, 19, 20}
13

Mergesort (Algorithm)

mergesort(data[], firstItem, lastItem)
if firstItem
Purchase answer to see full
attachment