Abstract Data Types

📘 Notes on Abstract Data Types (ADTs)

1. Abstract Data Type (ADT)
●​ An ADT defines a data structure purely by its behavior (operations it supports), not
by its implementation.
●​ Examples: Stack, Queue, Linked List, Tree, Graph.

2. Stack
●​ A linear data structure that follows the LIFO (Last In, First Out) principle.
●​ Operations:
o​ push(x) → Insert element x at the top.
o​ pop() → Remove the element from the top.
o​ peek() → View the element at the top without removing it.
o​ isEmpty() → Check if the stack is empty.

Example:

●​ Undo operations in editors.

●​ Browser history (back/forward navigation).

Sample Code (Python):

class Stack:
def __init__(self):
[Link] = []

def push(self, item):

[Link](item)

def pop(self):
return [Link]() if not self.is_empty() else None

def peek(self):
return [Link][-1] if not self.is_empty() else None

def is_empty(self):
return len([Link]) == 0

# Example usage
stack = Stack()
[Link](10)
[Link](20)
print([Link]()) # 20
print([Link]()) # 10
3. Queue
●​ A linear data structure that follows the FIFO (First In, First Out) principle.
●​ Operations:
o​ enqueue(x) → Insert element at the rear.
o​ dequeue() → Remove element from the front.
o​ peek() → View the element at the front.
o​ isEmpty() → Check if the queue is empty.

Example:

●​ Printing jobs in a printer queue.

●​ Call center waiting line.

Sample Code (Python):

class Queue:
def __init__(self):
[Link] = []

def enqueue(self, item):

[Link](item)

def dequeue(self):
return [Link](0) if not self.is_empty() else None

def peek(self):
return [Link][0] if not self.is_empty() else None

def is_empty(self):
return len([Link]) == 0

# Example usage
queue = Queue()
[Link](1)
[Link](2)
print([Link]()) # 1
print([Link]()) # 2

4. Linked List
●​ A linear data structure where elements (nodes) are connected using pointers.
●​ Each node contains:
o​ Data (value)
o​ Pointer (reference to the next node, or previous + next in some cases).

Types of Linked Lists:

1.​ Singly Linked List

 2.​ Doubly Linked List
3.​ Circular Linked List

4.1 Singly Linked List (SLL)

●​ Each node contains: data + pointer to next node.

●​ Traversal only in one direction.

Example: Student roll numbers in a sequence.

Sample Code (Python):

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class SinglyLinkedList:
def __init__(self):
[Link] = None

def append(self, data):

new_node = Node(data)
if not [Link]:
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node

def display(self):
current = [Link]
while current:
print([Link], end=" -> ")
current = [Link]
print("None")

# Example usage
sll = SinglyLinkedList()
[Link](10)
[Link](20)
[Link](30)
[Link]() # 10 -> 20 -> 30 -> None

4.2 Doubly Linked List (DLL)

●​ Each node contains: data + pointer to next + pointer to previous.

●​ Traversal possible in both directions.

Example: Music playlist (can move forward and backward).

Sample Code (Python):

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

def append(self, data):

new_node = Node(data)
if not [Link]:
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node
new_node.prev = current

def display(self):
current = [Link]
while current:
print([Link], end=" <-> ")
current = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
[Link](1)
[Link](2)
[Link](3)
[Link]() # 1 <-> 2 <-> 3 <-> None

4.3 Circular Linked List (CLL)

●​ Last node points back to the first node, forming a circle.

●​ Can be singly or doubly circular.

Example: Multiplayer board games (turns cycle among players).

Sample Code (Python):

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class CircularLinkedList:
def __init__(self):
[Link] = None

def append(self, data):

 new_node = Node(data)
if not [Link]:
[Link] = new_node
new_node.next = [Link]
return
current = [Link]
while [Link] != [Link]:
current = [Link]
[Link] = new_node
new_node.next = [Link]

def display(self, count=10): # limit to avoid infinite loop

current = [Link]
if not current:
return
for _ in range(count):
print([Link], end=" -> ")
current = [Link]
print("...")

