Enhance your performance in BSCS courses at KASB Institute of Technology in Karachi with effective study notes. Learn tips on creating and organizing study materials for success., studying BSCS at KASB Institute of Technology in Karachi can be a rewarding experience with the right approach and dedication. By following the study notes provided in this article and utilizing available resources, you can enhance your learning and academic performance in the BSCS program. Remember, consistency and hard work are key to achieving success in your academic journey at KASB Institute of Technology.

Study Notes BSCS at KASB Institute of Technology, Karachi.

Programming Fundamentals (Core) – Comprehensive Study Notes

Course Overview

PART 1: Introduction to Programming

1.1 What is Programming?

Programming (also called coding) is the process of designing and writing instructions (code) that a computer can execute to perform specific tasks or solve problems. A set of instructions is called a program or software.

Levels of Programming Languages:

1.2 The Programming Process

1.3 Algorithms and Flowcharts

Algorithm: Finite sequence of well-defined, unambiguous instructions to solve a problem.

Example Algorithm (Find Average of Three Numbers):

Step 1: Start
Step 2: Input three numbers A, B, C
Step 3: Compute Sum = A + B + C
Step 4: Compute Average = Sum / 3
Step 5: Output Average
Step 6: End

Flowchart Symbols:

PART 2: Basic Programming Concepts

2.1 Variables and Constants

Variable: Named memory location that can store a value that may change during program execution.

# Python
count = 10          # integer variable
price = 49.99       # float variable
name = "Alice"      # string variable
is_valid = True     # boolean variable

Constant: Named value that cannot change after initialization.

// C
#define PI 3.14159
const int MAX_USERS = 100;

Naming Rules (most languages):

• Must start with letter (a-z, A-Z) or underscore (_)

• Can contain letters, digits, underscores (no spaces)

• Cannot use reserved keywords (if, while, return, etc.)

• Case-sensitive (Count ≠ count)

2.2 Data Types

2.3 Operators

Arithmetic Operators:

Relational (Comparison) Operators:

Logical Operators:

2.4 Type Conversion

Implicit (Automatic) Conversion: Compiler automatically converts one type to another.

int a = 10;
double b = a;     // int → double (10.0)

Explicit (Type Casting): Programmer manually converts type.

// C
double x = 7.5;
int y = (int)x;   // y = 7 (truncates)

// Python
x = 7.5
y = int(x)        # y = 7

PART 3: Control Structures

Control structures determine the order in which statements are executed.

3.1 Sequential

Statements execute in order (top to bottom). This is the default.

a = 5
b = 10
c = a + b
print(c)          # Outputs: 15

3.2 Selection (Conditional)

if Statement:

// C
if (condition) {
    // executed if condition is true
}

# Python
if condition:
    # executed if condition is true

if-else Statement:

if (condition) {
    // executed if condition is true
} else {
    // executed if condition is false
}

if-else if-else (Ladder):

if (score >= 90) {
    grade = 'A';
} else if (score >= 80) {
    grade = 'B';
} else if (score >= 70) {
    grade = 'C';
} else {
    grade = 'F';
}

Switch Statement (C/C++/Java):

switch (day) {
    case 1:
        printf("Monday");
        break;
    case 2:
        printf("Tuesday");
        break;
    default:
        printf("Invalid day");
}

Note: Python does not have a switch statement (if-elif used instead; match-case in Python 3.10+).

3.3 Iteration (Loops)

while Loop: Repeats while condition is true (zero or more times).

# Python
count = 1
while count <= 5:
    print(count)
    count += 1

// C
int count = 1;
while (count <= 5) {
    printf("%d", count);
    count++;
}

do-while Loop (C/C++): Executes at least once (condition checked at end).

int count = 1;
do {
    printf("%d", count);
    count++;
} while (count <= 5);

for Loop: Combines initialization, condition, and increment in one line.

# Python
for i in range(1, 6):   # i = 1,2,3,4,5
    print(i)

// C
for (int i = 1; i <= 5; i++) {
    printf("%d", i);
}

Nested Loops: Loop inside another loop.

for i in range(1, 4):        # outer loop
    for j in range(1, 4):    # inner loop
        print(f"{i},{j}")

3.4 Jump Statements

PART 4: Functions (Modular Programming)

4.1 What is a Function?

Function: Reusable block of code that performs a specific task. Benefits: modularity, reusability, easier debugging, reduced code duplication.

4.2 Function Components

4.3 Function Examples

C:

#include <stdio.h>

// Function declaration (prototype)
int add(int a, int b);

int main() {
    int result = add(5, 3);   // function call
    printf("Sum: %d", result);
    return 0;
}

// Function definition
int add(int a, int b) {
    return a + b;
}

Python:

def add(a, b):
    """Returns sum of a and b"""
    return a + b

