FAST UNIVERSITY

Computer Science Concepts Guide

Complete Reference for CS Admission Test Preparation
Covering: Data Structures | Algorithms | Networks | Databases | OS | Digital Logic
Chapter 1: Data Structures
Data structures are fundamental ways of organizing and storing data in a computer.
Mastery of data structures is critical for both the FAST entry test and a successful CS
career.

1.1 Arrays
An array is a collection of elements stored at contiguous memory locations.
• Fixed size: size must be defined at declaration time
• Random access: any element accessible in O(1) time using index
• Zero-indexed in most languages: first element at index 0
• 1D Array: int arr[10]; — stores 10 integers
• 2D Array (Matrix): int matrix[3][4]; — 3 rows, 4 columns
Operation Time Complexity Description
Access O(1) Direct access via index
Search O(n) Linear search (unsorted)
Insertion (end) O(1) If space available
Deletion O(n) Requires shifting elements

1.2 Linked Lists

A linked list is a linear structure where each element (node) holds data and a pointer to
the next node.
• Singly Linked List: Each node points to the next node only
• Doubly Linked List: Nodes have pointers to both next and previous nodes
• Circular Linked List: Last node points back to the first node
Advantages over arrays: Dynamic size, efficient insertions/deletions at head
Disadvantages: No random access; requires O(n) to reach the nth element

1.3 Stacks and Queues

Feature Stack Queue
Principle LIFO (Last In, First Out) FIFO (First In, First Out)
Insert Operation Push Enqueue
Remove Operation Pop Dequeue
Peek Operation Top element Front element
Real-world Use Undo/redo, call stack Print queue, scheduling
Chapter 2: Trees & Graphs
2.1 Binary Trees
A binary tree is a hierarchical structure where each node has at most two children (left
and right).
• Root: The topmost node of the tree
• Leaf: A node with no children
• Height of tree: Longest path from root to a leaf
• Depth of node: Distance from root to that node
Tree Traversals:
1. In-order (LNR): Left subtree → Root → Right subtree — gives sorted output for
BST
2. Pre-order (NLR): Root → Left → Right — used for copying trees
3. Post-order (LRN): Left → Right → Root — used for deletion
4. Level-order (BFS): Visit nodes level by level

2.2 Binary Search Tree (BST)

A BST is a binary tree where: left child < parent < right child
• Search: O(log n) average, O(n) worst case
• Insert: O(log n) average
• Delete: O(log n) average — three cases (leaf, one child, two children)
Balanced BST variants: AVL Tree, Red-Black Tree — guarantee O(log n) always

2.3 Graph Fundamentals

A graph G = (V, E) consists of vertices (V) connected by edges (E).
Term Definition
Directed Graph Edges have direction (arrows)
Undirected Graph Edges have no direction
Weighted Graph Edges have associated values/costs
Degree of Vertex Number of edges connected to it
Path Sequence of vertices connected by edges
Cycle A path that starts and ends at the same
vertex
 Connected Graph Every vertex is reachable from every other

Graph Algorithms: BFS (Breadth-First Search) and DFS (Depth-First Search) are two
fundamental graph traversal methods.
Chapter 3: Sorting & Searching Algorithms
3.1 Sorting Algorithms Comparison
Algorithm Best Case Average Worst Space Stable?
Case
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

3.2 Searching Algorithms

• Linear Search: O(n) — checks each element one by one
• Binary Search: O(log n) — requires SORTED array, uses divide and conquer
• Hashing: O(1) average — uses hash functions to map keys to positions
Binary Search Algorithm:
5. Find the middle element of the search range
6. If middle equals target → found, return index
7. If target < middle → search the left half
8. If target > middle → search the right half
9. Repeat until found or range is empty

3.3 Algorithm Analysis (Big-O Notation)

Notation Name Example
O(1) Constant Array access, hash lookup
O(log n) Logarithmic Binary search, BST operations
O(n) Linear Linear search, simple loop
O(n log n) Linearithmic Merge sort, heap sort
O(n²) Quadratic Bubble sort, nested loops
O(2ⁿ) Exponential Recursive Fibonacci, subsets
Chapter 4: Operating Systems
4.1 OS Fundamentals
An Operating System is system software that manages hardware and software
resources.
Key OS Functions:
• Process Management: Creating, scheduling, and terminating processes
• Memory Management: Allocating and deallocating RAM efficiently
• File System Management: Organizing and accessing data on storage
• Device Management: Communication between hardware and software
• Security & Protection: Controlling access to system resources

4.2 Process Scheduling Algorithms

Algorithm Description Advantage
FCFS First Come First Served — processes in Simple to implement
arrival order
SJF Shortest Job First — shortest burst time Minimum average wait time
runs first
Round Robin Each process gets a fixed time quantum Fair for all processes
Priority Highest priority process runs first Important tasks get CPU first
SRTF Preemptive version of SJF Optimal for average wait time