# Example usage
cll = CircularLinkedList()
[Link]("A")
[Link]("B")
[Link]("C")
[Link]() # A -> B -> C -> A -> ...

✅ Summary Table
ADT Principle Direction Example Use Case
Stack LIFO One way Undo, Backtracking
Queue FIFO One way Print Queue, Waiting Line
SLL Linear One way Sequential data storage
DLL Linear Two way Playlists, Navigation
CLL Circular One way/two way Multiplayer Games, Round-robin scheduling
The System Development Life Cycle
(SDLC)
The System Development Life Cycle (SDLC)

What is an Information System (IS)?

An information system consists of hardware, software, data, people, and procedures that
work together to produce quality information.

System

A system is a set of components that interact to achieve a common goal.

Phases of the System Development Life Cycle

Phase 1: Planning
●​ Review project requests​

●​ Prioritize project requests​

●​ Allocate resources​

●​ Identify project development team​

Phase 2: Analysis
●​ Conduct preliminary investigation​

●​ Perform detailed analysis activities:​

○​ Study current system​

○​ Determine user requirements​

○​ Recommend solution​
Phase 3: Design
●​ Acquire hardware and software (if necessary)​

●​ Develop detailed design of the system​

Phase 4: Implementation
●​ Develop programs​

●​ Install and test new system​

●​ Train users​

●​ Convert to new system​

Phase 5: Support
●​ Conduct post‑implementation review​

●​ Identify errors and enhancements​

●​ Monitor system performance​

Guidelines for System Development

●​ Arrange tasks into phases​

●​ Involve users​

●​ Develop clearly defined standards​

Who Participates in the SDLC?

 ●​ Users​

●​ Management​

●​ System Analyst​

●​ Network Engineer​

●​ Database Administrator​

●​ Database Analyst​

●​ Steering Committee​

●​ Webmaster​

●​ Vendors​

Systems Analyst
A systems analyst is responsible for designing and developing an information system and acts
as a liaison between users and IT professionals.

Project Team
A group of people with defined roles working together to complete a project.​
Includes users, systems analysts, and IT professionals.

Project Leader

Manages and controls project budget, schedule, and ensures work is completed on time.

Feasibility
A measure of how suitable the system development is for the company.

Four Feasibility Tests

1.​ Technical Feasibility – Determines whether the organization has the needed
technology, resources, and expertise.​

2.​ Operational Feasibility – Determines whether users will adopt the system and if it
will function well in the organization.​

3.​ Economic Feasibility – Determines whether benefits outweigh costs.​

4.​ Schedule Feasibility – Determines whether the system can be developed in the
required timeframe.​

Documentation
Collection and summarization of data and information (reports, diagrams, programs,
deliverables).

Six Data and Information Gathering

Techniques
1.​ Review documentation​

2.​ Observe​

3.​ Questionnaire​

4.​ Interview​

5.​ Joint‑application design (JAD) session​

6.​ Research​
Reasons to Create or Modify an Information
System
●​ Correct problems in existing system​

●​ Improve existing system​

●​ External mandate requires change​

●​ Competition necessitates improvement​

Request for System Services

A formal request for a new or modified information system. Also called a project request.

Planning Phase
Begins when the steering committee receives a project request.

Steering Committee Functions

●​ Review and approve project requests​

●​ Prioritize requests​

●​ Allocate resources​

●​ Form project development teams​

Analysis Phase
Includes:

●​ Preliminary investigation (feasibility study)​

●​ Detailed analysis​

Preliminary Investigation
Determines nature of problem or improvement and whether it is worth pursuing; results in a
feasibility report.

Detailed Analysis
1.​ Study current system​

2.​ Determine users’ wants, needs, and requirements​

3.​ Recommend solution (logical design)​

System Proposal

Assesses feasibility of alternatives and recommends the most suitable one.

Possible Solutions

●​ Buy packaged software​

●​ Write custom software​

●​ Outsource development​

Design Phase
●​ Acquire hardware and software​
 ●​ Develop detailed system specifications​