result = add(5, 3)
print(f"Sum: {result}")

4.4 Parameter Passing Mechanisms

4.5 Variable Scope

int global = 100;        // global variable

void func() {
    static int count = 0;    // static variable (retains value)
    int local = 10;          // local variable
    count++;
    global++;
}

4.6 Recursion

Recursion: Function that calls itself (directly or indirectly).

Recursion vs. Iteration:

Example (Factorial):

def factorial(n):
    if n <= 1:          # base case
        return 1
    else:               # recursive case
        return n * factorial(n - 1)

# factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

Example (Fibonacci):

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

PART 5: Arrays and Strings

5.1 Arrays (One-Dimensional)

Array: Collection of elements of same data type stored in contiguous memory locations.

C Array Declaration and Initialization:

int numbers[5];                    // declaration (uninitialized)
int scores[5] = {85, 90, 78, 92, 88};  // declaration + initialization
int values[] = {1, 2, 3};          // size inferred (3)

// Accessing elements (0-indexed)
scores[0] = 95;      // first element
int x = scores[2];   // third element (78)

Common Array Operations (C):

int arr[5] = {10, 20, 30, 40, 50};

// Traversal
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);    // Output: 10 20 30 40 50
}

// Sum
int sum = 0;
for (int i = 0; i < 5; i++) {
    sum += arr[i];
}   // sum = 150

// Search (linear)
int target = 30;
int found = 0;
for (int i = 0; i < 5; i++) {
    if (arr[i] == target) {
        found = 1;
        printf("Found at index %d", i);
        break;
    }
}

Python Lists (dynamic arrays):

numbers = [10, 20, 30, 40, 50]    # list (size can change)
numbers.append(60)                  # add element
numbers.insert(2, 25)               # insert at index 2
numbers.remove(40)                  # remove by value
print(numbers[1])                   # access element (20)

5.2 Arrays: Two-Dimensional (Matrices)

// C – 3 rows, 4 columns
int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// Access element
int val = matrix[1][2];   // row 1, column 2 = 7

// Traversal
for (int i = 0; i < 3; i++) {          // rows
    for (int j = 0; j < 4; j++) {      // columns
        printf("%d ", matrix[i][j]);
    }
    printf("\n");
}

# Python (list of lists)
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

print(matrix[1][2])     # 7

5.3 Strings

C Strings: Null-terminated character arrays.

char str1[20] = "Hello";           // automatic null terminator '\0'
char str2[] = "World";
char str3[6] = {'H', 'e', 'l', 'l', 'o', '\0'};   // explicit null terminator

// String functions (string.h)
#include <string.h>

strlen(str1);          // returns length (5 – excludes '\0')
strcpy(dest, src);     // copies src to dest
strcat(dest, src);     // appends src to dest
strcmp(str1, str2);    // compares (0 if equal)

Python Strings:

message = "Hello World"
print(len(message))          # length
print(message[0])            # first character ('H')
print(message[6:11])         # slicing ("World")
print(message.upper())       # "HELLO WORLD"
print(message.split())       # ['Hello', 'World']

PART 6: Pointers (C/C++ specific)

6.1 Pointer Basics

Pointer: Variable that stores memory address of another variable.

int num = 42;          // ordinary integer variable
int *ptr = #       // pointer to integer (stores address of num)

printf("%d", num);     // prints 42 (value)
printf("%p", &num);    // prints address of num
printf("%p", ptr);     // prints same address
printf("%d", *ptr);    // dereference: prints 42 (value at that address)

Pointer Operators:

6.2 Pointers and Arrays

Array name acts as pointer to first element.

int arr[5] = {10, 20, 30, 40, 50};

// These are equivalent:
arr[0] == *(arr + 0)   // 10
arr[1] == *(arr + 1)   // 20
arr[2] == *(arr + 2)   // 30

// Pointer arithmetic
int *p = arr;          // points to arr[0]
p++;                   // now points to arr[1]

6.3 Dynamic Memory Allocation (C)

Allocate memory at runtime (heap).

#include <stdlib.h>

// malloc – allocates memory (uninitialized)
int *ptr = (int*)malloc(5 * sizeof(int));   // array of 5 ints

// calloc – allocates and initializes to zero
int *ptr2 = (int*)calloc(5, sizeof(int));   // all zeros

// realloc – resize previously allocated memory
ptr = (int*)realloc(ptr, 10 * sizeof(int)); // now 10 ints

// free – deallocate memory
free(ptr);

6.4 Pointers to Functions

#include <stdio.h>

int add(int a, int b) {
    return a + b;
}

int main() {
    int (*funcPtr)(int, int) = add;   // pointer to function
    int result = funcPtr(5, 3);       // call through pointer (result = 8)
    return 0;
}

PART 7: Basic File I/O

7.1 File Operations (C)

