Unit 4: Computational Structures — Long Questions

Primitive computational structures are the simplest and most fundamental components or operations used in computing systems. They serve as the building blocks for more complex programs and algorithms.

Examples Include basic data types (like integers and booleans), arithmetic and logical operations, and simple control structures like loops and conditionals.

Important in Computer Science
They are important in computer science because:
• Foundation of Computation: All higher-level software and algorithms are built using these primitives.
• Enable Abstraction: They allow developers to build complex systems by combining simple, well-understood elements.
• Determine Capabilities: The choice of primitives affects what a system can compute and how efficiently it can do so.
• Facilitate Learning and Design: Understanding primitives helps in learning programming languages, designing algorithms, and analyzing system behavior.

A list is a data structure used to store multiple pieces of data in a specific sequence. Each piece of data, known as an element, is positioned at a particular index within the list, facilitating easy access and management.

List Creation
In Python, Lists are created using square brackets '[]', with each item separated by a comma.
#Create a list of items
items=["Decorations","Snacks","Cold drinks","Plates","Balloon"]
#Print the list
print(items)

Explanation
"items" is the name of the list. The items inside the list are "Decorations", "Snacks", "Cold drinks", "Plates", and "Balloons". Each item is enclosed in quotes (for text) and separated by a comma.

Properties of Lists
List has following properties:
1) Dynamic Size: A list in Python can change its size. You can add new items to the list or remove items without any problems. The list will automatically adjust to fit the changes.
2) Index-Based Access: Every item in a list has a position, called an index. The first item has an index of 0, the second item has an index of 1, and so on. You can use these indexes to get specific items from the list.
3) Ordered Collection: The order in which you add items to a list is preserved. This means that if you add an item first, it will stay in that position unless you change it.

Some common operations of a list are:
1) Insertion: Adding a new item to your list is like adding a new task to your to-do list. You can insert an item at different positions in the list. You can insert an item at any position in the list using the 'insert( )' function.
party_list=["Buy drinks","Buy decorations","Buy snacks","Buy cold drinks"]
party_list.insert(0,"Invite friends")
#add Invite friends at start
print(party_list)
# Output: ["Buy drinks,"Buy decorations","Buy snacks","Buy cold drinks "]

2) Deletion: Removing an item from your list is like crossing off a task you've completed. You can remove items in various ways:
• Removing by Value: Use the 'remove()' function to delete the first occurrence of a specific item.
party_list=["Invite friends","Buy decorations","Buy snacks","Buy cold drinks"]
party_list.remove("Buy snacks")
#Removes'Buy snacks'from the list
print(party_list)
# Output: ['Invite friends','Buy decorations','Buy cold drinks ']

• Removing by Index: Use the 'pop()' function to remove an item at a specific index.
party_list=["Invite friends ","Buy decorations","Buy cold drinks"]
party_list.pop(0)
# Removes the item at index 0
print(party_list)
# Output: ['Buy decorations','Buy cold drinks']

• Searching: Finding an item in a list is similar to looking for a specific task in your to-do list. You can search for an item using different functions: Use the 'in' keyword to check if an item exists in the list.
party_list=["Invite friends","Buy decorations","Buy cold drinks"]if "Buy cold drinks" in party_list:
print("Buy cold drinks is on the list.")
# Prints if 'Buy cold drinks'is found
else:
print("Buy cold drinks is not on the list.")
# Output: Buy cold drinks is on the list.

Applications of lists
Two key applications of lists in data structures are:
• Data Storage and Manipulation: Lists are commonly used to store and manage collections of data, such as records, entries, or values. They allow for easy insertion, deletion, and access of elements.
• Stack and Queue Implementations: Lists can be used to implement stack (LIFO) and queue (FIFO) data structures, which are fundamental for various algorithms and tasks in computing.

A stack is a simple data structure where you can only add or remove items from one end, known as the "top". Both insertion and deletion of elements occur at this top end. A stack operates on the Last-In, First-Out (LIFO) principle, meaning that the most recently added element is the first one to be removed.