Identifying Hardware & Software Needs

●​ Consult analysts​

●​ Research online​

●​ Visit vendors​

●​ Read trade publications​

Three Technical Specification Documents

●​ RFQ: Vendor quotes price for listed products​

●​ RFP: Vendor proposes products that meets requirements and quotes price​

●​ RFI: Requests general information about products/services

Software Testing Methods (During Selection)

●​ References from vendor​

●​ Contacting current users​

●​ Demonstrations​

●​ Trial versions​

●​ Benchmark tests

Detailed Design
– Provides specifications and focuses on how each component or module of the system will
be built,

Includes:

●​ Database design​

●​ Input and output design​

●​ Program design​

Mockup
A sample of input or output containing actual data.

Prototype
A preliminary working model used to demonstrate functionality before full development.

CASE Tools
Software tools that support SDLC activities.

Implementation Phase
●​ Develop programs​

●​ Install and test system​

●​ Train users​
 ●​ Convert to new system​

Types of Testing

●​ Unit Test – Tests individual programs​

●​ System Test – Tests all programs together​

●​ Integration Test – Tests compatibility with other applications​

Training
Teaches users how to operate the new system.

Support Phase
●​ Monitor system performance​

●​ Identify enhancements and errors​

●​ Conduct post‑implementation review​

WORKSHEET SECTION: QUIZ
YOURSELF

Short Answer Questions

1.​ What are the five components of an information system?​

2.​ What is the purpose of the preliminary investigation?​

3.​ Name the four feasibility tests.​

4.​ What is the role of the systems analyst?​

5.​ List three reasons why a company may need to modify an information system.​

6.​ What are the main objectives of the design phase?​

7.​ What is a prototype and why is it used?​

8.​ What are the three types of tests performed during implementation?​

9.​ What is the purpose of the support phase?​

10.​What is a system proposal?​

Multiple‑Choice Questions (MCQ)
1. Which of the following is not a phase of the SDLC?

A. Planning​
B. Analysis​
C. Installation​
D. Implementation

2. Which feasibility test examines whether the project fits the deadline?

A. Technical​
B. Operational​
C. Schedule​
D. Economic

3. A systems analyst primarily acts as a:

A. Hardware technician​
B. Liaison between users and IT​
C. Database backup operator​
D. Network installer

4. Which document asks vendors to quote prices for specific products?

A. RFP​
B. RFI​
C. RFQ​
D. SLA

5. The detailed analysis phase is also called:

A. Logical design​
B. Physical design​
C. Preliminary investigation​
D. Prototyping

6. Which of the following involves testing individual program modules?

A. System test​
B. Unit test​
C. Pilot test​
D. Integration test
7. Which SDLC phase includes training users?

A. Planning​
B. Analysis​
C. Implementation​
D. Support

8. A mockup is a:

A. Working system​
B. Sample input/output with real data​
C. Network diagram​
D. Software license

9. Which team makes decisions on project approval?

A. Database team​
B. Steering committee​
C. Vendor team​
D. Executive supporters

10. A prototype is developed to:

A. Replace the final system​

B. Demonstrate functionality early​
C. Serve as final documentation​
D. Train only developers
Answer Keys & Diagrams
1. Verification vs Validation – Answer Key

●​ Verification: "Are we building the product right?" It checks if the system meets
specifications.​

●​ Validation: "Are we building the right product?" It checks if the system meets user
needs.​

2. Top-Down Design – Answer Key

●​ Breaking a system into major modules first, then into smaller submodules.​

3. Bottom-Up Design – Answer Key

●​ Building small components first and then combining them into larger systems.​

SDLC Diagram (Text-Based)

Planning → Analysis → Design → Implementation → Maintenance/Support
1. Hospital / Clinic System
●​ Current system: Doctors manually write patient records; lab results are written on
paper and stored in files; appointment booking is done via phone.​

●​ Possible question: “Identify the issues and propose a computerized patient

management system.”​

●​ Issues to highlight:​

○​ Misplaced patient records​

○​ Delays in retrieving information​