File Opening Modes:

Example (Write to File):

#include <stdio.h>

int main() {
    FILE *fp = fopen("data.txt", "w");
    if (fp == NULL) {
        printf("Error opening file!");
        return 1;
    }
    fprintf(fp, "Hello World\n");
    fprintf(fp, "Number: %d\n", 42);
    fclose(fp);
    return 0;
}

Example (Read from File):

FILE *fp = fopen("data.txt", "r");
if (fp == NULL) {
    printf("File not found!");
    return 1;
}
char buffer[100];
while (fgets(buffer, 100, fp) != NULL) {
    printf("%s", buffer);
}
fclose(fp);

7.2 File Operations (Python)

# Write to file
with open("data.txt", "w") as file:
    file.write("Hello World\n")
    file.write(f"Number: {42}\n")

# Read from file
with open("data.txt", "r") as file:
    content = file.read()          # entire file
    # or
    for line in file:
        print(line.strip())        # line by line

PART 8: Error Types and Debugging

8.1 Types of Errors

8.2 Debugging Techniques

PART 9: Introduction to Data Structures

9.1 What are Data Structures?

Data structure: Way of organizing and storing data in a computer so it can be accessed and modified efficiently.

9.2 Basic Data Structures

9.3 Stack Implementation (C)

#define MAX 100
int stack[MAX];
int top = -1;