Stack Operations
There are two basic operations in a stack:
1) Push Operation: Push means adding an item to the top of the stack.
2) Pop Operation: Pop means removing the item from the top of the stack.
These operations follow the LIFO (Last-In, First-Out) rule, meaning the last item added is the first one removed.
#Create an empty stack of books
stack_of_books = []
print("Initial stack:",stack_of_books)
#Empty stack
#Add books to the stack (push operation)
print("n Adding books to the stack (push operation):")
stack_of_books.append('Book A')
print("Stack after pushing 'Book A':", stack_of_books)
stack_of_books.append('Book B')
print("Stack after pushing'Book B':",stack_of_books)
#Remove the top book from the stack (pop operation)
print("nDeletion of top book (pop operation):") top_book = stack_of_books.pop()
print("Removed book:",top_book)
print("Stack after popping the top book:",stack_of_books)

The code creates an empty stack to hold books. It then adds books ("Book A" and "Book B") one by one to the top of the stack. Finally, it removes the top book from the stack, showing how the last book added is the first one taken off.

A queue is like a line in front of a bank or a ticket counter. The first person to get in line is the first person to be served. In a computer, a queue works the same way. It keeps track of things so that the first item added is the first one to be taken out. Just like in a bank line, you add things to the back and remove them from the front, following the FIFO (First-In, First-Out) principle, as shown in following figure.

Queue Operations
Queues support two primary operations:
1) Enqueue (Add an Item): This is like adding a person to the end of the line. In a queue, you add items to the back.
2) Dequeue (Remove an Item): This is like serving the person at the front of the line. In a queue, you take items out from the front. Additional operations might include checking if the queue is empty, retrieving the element at the front without removing it, and determining the size of the queue.

#Built-in module to implement queues in python from queue import Queue
#Create a new queue
q=Queue()
#Add people to the queue (Enqueue)
q.put("Ahmed")#Adds Ahmed to the end of the queue
q.put("Fatima")#Adds Fatima to the end of the queue
# View the person at the front of the queue (Peek)
front_person = q.queue [0]
#Looks at the person at the front without removing them
print(front_person)
#Remove a person from the front of the queue(Dequeue)
removed_person = q.get( )
#Removes and returns the person at the front of the queue
print(removed_person)

#Add another person to the queue (Enqueue)
q.put("Sara")
#Adds Sara to the end of the queue
#View the updated queue
updated_queue = list(q.queue)
print(updated_queue)

The code manages a line of people using a queue. It adds people to the end of the line, checks who is at the front without removing them, and then serves (removes) the person at the front. Finally, it adds another person to the end and shows the updated line.

A tree data structure organizes information in a way that spreads out from a main point called the root node. In a tree, each piece of information, called a node, can connect to other pieces, which are also nodes, forming a branching structure. This branching structure is different from a list, where items are organized one after the other in a straight line.

Example In a family tree, the oldest ancestors represent the root node, serving as the starting point of the hierarchy. Each individual in the tree may have descendants, forming subsequent levels of the hierarchy, as illustrated in following figure. This hierarchical structure is not suitable for storage in a linear format, such as a list, due to the complex parent-child relationships. Therefore, a tree data structure is employed to efficiently store and access such hierarchical data, enabling clear representation and retrieval of information.

Properties of Tree
• Root Node: The root is the very first or top node in a tree, like the main folder in a computer where all other folders and files are contained.
• Edges and Nodes: Nodes are the individual elements in the tree, and they are connected by lines called edges. A node without any child nodes is called a leaf, similar to a file in a folder that doesn't contain any other files.
• Height: The height of a tree is the longest path from the root node down to the farthest leaf. It tells us how deep or tall the tree is.
• Balanced Tree: A tree is considered balanced if the branches on the left and right sides are nearly the same height.

Applications of Trees
• File Systems: Pre-order tree traversal is useful for creating backups of file systems. By visiting the root first and then recursively backing up each directory, it ensures that directories are backed up before their contents.
• File System Deletion: In file systems, post-order traversal ensures that files and directories are deleted in the correct order; by first deleting all sub-directories and files before deleting the parent directory.
• Hierarchical Data Representation: Trees are used in representing data with a clear hierarchical relationship, such as organizational charts and family trees.
• Decision Making: Trees, such as decision trees, are used in algorithms to make decisions based on various conditions and outcomes.