○​ Errors in lab results​

○​ Double-booked appointments​

●​ SDLC solution: Implement an electronic patient management system with databases,

automated appointment scheduling, and digital lab reporting.

The current manual patient record system has several issues. First, patient files can easily be
lost or misplaced, delaying treatment and creating medical errors. Second, manually writing
lab results often leads to errors in recording important data, which may affect diagnosis.
Third, appointments are difficult to track, resulting in double bookings and scheduling
conflicts. Fourth, retrieving patient information is time-consuming, especially during
emergencies. Fifth, manual data entry creates redundant work for staff who must copy
information between files. Sixth, the system makes report generation slow and inaccurate,
as compiling information from multiple paper files is tedious. A computerized Patient
Management System would address these issues by storing patient data digitally, allowing
quick and secure retrieval. Automated lab reporting reduces recording errors. Appointment
scheduling can be automated to prevent conflicts. Redundant data entry is minimized, and
reports can be generated instantly, improving accuracy and efficiency. Overall, the system
enhances patient care and operational efficiency.
2. School / University System
●​ Current system: Grades, attendance, and student records are stored in notebooks or
spreadsheets.​

●​ Possible question: “Design a system to manage student data efficiently.”​

●​ Issues to highlight:​

○​ Loss of records​

○​ Slow grade calculation​

○​ Difficulty generating reports​

●​ SDLC solution: Create a student information system (SIS) for digital record-keeping,
automatic report generation, and attendance tracking.

Manual record-keeping in schools has many challenges. First, student records can be lost or
damaged, causing administrative delays. Second, calculating grades manually is
time-consuming and prone to errors. Third, attendance tracking is inaccurate, especially
for large classes. Fourth, generating transcripts and performance reports is slow. Fifth,
communication with parents and students is limited and inefficient, as notices are often
physical. Sixth, managing course registrations manually can lead to double bookings or
errors in class allocation. A computerized Student Information System resolves these
problems by storing all student information in a digital database, allowing easy retrieval and
secure storage. Grade calculations and attendance tracking are automated, reducing errors.
Reports can be generated instantly. Notifications can be sent digitally to parents and students,
and course registration can be handled efficiently without conflicts. This improves accuracy,
efficiency, and communication.
Waterfall Methodology
What is Waterfall Methodology?

The Waterfall methodology is an approach to project management that follows a linear,

sequential process. This approach is popular in software engineering and is called Software
Development Lifecycle (SDLC). However, product development is also utilizing this model.

The term “waterfall” refers to the flow of the project, where each phase cascades down to the
next. It involves a detailed planning phase, execution, testing, and maintenance. And each
phase must be completed before moving on to the next, with little to no flexibility for
changes during the project.

Additionally, the waterfall model is known for its structure and predictability, allowing teams
to plan and budget accurately. Furthermore, it can also be criticized for its inflexibility and
lack of adaptability to changing circumstances.

Advantages

Among the advantages of the waterfall model are the following:

●​ Provides a way for large or changing teams to work together toward a common goal
defined in the requirements phase
●​ Ensures a disciplined and structured organization
●​ Provides a simple method to understand, follow, and arrange tasks
●​ Facilitates management control and departmentalization based on deadlines
●​ Establishes good coding habits by defining first, then implementing design
●​ Provides easy access to early system design and specification changes
●​ Defines milestones and deadlines clearly

Disadvantages

However, the waterfall model has drawbacks, including its inflexibility and lack of revision
opportunities. Some specific concerns include the following:

●​ Design flaws, when discovered, often mean starting over from scratch
●​ It doesn’t incorporate mid-process feedback from users or clients and makes changes
based on results
●​ Delaying the testing until the end of development is common
●​ There’s no consideration for error correction
●​ The model doesn’t accommodate changes, scope adjustments, and updates well
●​ Work on different phases doesn’t overlap, which reduces the efficiency
●​ Projects don’t produce a working product until later stages
●​ Not an ideal model to use for complex and high-risk projects

When to Use the Waterfall Methodology?