4.3 Memory Management

• RAM (Primary Memory): Fast, volatile — CPU accesses directly
• Virtual Memory: Uses hard disk as extended RAM
• Paging: Divides memory into fixed-size pages — eliminates external
fragmentation
• Segmentation: Divides memory into variable-size logical segments
• Page Fault: When a page is not in RAM and must be loaded from disk
• Thrashing: Excessive paging leading to performance degradation
Chapter 5: Computer Networks
5.1 OSI Model (7 Layers)
Layer Number Key Protocols/Function
Physical 1 Bits, cables, hubs, electrical signals
Data Link 2 MAC address, Ethernet, switches, framing
Network 3 IP address, routers, routing (IP, ICMP)
Transport 4 TCP, UDP — end-to-end communication
Session 5 Establishing, maintaining sessions
Presentation 6 Encryption, compression, data formatting
Application 7 HTTP, FTP, SMTP, DNS — user interface

5.2 TCP vs UDP

Feature TCP UDP
Connection Connection-oriented Connectionless
Reliability Guaranteed delivery No guarantee
Speed Slower (overhead) Faster
Order Maintains packet order No ordering
Use Cases HTTP, Email, FTP Video streaming, DNS, VoIP
Header Size 20 bytes minimum 8 bytes

5.3 IP Addressing
• IPv4: 32-bit address (e.g., [Link]) — about 4.3 billion unique addresses
• IPv6: 128-bit address — 340 undecillion unique addresses
• Subnet Mask: Defines network and host portions of an IP address
• DHCP: Automatically assigns IP addresses to devices on a network
• DNS: Converts domain names to IP addresses (e.g., [Link] →
[Link])
Chapter 6: Database Management Systems
6.1 RDBMS Concepts
A Relational Database Management System stores data in tables (relations) with rows
and columns.
• Table: Collection of related data in rows and columns
• Primary Key: Uniquely identifies each row in a table — cannot be NULL
• Foreign Key: Links two tables — references the primary key of another table
• Index: Data structure that speeds up retrieval at the cost of storage
• View: Virtual table based on a SQL query result
• Normalization: Process of organizing tables to reduce redundancy

6.2 SQL Fundamentals

SQL (Structured Query Language) is used to interact with relational databases.
SQL Command Type Purpose
SELECT DQL Retrieve data from tables
INSERT DML Add new rows to a table
UPDATE DML Modify existing records
DELETE DML Remove rows from a table
CREATE TABLE DDL Create a new table
DROP TABLE DDL Delete a table permanently
GRANT / REVOKE DCL Control access permissions

6.3 Normalization Forms

10. 1NF (First Normal Form): No repeating groups, atomic values in each cell
11. 2NF (Second Normal Form): 1NF + No partial dependency on composite primary
key
12. 3NF (Third Normal Form): 2NF + No transitive dependency
13. BCNF (Boyce-Codd Normal Form): Stricter version of 3NF
Chapter 7: Digital Logic & Number Systems
7.1 Number Base Conversions
Decimal Binary (Base 2) Octal (Base 8) Hexadecimal (Base
16)
0 0000 0 0
5 0101 5 5
8 1000 10 8
10 1010 12 A
15 1111 17 F
16 10000 20 10

7.2 Logic Gates

• AND Gate: Output is 1 only if ALL inputs are 1
• OR Gate: Output is 1 if AT LEAST ONE input is 1
• NOT Gate (Inverter): Output is opposite of input
• NAND Gate: NOT-AND — output is 0 only when all inputs are 1
• NOR Gate: NOT-OR — output is 1 only when all inputs are 0
• XOR Gate: Output is 1 when inputs are DIFFERENT
• XNOR Gate: Output is 1 when inputs are SAME
NAND and NOR are called Universal Gates — any logic circuit can be built using only
NAND or only NOR gates.

Chapter 8: CS Exam Tips & Career Paths

8.1 Key CS Careers at FAST
• Software Engineer: Designing and developing software systems
• Data Scientist: Analyzing large datasets for insights and predictions
• Network Engineer: Designing and maintaining computer networks
• Database Administrator: Managing and optimizing database systems
• Systems Analyst: Bridging business requirements with technical solutions
• AI/ML Engineer: Building intelligent systems and machine learning models
8.2 Study Priority for CS Entry Test
14. Data Structures (Arrays, Linked Lists, Trees, Graphs) — High Priority
15. Algorithm complexity and sorting — High Priority
16. Operating Systems basics — Medium Priority
17. Networking OSI model and protocols — Medium Priority
18. Database SQL and normalization — Medium Priority
19. Digital logic and number systems — Low-Medium Priority

FAST CS graduates are among the most sought-after in Pakistan's tech industry.
Work hard and stay consistent!