void push(int value) {
    if (top >= MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = value;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

int peek() {
    return stack[top];
}

int isEmpty() {
    return top == -1;
}

9.4 Queue Implementation (C – Circular)

#define MAX 100
int queue[MAX];
int front = 0;
int rear = -1;
int count = 0;

void enqueue(int value) {
    if (count == MAX) {
        printf("Queue Full\n");
        return;
    }
    rear = (rear + 1) % MAX;
    queue[rear] = value;
    count++;
}

int dequeue() {
    if (count == 0) {
        printf("Queue Empty\n");
        return -1;
    }
    int value = queue[front];
    front = (front + 1) % MAX;
    count--;
    return value;
}

Summary Table for Revision

1. Data Types (C)

2. Loop Comparison

3. Memory Sections (C)

Glossary of Key Terms

Sample Pseudocode Reference

Input/Output:

INPUT variable
OUTPUT "message", variable

Assignment:

variable ← expression

Conditional:

IF condition THEN
    statements
ELSE IF condition THEN
    statements
ELSE
    statements
END IF

Looping:

WHILE condition DO
    statements
END WHILE

FOR variable ← start TO end DO
    statements
END FOR

Function:

FUNCTION name(parameters)
    statements
    RETURN value
END FUNCTION

Recommended Textbooks

1. Kernighan, B.W. & Ritchie, D.M. The C Programming Language (2nd ed.). Prentice Hall. (“K&R C” – classic reference)

2. Deitel, P.J. & Deitel, H.M. C: How to Program. Pearson.

3. Downey, A. Think Python (2nd ed.). O’Reilly. (Free online)

4. Cormen, T.H. et al. Introduction to Algorithms (4th ed.). MIT Press. (Data structures and algorithms)

5. Sedgewick, R. & Wayne, K. Algorithms (4th ed.). Addison-Wesley. (Java; algorithms focus)

These notes provide a comprehensive foundation for an introductory programming course. Mastery requires practice: write code regularly, debug systematically, and trace through examples step-by-step.

Study Notes: Application of Information and Communication Technologies (ICT) in General Education

1. What is ICT in Education?

Information and Communication Technology (ICT) refers to all technologies used to handle telecommunications, broadcast media, intelligent building management systems, audiovisual processing, and network-based control and monitoring functions.

In education, ICT means using digital tools, hardware, software, and internet-based resources to enhance teaching, learning, and administration.

Key Components of ICT

2. Rationale for Using ICT in General Education

Why integrate ICT?

3. Major Applications of ICT in the Classroom

A. Teaching & Instruction

B. Learning Management Systems (LMS)

C. Assessment & Feedback

D. Communication & Collaboration

E. Content Creation by Students

F. Administrative Applications

4. ICT Integration Models (Frameworks)

SAMR Model (Puentedura)

Describes levels of technology integration:

TPACK Framework (Mishra & Koehler)

Three knowledge domains overlap:

• Technological Knowledge (TK)

• Pedagogical Knowledge (PK)

• Content Knowledge (CK)

Effective teaching requires intersection of all three (TPACK).

5. Benefits of ICT in General Education

6. Challenges & Limitations

7. ICT Tools Categorized by Educational Goal

8. Best Practices for ICT Integration

DOs

• ✅ Align technology with learning objectives (not tech for tech’s sake).

• ✅ Provide clear instructions and technical support.

• ✅ Use active learning strategies (create, collaborate, debate).

• ✅ Ensure accessibility (closed captions, screen reader compatibility).

• ✅ Teach digital citizenship (privacy, copyright, online safety).

• ✅ Start small; scale successful tools.

DON’Ts

• ❌ Assume students already know how to use educational tech.

• ❌ Replace teacher with screens entirely.

• ❌ Ignore data privacy laws.

• ❌ Overload students with too many platforms.

• ❌ Neglect offline, hands-on activities.

9. ICT in Different Subject Areas (Examples)

10. Emerging Trends in ICT for Education

11. Sample Lesson Integration (Example)

Subject: Grade 7 Geography – Climate Change
ICT Tools Used: Google Slides, Padlet, PhET simulation (Greenhouse Effect), Flip (video responses)

Lesson Flow:

1. Engage: Watch a 3-min video on climate change (YouTube).

2. Explore: Use PhET simulation – students adjust CO₂ levels and observe temperature change.

3. Explain: Small group discussion on Padlet – share observations.

4. Elaborate: Create a 90-second Flip video explaining one cause and one solution.

5. Evaluate: Teacher rubric based on science accuracy and presentation quality.

12. Glossary of Key ICT-in-Education Terms

Summary – Key Takeaways for Revision

1. ICT in education includes hardware, software, networks, and digital content.

2. Major applications: teaching, LMS, assessment, communication, content creation, administration.

3. Two key frameworks: SAMR (Substitution to Redefinition) and TPACK (Tech + Pedagogy + Content).

4. Benefits: personalization, motivation, access, immediate feedback.

5. Challenges: digital divide, training, distraction, cost, privacy.

6. Best practices: align with goals, teach digital citizenship, balance online/offline.

7. Emerging trends: AI, VR/AR, learning analytics, OER.

Revision Questions

1. What is the difference between substitution and redefinition in the SAMR model?

2. List three specific ICT tools for formative assessment.

3. Explain two strategies to overcome the digital divide in a rural school.

4. How can a teacher use TPACK to plan a science lesson on the water cycle?

5. Name one benefit and one challenge of using AI tutors.

DISCRETE STRUCTURES – Complete Study Notes

PART 1: PROPOSITIONAL LOGIC

1.1 Propositions and Logical Operators

Definition: A proposition (or statement) is a declarative sentence that is either true (T) or false (F) , but not both.

Logical operators (connectives):

1.2 Truth Tables

Truth table for basic operators (p, q ∈ {T, F}):

Key points about implication (p → q):

• Vacuous truth: When p is false, p → q is true regardless of q.

• Equivalent forms: p → q ≡ ¬p ∨ q

• Contrapositive: p → q ≡ ¬q → ¬p

• Converse: q → p (not logically equivalent)

• Inverse: ¬p → ¬q (not logically equivalent)

Example (vacuous truth): “If 2 + 2 = 5 (false), then I am the Pope (false)” — the statement is true (vacuously) because the antecedent is false, even though the consequent is also false. This seems counterintuitive but is necessary for logical consistency.

1.3 Logical Equivalences

Definition: Two compound propositions are logically equivalent (≡) if they have identical truth values for all possible truth values of their variables.

Important logical equivalences (laws):

Example (De Morgan’s Law application): “It is not true that both the sky is blue and grass is green” is equivalent to “Either the sky is not blue OR grass is not green.”

1.4 Predicate Logic (First-Order Logic)

Definition: Extends propositional logic by introducing predicates (properties of objects), quantifiers, and variables.

Domain (universe of discourse): The set of all possible values for a variable.

Negating quantifiers (De Morgan’s laws for quantifiers):

Example (negation): Let the domain be integers.

• ∀x (x > 0) → “Every integer is positive” (false)

• ¬∀x (x > 0) ≡ ∃x ¬(x > 0) ≡ ∃x (x ≤ 0) → “There exists an integer that is non-positive” (true, e.g., x = 0 or x = -1)

Nested quantifiers:

Example (order matters):

• ∀x ∃y (x + y = 0) is true for integers (for every x, choose y = -x).

• ∃y ∀x (x + y = 0) is false for integers (there is no single y that works for all x).

PART 2: SET THEORY

2.1 Basic Definitions and Notation

Definition: A set is an unordered collection of distinct objects (elements).

Notation:

• Roster form: S = {1, 2, 3, 4, 5}

• Set-builder form: S = {x | x is a positive integer less than 6}

• Element membership: a ∈ S (“a is an element of S”), a ∉ S

Special sets:

2.2 Set Operations

Universal set (U): The set of all possible elements under consideration — context-dependent.

2.3 Set Identities (Analogous to logical equivalences)

2.4 Set Relations (Subset, Superset, Equality)

Power set: P(A) = {S | S ⊆ A} — the set of all subsets of A.

• |P(A)| = 2^{|A|} (if A is finite)

Example: A = {1, 2}
P(A) = {∅, {1}, {2}, {1, 2}} (4 = 2² subsets)

Cartesian product: A × B = {(a, b) | a ∈ A ∧ b ∈ B}

• |A × B| = |A| × |B|

• A × B ≠ B × A (unless A = B or one is empty)

Example: A = {1, 2}, B = {x, y}
A × B = {(1, x), (1, y), (2, x), (2, y)}

2.5 Cardinality (Size of a Set)

PART 3: FUNCTIONS

3.1 Definition and Terminology

Definition: A function f: A → B is a relation that assigns exactly one element of B (the codomain) to each element of A (the domain).

3.2 Properties of Functions

Examples (f: ℝ → ℝ):

3.3 Inverse and Composition

Inverse function: If f: A → B is bijective, then f⁻¹: B → A exists, defined by f⁻¹(b) = a where f(a) = b.

Composition: (g ∘ f)(x) = g(f(x)), defined when f: A → B and g: B → C.

Properties of composition:

• (f ∘ g) ∘ h = f ∘ (g ∘ h) (associative)

• f ∘ g ≠ g ∘ f generally (not commutative)

• If f and g are injective, then f ∘ g is injective.

• If f and g are surjective, then f ∘ g is surjective.

• If f and g are bijective, then f ∘ g is bijective, and (f ∘ g)⁻¹ = g⁻¹ ∘ f⁻¹.

PART 4: RELATIONS

4.1 Binary Relations

Definition: A binary relation R from set A to set B is a subset of A × B. If (a, b) ∈ R, we write a R b.

Domain of R: dom(R) = {a ∈ A | ∃b ∈ B such that (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃a ∈ A such that (a, b) ∈ R}

4.2 Relations on a Set (A → A)

Definition: A relation on a set A is a subset of A × A.

4.3 Equivalence Relations

Definition: A relation R on A is an equivalence relation if it is:

1. Reflexive

2. Symmetric

3. Transitive

Equivalence classes: For each a ∈ A, [a] = {x ∈ A | x R a} is the equivalence class of a.

• Partition of A into disjoint equivalence classes.

Example: Let A = ℤ, define a R b if a ≡ b (mod 3) (i.e., a – b divisible by 3).

• Reflexive: a – a = 0 divisible by 3.

• Symmetric: if a – b divisible by 3, then b – a divisible by 3.

• Transitive: if a – b and b – c divisible by 3, then a – c divisible by 3.
  Equivalence classes: [0] = {…, -3, 0, 3, 6, …}, [1] = {…, -2, 1, 4, 7, …}, [2] = {…, -1, 2, 5, 8, …}. Partition of ℤ into 3 classes.

4.4 Partial Orders

Definition: A relation R on A is a partial order if it is:

1. Reflexive

2. Antisymmetric

3. Transitive

Notation: Often ≤ is used for partial orders.

Hasse diagram: Graphical representation of a partial order, omitting reflexive and transitive edges.

Comparability: a and b are comparable if a ≤ b or b ≤ a.

Total order (chain): A partial order where every pair of elements is comparable.

Example: (ℤ⁺, |) where a | b means “a divides b”.

• Reflexive: a | a.

• Antisymmetric: if a | b and b | a, then a = b (for positive integers).

• Transitive: if a | b and b | c, then a | c.
  Not a total order because 2 and 3 are not comparable (2 ∤ 3, 3 ∤ 2).

Maximal, minimal, greatest, least elements:

PART 5: COMBINATORICS

5.1 Basic Counting Principles

Sum rule: If a task can be done in m ways OR in n ways (with no overlap), total = m + n.

Product rule: If a task requires doing subtask 1 in m ways AND subtask 2 in n ways, total = m × n.

Example (product rule): How many 2-digit numbers are there? First digit: 1-9 (9 ways), second digit: 0-9 (10 ways). Total = 9 × 10 = 90.

Inclusion-Exclusion Principle (for two sets): |A ∪ B| = |A| + |B| – |A ∩ B|

Generalized (for three sets):
|A ∪ B ∪ C| = |A| + |B| + |C| – |A∩B| – |A∩C| – |B∩C| + |A∩B∩C|

5.2 Permutations (Order matters)

5.3 Combinations (Order does NOT matter)

Properties of C(n,r):

5.4 Binomial Coefficients and Pascal’s Triangle

Pascal’s Triangle (rows 0-5):

Row 0:              1
Row 1:            1   1
Row 2:          1   2   1
Row 3:        1   3   3   1
Row 4:      1   4   6   4   1
Row 5:    1   5  10  10   5   1

Each entry = sum of two above: C(n,r) = C(n-1, r-1) + C(n-1, r)

5.5 Pigeonhole Principle

Simple form: If n items are placed into m boxes and n > m, then at least one box contains at least 2 items.

Generalized form: If n items are placed into m boxes, then at least one box contains at least ⌈n/m⌉ items.

Example: Among any 13 people, at least 2 were born in the same month (12 months, 13 people → ⌈13/12⌉ = 2).

Example (more advanced): Show that any set of 10 integers from {1,…,100} contains two subsets with equal sum. There are 2¹⁰ – 1 = 1023 non-empty subsets, but possible sums range from 1 to 100+99+…+91 = 955. Pigeonhole: 1023 subsets → at least two with same sum.

PART 6: GRAPH THEORY

6.1 Basic Definitions

Definition: A graph G = (V, E) consists of:

• V: set of vertices (nodes)

• E: set of edges (pairs of vertices)

Types of graphs:

6.2 Graph Terminology

Handshaking theorem: Σ_{v∈V} deg(v) = 2|E|

• Corollary: The number of vertices of odd degree is even.

6.3 Graph Isomorphism

Definition: Two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic if there exists a bijection f: V₁ → V₂ such that {u,v} ∈ E₁ iff {f(u), f(v)} ∈ E₂. (Edge-preserving bijection).

Invariants for non-isomorphism (properties preserved under isomorphism):

• Number of vertices

• Number of edges

• Degree sequence (sorted list of degrees)

• Number of cycles of each length

• Connectivity properties

Example: Are G₁ (square with diagonal) and G₂ (K₄ minus one edge) isomorphic? G₁ has a vertex of degree 2 and two vertices of degree 3; G₂ has two vertices of degree 2 and two of degree 3. Wait, check carefully — best to test by exhaustive mapping.

6.4 Eulerian and Hamiltonian Paths

Example (Bridges of Königsberg): Four land masses, seven bridges. Graph has 4 vertices with degrees 3,3,3,5 (all odd). No Eulerian circuit or trail (impossible to cross each bridge exactly once).

6.5 Planar Graphs

Definition: A graph is planar if it can be drawn in the plane without edge crossings.

Euler’s formula for connected planar graphs: V – E + F = 2, where F = number of faces (including the unbounded outer face).

Corollaries:

• For planar graphs with V ≥ 3: E ≤ 3V – 6

• For bipartite planar graphs: E ≤ 2V – 4

Non-planar graphs: K₅ (complete graph on 5 vertices) and K₃,₃ (complete bipartite 3×3) are non-planar (Kuratowski’s theorem: a graph is planar iff it contains no subdivision of K₅ or K₃,₃).

6.6 Graph Coloring

Definition: A k-coloring of a graph assigns one of k colors to each vertex such that no two adjacent vertices share the same color.

Chromatic number χ(G): Minimum number of colors needed to color G.

Famous theorem (Four Color Theorem): Every planar graph is 4-colorable (χ(G) ≤ 4).

PART 7: TREES

7.1 Definition and Properties

Definition: A tree is a connected acyclic undirected graph.

Properties of trees:

7.2 Rooted Trees

Definition: A rooted tree is a tree with one vertex designated as the root.

Terminology:

Binary tree: Each node has at most 2 children (left and right).

Full binary tree: Each node has 0 or 2 children.

Complete binary tree: All levels filled except possibly last, which is filled left to right.

7.3 Tree Traversals

7.4 Spanning Trees

Definition: A spanning tree of a connected graph G is a subgraph that is a tree and includes all vertices of G.

Minimum spanning tree (MST): Spanning tree with minimum total edge weight (for weighted graphs).

Algorithms to find MST:

PART 8: NUMBER THEORY (BASICS)

8.1 Divisibility and Modular Arithmetic

Definition: a | b (a divides b) if ∃ integer k such that b = a·k.

Division algorithm: For integers a and positive integer d, there exist unique integers q (quotient) and r (remainder) such that:
a = d·q + r, where 0 ≤ r < d.

Modular arithmetic: a ≡ b (mod m) iff m | (a – b).

8.2 Greatest Common Divisor (GCD)

Definition: gcd(a, b) = largest positive integer d such that d | a and d | b.

Euclidean algorithm:

1. Let a₁ = max(a,b), b₁ = min(a,b)

2. Compute a₁ = b₁·q + r (0 ≤ r < b₁)

3. If r = 0, gcd = b₁

4. Else set new a₂ = b₁, b₂ = r, repeat

Example: Find gcd(252, 105)
252 = 105·2 + 42
105 = 42·2 + 21
42 = 21·2 + 0
gcd = 21

Extended Euclidean algorithm: Finds integers x, y such that ax + by = gcd(a, b).

8.3 Prime Numbers

Definition: p > 1 is prime if its only positive divisors are 1 and p.

Fundamental theorem of arithmetic: Every integer greater than 1 can be uniquely expressed as a product of primes (up to order).

Infinitude of primes (Euclid’s proof): Assume finite list p₁,…,pₙ. Consider N = p₁·p₂·…·pₙ + 1. N is either prime (not in list) or divisible by a prime not in list. Contradiction. Therefore infinite primes.

8.4 Modular Inverses and Cryptography (RSA motivation)

Definition: a has an inverse modulo m if ∃ a⁻¹ such that a·a⁻¹ ≡ 1 (mod m). Exists iff gcd(a, m) = 1.

Fermat’s little theorem: If p is prime and a is not divisible by p, then a^{p-1} ≡ 1 (mod p).

PART 9: PROOF TECHNIQUES

9.1 Direct Proof

Structure: Assume P is true. Use logical steps to deduce Q is true. (P → Q)

Example: Prove: If n is even, then n² is even.
Proof: If n is even, then n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²), which is even. ∎

9.2 Proof by Contraposition

Structure: Prove ¬Q → ¬P instead of P → Q (logically equivalent).

Example: Prove: If n² is odd, then n is odd.
Proof by contraposition: Assume n is even (¬Q). Then n = 2k, n² = 4k² = 2(2k²), which is even (¬P). Therefore if n² is odd, n cannot be even, so n is odd. ∎

9.3 Proof by Contradiction

Structure: Assume P ∧ ¬Q. Derive a contradiction (R ∧ ¬R). Therefore P → Q is true.

Example: Prove √2 is irrational.
Proof: Assume √2 is rational. Then √2 = a/b in lowest terms. Squaring: 2 = a²/b² → a² = 2b². Thus a² is even → a is even (a = 2k). Then (2k)² = 2b² → 4k² = 2b² → 2k² = b² → b² even → b even. But then a and b both even, contradicting “in lowest terms.” Therefore √2 is irrational

Object Oriented Programming (Core) – Complete Study Notes

Course Overview

Object Oriented Programming (OOP) is a programming paradigm that organizes software design around objects rather than functions and logic. An object is a self-contained entity that contains both data (attributes/properties) and methods (functions/procedures) that operate on that data. OOP aims to increase flexibility, maintainability, and reusability in software development.

Core Languages: Java, C++, Python, C#, JavaScript, PHP

Prerequisites: Basic programming concepts (variables, loops, conditionals, functions), familiarity with at least one programming language.

PART 1: FUNDAMENTAL CONCEPTS

1.1 What is Object Oriented Programming?

Definition: OOP is a programming methodology based on the concept of “objects” that contain data (fields/attributes) and code (methods/procedures) that manipulate that data. Objects are instances of classes, which act as blueprints or templates.

Procedural vs. Object Oriented Programming:

1.2 The Four Pillars of OOP

Mnemonic: “A PIE” (Abstraction, Polymorphism, Inheritance, Encapsulation) – but standard order often presented as: Encapsulation, Inheritance, Polymorphism, Abstraction . Any order is acceptable if you understand each concept.

PART 2: CLASSES AND OBJECTS

2.1 Class Definition

Definition: A class is a blueprint or template for creating objects. It defines the structure (data members) and behavior (member functions/methods) that objects of that class will have.

Analogy:

• Class = Cookie cutter (blueprint)

• Object = Cookie (instance created from the cutter)

2.2 Syntax Examples (Multiple Languages)

Java Example:

public class Car {
    // Data members (attributes/fields) - Encapsulation through private access
    private String brand;
    private String model;
    private int year;
    
    // Constructor (called when object is created)
    public Car(String brand, String model, int year) {
        this.brand = brand;
        this.model = model;
        this.year = year;
    }
    
    // Method (behavior)
    public void startEngine() {
        System.out.println(brand + " " + model + " engine started.");
    }
    
    // Getter (accessor)
    public String getBrand() {
        return brand;
    }
    
    // Setter (mutator)
    public void setBrand(String brand) {
        this.brand = brand;
    }
}

// Creating an object (instance of Car class)
Car myCar = new Car("Toyota", "Camry", 2023);
myCar.startEngine();  // Output: Toyota Camry engine started.

C++ Example:

class Car {
private:
    string brand;
    string model;
    int year;
    
public:
    // Constructor
    Car(string brand, string model, int year) {
        this->brand = brand;
        this->model = model;
        this->year = year;
    }
    
    void startEngine() {
        cout << brand << " " << model << " engine started." << endl;
    }
};

Car myCar("Honda", "Civic", 2022);
myCar.startEngine();

Python Example:

class Car:
    def __init__(self, brand, model, year):   # Constructor
        self.brand = brand      # Public attribute (by convention)
        self.model = model
        self.__year = year      # Name mangling for private attribute (not truly private)
    
    def start_engine(self):     # Method
        print(f"{self.brand} {self.model} engine started.")
    
    # Getter (property)
    @property
    def year(self):
        return self.__year
    
    # Setter
    @year.setter
    def year(self, value):
        if value > 1885:   # First car invented ~1886
            self.__year = value

my_car = Car("Tesla", "Model 3", 2023)
my_car.start_engine()

2.3 Object Lifecycle

2.4 Constructor Types

Constructor Chaining (Calling one constructor from another):

• Java: this(...) must be first statement

• C++: Initializer list : Car(brand, model); or delegating constructors (C++11)

• Python: __init__ cannot directly call another __init__; use class methods or composition

• C#: this(...) similar to Java

2.5 Destructors and Garbage Collection

Rule of Three (C++): If a class defines a destructor, copy constructor, or copy assignment operator, it should define all three (or explicitly delete them). This ensures proper resource management (especially for dynamic memory, file handles, network sockets). (Updated to Rule of Five in C++11: move constructor and move assignment added.)

PART 3: ENCAPSULATION (DATA HIDING)

3.1 Access Modifiers (Access Specifiers)

3.2 Language-Specific Access Modifiers

3.3 Getters and Setters (Accessors and Mutators)

Purpose: Control access to private data members; validate input before modification; maintain invariants.

Java Example:

public class BankAccount {
    private double balance;
    
    // Getter (accessor)
    public double getBalance() {
        return balance;
    }
    
    // Setter (mutator) with validation
    public void setBalance(double balance) {
        if (balance >= 0) {
            this.balance = balance;
        } else {
            throw new IllegalArgumentException("Balance cannot be negative.");
        }
    }
    
    // Alternative: Provide behavior instead of getter/setter
    public void deposit(double amount) {
        if (amount > 0) {
            this.balance += amount;
        }
    }
}

When to use getters/setters:

• Use getter/setter when you need validation, logging, or change notification (JavaBeans convention)

• Avoid getter/setter for trivial fields if internal representation is unlikely to change (direct field access can be allowed within the same class) – Some OOP purists argue getters/setters break encapsulation anyway because they expose internal data structure. Use behavior methods instead.

Rule of thumb: Expose behavior, not data. Ask “what does the object DO?” not “what data does it HOLD?”

3.4 Information Hiding Benefits

PART 4: INHERITANCE

4.1 Definition and Terminology

Inheritance: A mechanism where a new class (derived/child/subclass) is created from an existing class (base/parent/superclass), inheriting its attributes and methods.

Terminology:

• Base class (parent class, superclass): The class being inherited from

• Derived class (child class, subclass): The new class that inherits from the base class

• “IS-A” relationship: Inheritance should model “is-a” (a Dog is an Animal; a Car is a Vehicle)

• “HAS-A” relationship: Composition – a Car has an Engine (not inheritance)

4.2 Syntax Examples

Java:

// Base class (Parent)
public class Animal {
    protected String name;
    
    public Animal(String name) {
        this.name = name;
    }
    
    public void eat() {
        System.out.println(name + " is eating.");
    }
    
    public void sleep() {
        System.out.println(name + " is sleeping.");
    }
}

// Derived class (Child)
public class Dog extends Animal {
    private String breed;
    
    public Dog(String name, String breed) {
        super(name);   // Call parent constructor (must be first statement)
        this.breed = breed;
    }
    
    // Override parent method (polymorphism)
    @Override
    public void eat() {
        System.out.println(name + " the dog is eating kibble.");
    }
    
    // New method specific to Dog
    public void bark() {
        System.out.println(name + " says Woof!");
    }
}

// Usage
Dog myDog = new Dog("Rex", "German Shepherd");
myDog.eat();           // Rex the dog is eating kibble. (Overridden)
myDog.sleep();         // Rex is sleeping. (Inherited)
myDog.bark();          // Rex says Woof! (Specific to Dog)

C++:

class Animal {
protected:
    string name;
public:
    Animal(string name) : name(name) {}
    virtual void eat() { cout << name << " is eating." << endl; }
    void sleep() { cout << name << " is sleeping." << endl; }
    virtual ~Animal() {} // Virtual destructor for proper cleanup
};

class Dog : public Animal {
    string breed;
public:
    Dog(string name, string breed) : Animal(name), breed(breed) {}
    void eat() override { cout << name << " the dog is eating kibble." << endl; }
    void bark() { cout << name << " says Woof!" << endl; }
};

Python:

class Animal:
    def __init__(self, name):
        self.name = name
    
    def eat(self):
        print(f"{self.name} is eating.")
    
    def sleep(self):
        print(f"{self.name} is sleeping.")

class Dog(Animal):
    def __init__(self, name, breed):
        super().__init__(name)   # Call parent constructor
        self.breed = breed
    
    def eat(self):               # Override
        print(f"{self.name} the dog is eating kibble.")
    
    def bark(self):
        print(f"{self.name} says Woof!")

4.3 Types of Inheritance