The waterfall model’s planning and documentation can be helpful for efficient resource
allocation, but its inflexibility may limit plan modifications. So, evaluating the project
requirements is necessary to determine if the model is suitable. The following are some
instances when a waterfall system would be a great choice.

Established Project Requirements

Waterfall management may be the better choice if you have a clear objective in mind for your
project. However, suppose the end goal is unclear, and there are ambiguous requirements or
potential changes in direction. In that case, other project management methodologies may be
the best approach for you or your clients.

Well-Defined Project Tasks and Deadlines

The waterfall model is a structured methodology. Hence, this methodology is designed for
businesses prioritizing meeting deadlines, some examples are the construction or
manufacturing industry.

You Have Plenty of Time to Plan

Waterfall management requires significant time allocated to the first two stages. If you have
enough time to gather requirements and plan, you may opt for the waterfall approach.
However, utilizing other methodologies may suit those with time constraints.

Phases of the Waterfall Model

Each phase of the waterfall model follows a strict linear order, where a phase can’t begin
until the previous one is complete. Following is a description of the phases.
Stage 1: Requirements
The first phase involves collecting all customer requirements at the start of the project,
enabling subsequent phases to be planned without additional customer input until the product
is finished. The assumption is that all requirements are gathered during this phase.
 Stage 2: Design
During the design phase, it’s recommended to divide it into two subphases: logical design and
physical design. The logical design subphase involves brainstorming and theorizing possible
solutions, while the physical design subphase involves turning those theoretical ideas and
schemas into specific specifications.
Stage 3: Implementation
During this phase, programmers use the requirements and specifications from earlier phases
to create the functional code. Returning to the design phase may be necessary if significant
changes are needed.
Stage 4: Verification
During this phase, the customer reviews the product to verify that it fulfills the initial
requirements outlined at the start of the project. The final step is to deliver the finished
product to the customer.
Stage 5: Maintenance
In the maintenance phase, the customer uses the product and detects issues such as bugs,
insufficient features, and errors during production. Then the production team makes
corrections as needed to ensure customer satisfaction.
Variation of the Waterfall Method: V-Model
Over time, the waterfall method has evolved to meet the changing needs of users, enhancing
and expanding upon the original technique.
The V-Model is a widely used development model for application testing. It involves dividing
the model into sub-phases and implementing corresponding testing phases for each
development phase. It is also known as the Verification and Validation Model.
The model follows a sequential approach, with each phase starting only after completing the
previous one. The V-Model requires detailed specifications at the beginning and involves
significant customer involvement. However, it is also considered an expensive approach.
Software and Tools for Managing Waterfall Projects
Gantt charts are often used for waterfall project management. They facilitate the visualization
of sequential phases, allowing project managers to assign dependencies and subtasks to each
process phase. They also provide a clear view of timelines and deadlines for each phase.
However, if you’re looking for project management software to help complete your tasks.
Here are some essential features you should consider.

●​ Ability to collaborate with your team

●​ Capability to take notes
●​ Analyze and visualize data to gain insights
●​ Organize projects into workflows
●​ Secure storage of all project data
PAST PAPERS
PAPER 2 2025
The most appropriate data structure is a stack. A stack works on the principle of Last In,
First Out (LIFO). This would mean that the last book placed on the pile is the first one that
can be removed. This matches the way the books are physically stacked, as you can only
take from the top without disturbing the rest.

A queue would not be suitable. It works on First In, First Out (FIFO). That would mean the
first book placed should be the first one removed, but in a physical pile of books, you can’t
easily access the bottom book without moving the others.
Benefits of Agile

●​ Flexibility: Adapts to changing requirements.

●​ Faster delivery: Frequent releases provide value sooner.
●​ Improved quality: Continuous testing and feedback.
●​ Customer focus: Regular stakeholder involvement ensures alignment.
●​ Team empowerment: Encourages collaboration and ownership.
Challenges & Trade‑Offs

●​ Scope creep: Frequent changes can expand project scope.

●​ Requires discipline: Teams must commit to regular meetings and reviews.
●​ Not ideal for fixed contracts: Works best when requirements are evolving.