A Graph is a data structure that consists of a set of vertices (or nodes) connected by edges. Graphs are used to represent networks of connections, where each connection is a relationship between two vertices. These vertices can represent anything, like cities, people, or even abstract concepts, and the edges represent the relationships or pathways between them.

Imagine you are mapping out all the cities in Pakistan and the roads that connect them. Each city is a vertex, and each road between two cities is an edge. Unlike a tree, a graph does not have a single "root" and does not follow a hierarchical structure. In a graph, any two vertices can be connected, creating a complex web of relationships.

Example In a social network, each person can be connected to many others, forming a graph. There is no single starting point, and people (vertices) can have multiple connections (edges) that do not follow a strict parent-child relationship like in a tree.

Difference between Tree and Graph

Feature | Tree | Graph
Hierarchy | Hierarchical structure with a single root node | No fixed hierarchy; may not have a root node
Paths Between Nodes | Exactly one unique path between any two nodes (no cycles) | Can have multiple paths between nodes; cycles are allowed
Structure | Acyclic (no loops) | Can be cyclic (may contain loops)
Type | [No entry] | [No entry]
Use Cases | Used for structured data (e.g., family trees, organizational charts) | Used for complex relationships (e.g., social networks, transport maps, web links)
Connectivity | Always connected (if not, it's a forest) | Can be connected or disconnected

Characteristics of Graphs

Graphs have several defining features that help us understand and use them effectively:
1) Vertices (Nodes): These are the individual points or entities in a graph.
For example, in a social network graph, each user is represented by a vertex.
2) Edges (Links): These are the connections between vertices.
For example, in a transport system graph, each road connecting two cities is an edge.

Properties of Graphs

Graphs also have specific details that describe their structure:
1) Degree: This is the number of edges connected to a vertex.
For instance, if a city is connected to three other cities, the degree of that city's vertex is three.
2) Weight: In some graphs, edges have weights that represent values like distances or costs.
For example, if a road between two cities is 50 kilometers long, its edge might have a weight of 50.
3) Direction: Edges can be either directed or undirected. Directed edges have a one-way connection, meaning a road from city A to city B does not necessarily have a return road from B to A. Undirected edges represent a two-way connection.

A Graph is a data structure that consists of a set of vertices (or nodes) connected by edges. Graphs are used to represent networks of connections, where each connection is a relationship between two vertices.

Types of Graphs

Graphs can be classified into several types based on their structure and properties. The main types of graphs are directed, undirected, and weighted. Each type has its own characteristics, which can be better understood through simple examples.
1) Directed Graphs: In a directed graph, edges have a direction, which means they go from one vertex to another in a specific way as shown in following figure.
Example: Consider a graph shown in above figure. If you want to travel from city A to city B, you can only go in the direction permitted by the city's sign. If there's no one-way street going from city A to city B, you cannot travel directly from city A to B.
2) Undirected Graphs: In an undirected graph, edges do not have a direction. This means that if there is a connection between two vertices, you can travel in both directions.
Example: Consider a graph that shown in following figure, if Person A is friends with Person B, then Person B is also friends with Person A. There is no restriction on the direction of the friendship, so you can move freely between friends.
3) Weighted Graphs: In a weighted graph, each edge has a weight or cost associated with it. This weight represents the distance, time, or cost required to travel from one vertex to another.
Example: Imagine a map of a city where each road has a different distance or travel time. If you want to travel from one landmark to another, the map provides the distance or travel time for each road. This information helps you determine the shortest or quickest route between landmarks.

Differences between Directed and Undirected Graphs

Aspect | Directed Graph | Undirected Graph
Edge Direction | Edges have a specific direction (A → B) | Edges do not have direction (A — B)
Connection Type | One-way relationship | Two-way (mutual) relationship
Representation | Ordered pairs (A, B) | Unordered pairs {A, B}
Real-life Example | Twitter (A follows B, but B may not follow A) | Facebook (A and B are friends)
Degree of Node | In-degree and out-degree are separate | Only degree (number of connections)
Application Use | Web links, task scheduling, maps with one-way roads | Social networks, undirected maps

[ANSWER CONTINUES BEYOND PAGE 8]