1. Black Box Testing

●​ Focuses on the functionality of the software without looking at the internal code.
●​ Testers provide inputs and check outputs against expected results.
●​ Ensures the system meets user requirements.

2. White Box Testing

●​ Focuses on the internal logic and structure of the code.

●​ Testers design cases to check paths, conditions, and loops.
●​ Ensures the program’s internal operations work correctly.

3. Alpha Testing

●​ Conducted internally by developers or QA staff within the organization.

●​ Done before release to catch bugs early in a controlled environment.
●​ Ensures the system works as intended before external testing.
4. Beta Testing

●​ Conducted externally by a limited group of real users outside the organization.

●​ Provides feedback on usability, performance, and unexpected issues in real‑world
conditions.
●​ Helps refine the product before full public release.

Testing ensures the software is reliable, accurate, and user‑friendly. It confirms that
features like adding expenses, all work smoothly because if the app miscalculates, users
could lose trust and stop using the app.

The student’s actions are inappropriate because she is engaging in software piracy. By
downloading Microsoft Word from an online forum, she is using an unauthorized copy that
violates the software’s licensing agreement. Sharing it with her friend makes the situation
worse, since the license is for single‑user use only and distributing it breaches copyright law.

Ensures the software meets user requirements – involving end users during development
helps confirm that the system actually solves their problems and includes the features they
need.

Ensures the software is user‑friendly – feedback from end users helps identify usability
issues early, making the application easier to navigate and more satisfying to use.
One tool that can be used during the coding process of the airline reservation app is an
Integrated Development Environment (IDE). An IDE such as Visual Studio Code provides
a workspace where developers can write, edit, and debug code efficiently.

Fixing bugs and errors – Even after launch, issues may appear when users interact with the
app in ways developers didn’t anticipate. Maintenance ensures these problems are corrected
so the app remains reliable.

Updating features and compatibility – Over time, user needs change and operating systems
are updated. Maintenance allows the app to stay user‑friendly, secure, and compatible with
new devices or software versions.
Paging is a memory management technique where processes are divided into equal‑sized
units called pages, which are then loaded into available frames in physical memory.

First student (read only): The ACL entry would grant this user read (R) permission but
deny write and delete.
Second student (read and write, no delete): The ACL entry would allow read and write
(RW) permissions but explicitly block delete.
Third student (full access): The ACL entry would grant read, write, and delete (RWD)
permissions.
A multi‑processing operating system uses multiple processors to run processes
simultaneously. The OS schedules and coordinates tasks across processors, improving speed,
efficiency, and reliability by allowing parallel execution.
(i) Switch vs Router

A switch connects devices within the same local area network (LAN) using MAC addresses,
while a router connects different networks using IP addresses.

(ii) Switch vs Hub

A switch is a smarter device that forwards data to the intended device only, while a hub is a
simple device that broadcasts data to all devices.
PAPER 2 2024
Rapid delivery of results: Agile uses short iterations (sprints), so the company can see
working features quickly instead of waiting for a long final release.​

Flexibility and adaptability: Since requirements can change, Agile allows the team to adjust
priorities and incorporate feedback during development.​

Team collaboration: Agile emphasizes communication and cross‑functional teamwork,

which suits Jim’s small, closely knit team.
A batch processing operating system works by collecting and grouping similar jobs together
and executing them sequentially without user interaction, which reduces setup time and
improves efficiency.
Memory management is important because it ensures efficient allocation, protection, and
multitasking. For example, using paging, the OS divides memory into fixed‑size pages,
which prevents fragmentation and allows processes to run smoothly even when physical
memory is limited.
OTHER TYPES OF SCHEDULING ALGORITHMS
In a relational database, a foreign key is a field (or set of fields) in one table that refers to
the primary key in another table. Its role is to link related records across tables.
PAPER 2 2023
Please Do Not Touch Sally’s Pet Alligator
OR
PAPER 2 2022
Syllabus Extra Info
 SHORTER VERSION

LONGER VERSION (everything explained)