AB
      00  01  11  10
C=0 | 0   1   1   0
C=1 | 1   1   0   0

#include <iostream>  
using namespace std;



int main()            
{
    
    
    return 0;         
}

const int MAX_SIZE = 100;
#define PI 3.14159  

#include <iostream>
using namespace std;


cout << "Hello, World!" << endl;
cout << "Value: " << variable << endl;


int age;
cin >> age;

#include <stdio.h>

printf("Value: %d", variable);
scanf("%d", &variable);

double x = 3.14;
int y = (int)x;  
int z = static_cast<int>(x);  

if (condition) {
    
} else {
    
}

if (condition1) {
    
} else if (condition2) {
    
} else {
    
}

switch (expression) {
    case value1:
        
        break;
    case value2:
        
        break;
    default:
        
}

variable = (condition) ? value_if_true : value_if_false;

do {
    
} while (condition);

for (initialization; condition; increment) {
    
}

for (data_type variable : array/container) {
    
}

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        if (i == j) {
            cout << "*";
        } else {
            cout << " ";
        }
    }
    cout << endl;
}

return_type function_name(parameter_list) {
    
    return value;  
}

return_type function_name(parameter_list);

function_name(arguments);

void swapByValue(int a, int b) {       
    int temp = a; a = b; b = temp;
}

void swapByReference(int &a, int &b) {  
    int temp = a; a = b; b = temp;
}

void swapByPointer(int *a, int *b) {     
    int temp = *a; *a = *b; *b = temp;
}

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

double calculateAverage(double sum, int count) {
    return sum / count;
}


void calculate(int a, int b, int &sum, int &product) {
    sum = a + b;
    product = a * b;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

double max(double a, double b) {
    return (a > b) ? a : b;
}

int max(int a, int b, int c) {
    return max(max(a, b), c);
}

void display(string message, int repeat = 1) {
    for (int i = 0; i < repeat; i++) {
        cout << message << endl;
    }
}

display("Hello");      
display("Hello", 3);   

inline int square(int x) {
    return x * x;
}

int factorial(int n) {
    if (n <= 1) return 1;          
    return n * factorial(n - 1);    
}

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int numbers[5] = {1, 2, 3, 4, 5};        
int values[5] = {1, 2};                   
int scores[] = {90, 85, 88, 92, 78};      

numbers[0] = 10;        
int x = numbers[2];      

for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
}


int sum = 0;
for (int i = 0; i < size; i++) {
    sum += arr[i];
}


int search(int arr[], int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) return i;
    }
    return -1;
}

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

matrix[1][2] = 10;    
int value = matrix[0][0];  

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
}

void modifyArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] *= 2;  
    }
}

char name[] = "John";        
char city[20] = "New York";


#include <cstring>
strlen(str);        
strcpy(dest, src);  
strcat(dest, src);  
strcmp(str1, str2); 

#include <string>
using namespace std;

string name = "Alice";
string fullName = name + " Smith";  
int len = name.length();             
name.append(" Jones");                
name.substr(0, 3);                    


getline(cin, fullName);               

int x = 10;
int *ptr = &x;      

cout << ptr;        
cout << *ptr;       

*ptr = 20;          

int arr[] = {10, 20, 30, 40};
int *ptr = arr;      

cout << *ptr;        
ptr++;               
cout << *ptr;        


for (int *p = arr; p < arr + 4; p++) {
    cout << *p << " ";
}

int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr;      


arr[2] = 10;
*(arr + 2) = 10;
ptr[2] = 10;
*(ptr + 2) = 10;

int x = 5;
int *ptr = &x;
int **pptr = &ptr;   

cout << **pptr;      

#include <cstdlib>

int *p = (int*)malloc(5 * sizeof(int));     
free(p);                                     

int *q = (int*)calloc(5, sizeof(int));       
q = (int*)realloc(q, 10 * sizeof(int));      

int *p = new int(5);      
delete p;                 


int *arr = new int[10];   
delete[] arr;             

int rows = 3, cols = 4;
int **matrix = new int*[rows];

for (int i = 0; i < rows; i++) {
    matrix[i] = new int[cols];
}


matrix[1][2] = 10;


for (int i = 0; i < rows; i++) {
    delete[] matrix[i];
}
delete[] matrix;

#include <memory>

unique_ptr<int> p1(new int(5));
unique_ptr<int> p2 = make_unique<int>(10);  

shared_ptr<int> s1 = make_shared<int>(20);  
shared_ptr<int> s2 = s1;                     

struct Student {
    int rollNumber;
    string name;
    float marks;
    char grade;
};  


Student s1;
Student s2 = {101, "Alice", 85.5, 'A'};


s1.rollNumber = 102;
s1.name = "Bob";
s1.marks = 92.0;

cout << s2.name << " scored " << s2.marks;

Student batch[30];
batch[0].rollNumber = 101;
batch[0].name = "Alice";

for (int i = 0; i < 30; i++) {
    cout << batch[i].name << endl;
}

Student s = {101, "Alice", 85.5, 'A'};
Student *ptr = &s;


cout << ptr->name;     
cout << (*ptr).name;   

struct Address {
    string street;
    string city;
    int zipCode;
};

struct Person {
    string name;
    int age;
    Address address;  
};

Person p;
p.address.city = "New York";

void display(Student s) {
    cout << s.name << endl;
}


void updateMarks(Student &s, float newMarks) {
    s.marks = newMarks;
}


void initStudent(Student *s, int roll, string name) {
    s->rollNumber = roll;
    s->name = name;
}

union Data {
    int i;
    float f;
    char str[20];
};

Data d;
d.i = 10;           
cout << d.f;        
d.f = 3.14;         

typedef struct {
    int x, y;
} Point;

Point p1, p2;  


using Point = struct { int x, y; };

enum Color { RED, GREEN, BLUE };  
enum Status { OK = 200, NOT_FOUND = 404, ERROR = 500 };

Color c = RED;


enum class TrafficLight { RED, YELLOW, GREEN };
TrafficLight light = TrafficLight::GREEN;

#include <fstream>


ofstream outFile("data.txt");
if (outFile.is_open()) {
    outFile << "Hello, World!" << endl;
    outFile << 100 << " " << 3.14 << endl;
    outFile.close();
}


ifstream inFile("data.txt");
string line;
while (getline(inFile, line)) {
    cout << line << endl;
}
inFile.close();


ofstream appFile("data.txt", ios::app);
appFile << "Additional line" << endl;
appFile.close();

struct Record {
    int id;
    char name[50];
    double salary;
};


Record emp = {101, "John Doe", 50000.0};
ofstream binOut("data.bin", ios::binary);
binOut.write(reinterpret_cast<char*>(&emp), sizeof(emp));
binOut.close();


Record empRead;
ifstream binIn("data.bin", ios::binary);
binIn.read(reinterpret_cast<char*>(&empRead), sizeof(empRead));
binIn.close();

streampos pos = file.tellg();  
streampos pos2 = file.tellp(); 


file.seekg(0, ios::beg);    
file.seekg(10, ios::cur);    
file.seekg(-5, ios::end);    

if (!file) {
    cerr << "Error opening file" << endl;
}

if (file.fail()) {
    cerr << "Operation failed" << endl;
}

if (file.eof()) {
    cout << "End of file reached" << endl;
}

#include <stdio.h>

FILE *fp = fopen("data.txt", "w");
fprintf(fp, "Hello, World!n");
fclose(fp);

fp = fopen("data.txt", "r");
char buffer[100];
fgets(buffer, 100, fp);
printf("%s", buffer);
fclose(fp);

class Rectangle {
private:
    double length;
    double width;

public:
    
    Rectangle(double l = 0, double w = 0) {
        length = l;
        width = w;
    }
    
    
    void setDimensions(double l, double w) {
        length = l;
        width = w;
    }
    
    double getArea() {
        return length * width;
    }
    
    double getPerimeter() {
        return 2 * (length + width);
    }
};


Rectangle rect1(5, 3);
Rectangle rect2;  

class Student {
private:
    string name;
    int age;

public:
    
    Student() {
        name = "Unknown";
        age = 0;
    }
    
    
    Student(string n, int a) {
        name = n;
        age = a;
    }
    
    
    Student(const Student &other) {
        name = other.name;
        age = other.age;
    }
    
    
    ~Student() {
        cout << "Destroying student: " << name << endl;
    }
};

class Counter {
private:
    static int count;  

public:
    Counter() { count++; }
    ~Counter() { count--; }
    static int getCount() { return count; }
};


int Counter::count = 0;

class Person {
private:
    string name;
    
public:
    void setName(string name) {
        this->name = name;  
    }
    
    Person& setAge(int age) {
        this->age = age;
        return *this;       
    }
};

#include <iostream>
using namespace std;

int main() {
    cout << "Hello, World!" << endl;
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    double a, b;
    char op;
    
    cout << "Enter expression (e.g., 5 + 3): ";
    cin >> a >> op >> b;
    
    switch(op) {
        case '+': cout << "Result: " << a + b << endl; break;
        case '-': cout << "Result: " << a - b << endl; break;
        case '*': cout << "Result: " << a * b << endl; break;
        case '/': 
            if (b != 0) cout << "Result: " << a / b << endl;
            else cout << "Division by zero!" << endl;
            break;
        default: cout << "Invalid operator!" << endl;
    }
    
    return 0;
}

int rows = 5;
for (int i = 1; i <= rows; i++) {
    for (int j = 1; j <= i; j++) {
        cout << "*";
    }
    cout << endl;
}

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0));
    int secret = rand() % 100 + 1;
    int guess, attempts = 0;
    
    do {
        cout << "Guess number (1-100): ";
        cin >> guess;
        attempts++;
        
        if (guess > secret) cout << "Too high!" << endl;
        else if (guess < secret) cout << "Too low!" << endl;
        else cout << "Correct! Attempts: " << attempts << endl;
        
    } while (guess != secret);
    
    return 0;
}

#include <iostream>
using namespace std;


int add(int a, int b);
int subtract(int a, int b);
int multiply(int a, int b);
float divide(int a, int b);

int main() {
    int choice, x, y;
    
    do {
        cout << "n1. Addn2. Subtractn3. Multiplyn4. Dividen5. Exitn";
        cout << "Choice: ";
        cin >> choice;
        
        if (choice >= 1 && choice <= 4) {
            cout << "Enter two numbers: ";
            cin >> x >> y;
        }
        
        switch(choice) {
            case 1: cout << "Result: " << add(x, y) << endl; break;
            case 2: cout << "Result: " << subtract(x, y) << endl; break;
            case 3: cout << "Result: " << multiply(x, y) << endl; break;
            case 4: 
                if (y != 0) cout << "Result: " << divide(x, y) << endl;
                else cout << "Division by zero!" << endl;
                break;
            case 5: cout << "Goodbye!" << endl; break;
            default: cout << "Invalid choice!" << endl;
        }
    } while (choice != 5);
    
    return 0;
}

int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
int multiply(int a, int b) { return a * b; }
float divide(int a, int b) { return (float)a / b; }

#include <iostream>
using namespace std;

void inputArray(int arr[], int size) {
    cout << "Enter " << size << " elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }
}

void displayArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int findMax(int arr[], int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

int findMin(int arr[], int size) {
    int min = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

double findAverage(int arr[], int size) {
    double sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum / size;
}

void sortArray(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    const int SIZE = 10;
    int numbers[SIZE];
    
    inputArray(numbers, SIZE);
    
    cout << "Array: ";
    displayArray(numbers, SIZE);
    
    cout << "Maximum: " << findMax(numbers, SIZE) << endl;
    cout << "Minimum: " << findMin(numbers, SIZE) << endl;
    cout << "Average: " << findAverage(numbers, SIZE) << endl;
    
    sortArray(numbers, SIZE);
    cout << "Sorted: ";
    displayArray(numbers, SIZE);
    
    return 0;
}

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main() {
    string text;
    
    cout << "Enter a sentence: ";
    getline(cin, text);
    
    
    cout << "Length: " << text.length() << endl;
    
    
    string upper = text;
    for (char &c : upper) {
        c = toupper(c);
    }
    cout << "Uppercase: " << upper << endl;
    
    
    bool isPalindrome = true;
    int len = text.length();
    for (int i = 0; i < len / 2; i++) {
        if (tolower(text[i]) != tolower(text[len - 1 - i])) {
            isPalindrome = false;
            break;
        }
    }
    cout << (isPalindrome ? "Palindrome" : "Not palindrome") << endl;
    
    
    int vowels = 0, consonants = 0;
    for (char c : text) {
        if (isalpha(c)) {
            c = tolower(c);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
                vowels++;
            else
                consonants++;
        }
    }
    cout << "Vowels: " << vowels << ", Consonants: " << consonants << endl;
    
    return 0;
}

#include <iostream>
using namespace std;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int x = 10, y = 20;
    cout << "Before swap: x = " << x << ", y = " << y << endl;
    swap(&x, &y);
    cout << "After swap:  x = " << x << ", y = " << y << endl;
    
    
    int size;
    cout << "Enter array size: ";
    cin >> size;
    
    int *arr = new int[size];
    cout << "Enter " << size << " numbers: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }
    
    cout << "Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    delete[] arr;
    
    return 0;
}

Study Notes: CS-407 Operating Systems

An Operating System (OS) is the most fundamental software that acts as an intermediary between the user and the computer hardware. Its primary goal is to manage all other applications and programs and to facilitate hardware interaction, ensuring that resources are allocated efficiently and fairly among running applications . This course explores the core concepts, structures, and algorithms that make up modern operating systems.

Unit 1: Introduction to Operating Systems

This unit provides a foundational understanding of what an OS is, how it evolved, and its core architectural components.

1.1 What is an Operating System?

From an abstract viewpoint, an OS is the software layer that manages a computer’s hardware and provides a stable, consistent environment for applications to execute . Key functions include:

• Resource Management: Efficiently and fairly managing the CPU, memory, and peripheral devices .

• User Interface: Providing a means for users to interact with the system (Command-Line Interface or Graphical User Interface).

• Application Support: Offering a platform for application software to run without needing to know hardware details.

1.2 Evolution and Types of Operating Systems

Operating systems have evolved significantly to meet different computing needs .

1.3 Core Operating System Components

• Interrupts and its types : A signal sent by hardware or software to the CPU, indicating an event that needs immediate attention. Interrupts are fundamental to how the OS responds to events (like keyboard input or disk I/O completion). They allow the CPU to be used for other tasks while waiting for slow I/O operations.

• What is Kernel and its types : The kernel is the core, central component of an operating system. It has complete control over everything in the system. It is the first program loaded on startup and manages memory, processes, and devices. Types include monolithic kernels (where all OS services run in kernel space, e.g., Linux) and microkernels (where only essential services run in kernel space, e.g., QNX) .

• System Calls : The programming interface to the services provided by the OS. When an application needs to perform a privileged operation (like reading a file or creating a new process), it makes a system call to the kernel .

2. Process Management

A process is the fundamental unit of work in an operating system. This unit covers its lifecycle and how the OS manages it.

2.1 The Concept of a Process

A process is a program in execution . It is more than just the program code (text section); it also includes the current activity (program counter, processor registers), the process stack, and a data section (heap). The OS manages processes using a data structure called the Process Control Block (PCB) . The PCB contains all information about a specific process, such as its state, program counter, CPU registers, memory limits, and list of open files.

2.2 Process States and Transitions

As a process executes, it changes states . The typical states are:

1. New: The process is being created.

2. Ready: The process is in main memory and is ready to be assigned to the CPU.

3. Running: Instructions are being executed on the CPU.

4. Waiting (Blocked) : The process is waiting for some event to occur (such as an I/O completion).

5. Terminated: The process has finished execution.

2.3 Process Scheduling and Operations

The OS uses various schedulers to manage processes .

• Long-Term Scheduler (Job Scheduler) : Selects processes from a disk and loads them into memory for the ready queue.

• Short-Term Scheduler (CPU Scheduler) : Selects from among the processes that are ready to execute and allocates the CPU to one of them. This is invoked frequently.

• Medium-Term Scheduler: Used for swapping processes out of memory to reduce multiprogramming.

Operations on processes include creation (e.g., fork() in Unix) and termination (e.g., exit()).

2.4 Threads: Introduction, Advantages, and Types

A thread is a lightweight process; it is the basic unit of CPU utilization. It comprises a thread ID, a program counter, a register set, and a stack. A process can have multiple threads, all sharing the same code, data, and other OS resources (like open files) of that process.

• Advantages: Responsiveness (a program can continue even if part of it is blocked), Resource Sharing (threads share memory and resources), Economy (cheaper to create and context-switch threads than processes), and Scalability (threads can run in parallel on multiple cores).

• Types:

  • User Threads: Managed entirely in user space without kernel support. Faster to manage but if one thread blocks, the entire process can block.

  • Kernel Threads: Supported and managed directly by the kernel. Slower to manage but if one thread blocks, others can continue. All modern OSes (Linux, Windows, macOS) support kernel threads.

3. CPU Scheduling

CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes, the OS can make the computer more productive.

3.1 Scheduling Objectives and Criteria

The primary objectives of a scheduling algorithm are to maximize CPU utilization and throughput (number of processes completed per time unit) and to minimize turnaround time, waiting time, and response time .

3.2 Preemptive and Non-Preemptive Scheduling

• Non-Preemptive Scheduling: Once a process gets the CPU, it holds it until it either terminates or voluntarily switches to the waiting state.

• Preemptive Scheduling: A process can be preempted (interrupted) by the OS and moved from the running state to the ready state. This is used in modern time-sharing systems.

3.3 Scheduling Algorithms

4. Synchronization and Deadlocks

Concurrent access to shared data may result in data inconsistency. Mechanisms are needed to ensure the orderly execution of cooperating processes.

4.1 Process Synchronization

When multiple processes access and manipulate the same shared data, the final result depends on the order of execution. This is a race condition. To prevent this, we need process synchronization. Regions of code that access shared resources are called critical sections . The idea is that when one process is executing in its critical section, no other process should be allowed to execute in its critical section.

4.2 Synchronization Tools

• Mutex Locks (Mutual Exclusion) : A simple lock that a process must acquire before entering a critical section and release when it leaves. If the lock is available, the process acquires it and continues; otherwise, it waits.

• Semaphores: A more robust synchronization tool proposed by Dijkstra. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() (or P) and signal() (or V). They can be used for both mutual exclusion and for coordinating events.

4.3 Deadlocks

A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process in the set.

• Resources : CPU cycles, memory space, files, and I/O devices.

• Necessary Conditions for Deadlock:

  1. Mutual Exclusion: At least one resource must be held in a non-sharable mode.

  2. Hold and Wait: A process must be holding at least one resource and waiting for additional resources held by others.

  3. No Preemption: Resources cannot be preempted; they can only be released voluntarily by the process holding them.

  4. Circular Wait: A set of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, …, Pn is waiting for a resource held by P0.

These conditions can be represented using a Resource Allocation Graph (RAG) .

4.4 Handling Deadlocks

1. Deadlock Prevention: Ensuring that at least one of the four necessary conditions never holds.

2. Deadlock Avoidance: The OS knows in advance the resources a process will need and uses an algorithm (like the Banker’s Algorithm) to decide if allocating a resource will lead to an unsafe state.

3. Deadlock Detection and Recovery: Allowing the system to enter a deadlock state, detecting it, and then recovering (e.g., by terminating a process or preempting a resource).

5. Memory Management

The main purpose of a computer system is to execute programs, which must be in main memory during execution. Memory management is the task of allocating memory to processes efficiently and safely.

5.1 Basic Concepts

• Logical vs. Physical Address Space : A logical address (or virtual address) is generated by the CPU and is relative to the program. A physical address is the actual address in main memory. The MMU (Memory Management Unit) maps logical addresses to physical addresses at runtime.

• Swapping : A process can be temporarily swapped out of memory to a backing store (disk) and then brought back into memory for continued execution.

• Contiguous vs. Non-Contiguous Storage Allocation : In contiguous allocation, each process is contained in a single contiguous section of memory. Non-contiguous allocation (like paging) allows a process to be spread across multiple, non-adjacent memory regions.

5.2 Contiguous Memory Allocation

Main memory is usually divided into two partitions: one for the OS and one for user processes. In contiguous allocation, each process is contained in a single contiguous section of memory. This can lead to fragmentation—especially external fragmentation (memory is so broken into little pieces that no single piece is large enough to hold a process).

5.3 Paging

Paging is a memory management scheme that permits the physical address space of a process to be non-contiguous. It avoids external fragmentation.

• Physical memory is divided into fixed-sized blocks called frames.

• Logical memory is divided into blocks of the same size called pages.

• Every address generated by the CPU is divided into a page number (p) and a page offset (d).

• The page number is used as an index into a page table, which contains the base address of each frame in physical memory.

5.4 Virtual Memory

Virtual memory is a technique that allows the execution of a process that is not completely in memory. It abstracts main memory into a huge, uniform array of storage, separating logical memory as perceived by users from physical memory.

• Demand Paging : A virtual memory implementation where a page is brought into memory only when it is needed (i.e., when there is a page fault). This reduces the amount of I/O needed and memory required.

• Page Replacement Algorithms : When a page fault occurs and there is no free frame in memory, the OS must replace an existing page to make room for the new one. Common algorithms include:

  • FIFO (First-In, First-Out)

  • Optimal Page Replacement (OPT)

  • LRU (Least Recently Used)

• Thrashing : A phenomenon where a process spends more time paging (swapping pages in and out) than executing. This happens when there are too many processes in memory, leading to insufficient frames for each.

6. File System and I/O Management

This unit covers how the OS manages persistent data and interacts with hardware devices.

6.1 File System Management

A file is a collection of related information defined by its creator. The OS implements the abstract concept of a file by managing mass storage media.

• File Attributes : Name, identifier, type, location, size, protection, time/date/user identification.

• File Operations : Creating, writing, reading, repositioning within a file, deleting, truncating.

• Access Methods : Sequential access (reading bytes in order) and direct access (random access based on block/record number).

• Directory Structure : A symbol table that maps file names to their directory entries. Structures can be single-level, two-level, or tree-structured. Modern OSes use a tree-structured or acyclic-graph structure, which allows for sharing via links.

6.2 I/O Management

The OS hides the peculiarities of specific hardware devices from the user.

• I/O Operations & Handshaking : The process of coordinating data transfer between the CPU and a device controller.

• Classes of Interrupts : Mechanisms by which device controllers inform the CPU that they have completed an operation or require attention.

• I/O Devices : Broad categories include block devices (e.g., disks) and character devices (e.g., keyboards).

7. Advanced Topics and System Security

This unit touches on advanced OS concepts and the critical area of security.

7.1 System Protection and Security

• Protection: A mechanism for controlling the access of programs, processes, or users to the resources defined by a computer system (e.g., memory protection).

• Security: Defending a system from external and internal threats, such as viruses, worms, and unauthorized access.

7.2 Virtual Machines

A virtual machine (VM) takes the layered approach to its logical conclusion. It treats the OS and the hardware of a single computer as though they were multiple, different machines. A hypervisor (VMM) manages the underlying hardware and creates the illusion of multiple separate machines. This allows for running multiple different OSes on the same physical hardware.

7.3 Specialized Operating Systems

The principles learned in this course are applied in various specialized contexts:

• Mobile OS (e.g., Android, iOS) : Designed for handheld devices, with a focus on power management, touch interfaces, and app ecosystems .

• Cloud OS (e.g., OpenStack) : Manages the infrastructure of a data center, abstracting a collection of physical machines into one large, virtualized system .

Laboratory Work (Practical)

The 1 credit of practical work in this 3(2-1) course is designed to reinforce the theoretical concepts through hands-on application. Key activities include:

1. OS Installation and Commands: Installation of different Operating Systems (Windows, Linux). Mastering essential OS commands for file creation and management .

2. Scheduling Algorithm Implementation: Implementing and simulating core scheduling algorithms like First In First Out (FIFO) , Shortest Job First (SJF) , Priority Scheduling, and Round Robin (RR) .

3. Memory and Deadlock Management: Simulating various memory allocation methods (e.g., first-fit, best-fit) and implementing techniques for deadlock detection and recovery .

4. Thread Programming: Creating and managing threads using modern programming languages (like C or C++ with pthreads) to explore concurrency and synchronization .

5. System Performance Optimization: Using OS tools and commands to monitor system performance and identify bottlenecks

Study Notes: CS-406 Data Communications and Networks

Data communications and computer networks form the backbone of our interconnected world. This course introduces the fundamental concepts, technologies, and protocols that enable devices to communicate and share resources. From the physical transmission of bits to the applications we use daily, understanding these principles is essential for anyone working with modern computing systems .

Unit 1: Data Communication Concepts and Physical Layer

1.1 Data Communication Fundamentals

Data communication is the exchange of data between two devices via some form of transmission medium. For effective communication, the system must have:

• Message: The information to be communicated

• Sender: The device that sends the message

• Receiver: The device that receives the message

• Medium: The physical path by which the message travels

• Protocol: A set of rules governing data communication

Data representation includes text (ASCII, Unicode), numbers, images, audio, and video, each requiring different encoding and transmission considerations .

1.2 Data Transmission Concepts

Data transmission can occur in different modes:

• Simplex: One-way communication (keyboard to computer)

• Half-duplex: Two-way communication but only one direction at a time (walkie-talkie)

• Full-duplex: Two-way simultaneous communication (telephone)

Transmission impairments degrade signal quality:

• Attenuation: Loss of energy as signal propagates

• Distortion: Signal shape changes due to different frequency components traveling at different speeds

• Noise: Unwanted signals from various sources (thermal noise, crosstalk, impulse noise)

Signal encoding converts data into signals suitable for transmission:

• Digital-to-digital encoding: Line coding (NRZ, Manchester, differential Manchester)

• Digital-to-analog encoding: Modulation for transmission over analog media

1.3 Transmission Media

Transmission media can be guided (wired) or unguided (wireless) .

Unit 2: Transmission Techniques and Multiplexing

2.1 Transmission Modes

Asynchronous transmission sends data one character at a time with start and stop bits, allowing for simple timing but lower efficiency. Used in low-speed applications.

Synchronous transmission sends blocks of data with precise timing synchronization between sender and receiver, achieving higher efficiency. Used in high-speed applications .

2.2 Baseband vs. Broadband Transmission

2.3 Modulation Methods

Modulation converts digital data to analog signals for transmission over analog media:

Modems (modulator-demodulator) perform digital-to-analog conversion for transmission and analog-to-digital conversion at the receiving end.

2.4 Multiplexing

Multiplexing allows multiple signals to share a single transmission medium .

Unit 3: Network Evolution and Architecture

3.1 Evolution of Computer Networks

Computer networks evolved through distinct phases :

3.2 Switching Techniques

Circuit switching establishes a dedicated communication path before data transfer (traditional telephone network). Resources are reserved for the entire duration.

Packet switching divides messages into packets that travel independently and are reassembled at destination. Resources are shared dynamically .

3.3 Network Standards and Protocols

Standards ensure interoperability between different manufacturers’ equipment. Key standards organizations include IEEE, IETF, ITU-T, and ISO .

Unit 4: Reference Models and Data Link Layer

4.1 OSI 7-Layer Model

The Open Systems Interconnection (OSI) model provides a conceptual framework for understanding network communication .

4.2 TCP/IP Protocol Suite

The TCP/IP model is the practical implementation used in the Internet, with four layers :

4.3 Data Link Layer Functions

The data link layer provides reliable transfer of data across a single physical link .

Frame design structures data into frames with headers and trailers for addressing, error detection, and control.

Flow control prevents sender from overwhelming receiver:

• Stop-and-wait: Send one frame, wait for acknowledgment

• Sliding window: Multiple frames in flight with window control

Error handling detects and corrects transmission errors:

• Error detection: Parity checks, checksum, CRC (Cyclic Redundancy Check)

• Error correction: Automatic Repeat Request (ARQ) mechanisms (Stop-and-wait ARQ, Go-Back-N ARQ, Selective Repeat ARQ)

4.4 Data Link Protocols

Unit 5: Network, Transport, and Application Layers

5.1 Network Layer

The network layer handles routing and logical addressing, enabling communication across different networks .

Key protocols:

• IP (Internet Protocol) : Provides unreliable, best-effort delivery; IPv4 (32-bit addresses) and IPv6 (128-bit addresses)

• X.25: Early packet-switched network protocol

• Frame Relay: Simplified WAN protocol for high-speed packet switching

• ATM (Asynchronous Transfer Mode) : Cell-based switching with fixed 53-byte cells; supports QoS

Routing determines paths through the network:

• Static routing: Manually configured

• Dynamic routing: Protocols exchange routing information (RIP, OSPF, BGP)

Queuing theory analyzes waiting lines in networks, essential for understanding delay and buffer management .

5.2 Transport Layer

The transport layer provides end-to-end communication services for applications .

Congestion control manages network overload:

• TCP uses algorithms like slow start, congestion avoidance, fast retransmit, fast recovery

Flow control prevents sender from overwhelming receiver’s buffer:

Socket interface provides programming API for network applications .

5.3 Application Layer

The application layer provides services directly to end-users .

Network File System (NFS) enables file sharing across networks.
Remote Procedure Calling (RPC) allows programs to execute procedures on remote systems.

Authentication and encryption provide security:

• Authentication: Verifying identity (passwords, certificates)

• Encryption: Protecting data confidentiality (SSL/TLS, IPsec)

Unit 6: Local Area Networks (LANs)

6.1 LAN Architecture and Technology

Local Area Networks connect devices within a limited geographic area (building, campus) .

LAN needs:

• Resource sharing (printers, storage)

• Communication between users

• Centralized management

LAN architecture includes physical topology and access methods.

6.2 Ethernet

Ethernet is the dominant LAN technology .

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) operation:

1. Listen before transmitting (carrier sense)

2. If channel idle, transmit; if busy, wait

3. While transmitting, listen for collisions

4. If collision detected, stop, transmit jam signal, wait random time (backoff), retry

Ethernet parameters and specifications define timing, frame format, and electrical characteristics.

Ethernet cabling standards :

Ethernet evolution:

• 100BaseT (Fast Ethernet) : 100 Mbps over UTP

• 100BaseVG/AnyLAN: Alternative 100 Mbps technology (not widely adopted)

• Gigabit Ethernet: 1000 Mbps (1000BaseT, 1000BaseSX/LX)

• 10 Gigabit Ethernet and beyond: Increasing speeds for backbone and high-performance computing

6.3 LAN Interconnection Devices

Wiring closets centralize network equipment for structured cabling.

6.4 Other LAN Technologies

Unit 7: Advanced Topics and Network Management

7.1 VSAT Technology

VSAT (Very Small Aperture Terminal) uses small satellite dishes for two-way communications:

• Hub-spoke topology (star network)

• Applications: Rural connectivity, point-of-sale networks, private networks

7.2 Wireless LAN Technologies

Wireless LANs use radio frequencies and follow IEEE 802.11 standards :

WLAN components:

• Access points (APs): Connect wireless devices to wired network

• Wireless clients: Devices with wireless adapters

• Distribution system: Connects APs (usually wired Ethernet)

7.3 Network Management and Security

Network management encompasses monitoring, controlling, and optimizing network resources .

Infrastructure for network management includes:

• Managed devices (routers, switches, servers)

• Network Management Systems (NMS)

• Management protocols (SNMP)

• Management databases (MIB – Management Information Base)

Security infrastructure includes:

• Firewalls: Filter traffic based on rules

• IDS/IPS: Intrusion detection/prevention systems

• VPNs: Virtual Private Networks for secure remote access

• Authentication servers: RADIUS, TACACS+

• Encryption: Protecting data confidentiality and integrity

Key security concepts:

• Authentication: Verifying identity

• Authorization: Determining access rights

• Accounting: Tracking resource usage

• Confidentiality: Preventing unauthorized disclosure

• Integrity: Preventing unauthorized modification

• Availability: Ensuring timely access

Summary

Data Communications and Networks provides essential knowledge for understanding how information flows in our connected world:

• Data communication fundamentals establish the physical and electrical basis for transmission

• Transmission techniques (baseband/broadband, modulation, multiplexing) enable efficient use of media

• Network evolution from circuit switching to packet switching shaped today’s Internet

• OSI and TCP/IP models provide frameworks for understanding layered protocols

• Data link layer handles frame transfer, error control, and medium access

• Network layer routes packets across interconnected networks

• Transport layer ensures reliable end-to-end delivery

• Application layer provides services for users

• LAN technologies (especially Ethernet) dominate local connectivity

• Advanced topics include wireless, VSAT, and network management/security

Mastering these concepts prepares students to design, implement, and manage modern networks that support the applications and services essential to today’s digital economy.

Study Notes: CS-408 Database Systems

Course Overview

Database Systems is a comprehensive course covering the principles, design, and implementation of database management systems (DBMS). The course objectives include gaining knowledge of DBMS both in terms of use and implementation/design, developing proficiency with SQL, and gaining experience with analysis and design of database software .

Unit 1: Introduction to Database Systems and Data Modeling

1.1 Introduction to Database Systems

Database System Applications: Databases are integral to modern computing, supporting applications ranging from banking and airline reservations to university information systems and e-commerce platforms .

Database Systems Versus File Systems: Traditional file systems have several disadvantages compared to database systems:

• Data redundancy and inconsistency: Multiple file formats and duplication of data

• Difficulty in accessing data: Need to write new programs for each new task

• Data isolation: Multiple files and formats make integration difficult

• Integrity problems: Integrity constraints scattered throughout programs

• Atomicity problems: Failures may leave data in inconsistent state

• Concurrent access anomalies: Uncontrolled concurrent access can lead to inconsistencies

• Security problems: Hard to provide fine-grained access control

Views of Data: Database systems provide multiple levels of abstraction:

• Physical level: Describes how data is actually stored

• Logical level: Describes what data is stored and relationships among data

• View level: Application programs hide details of data types; only part of database is shown

Data Models: A collection of conceptual tools for describing data, data relationships, data semantics, and consistency constraints . Types include:

• Relational Model: Uses tables to represent data and relationships

• Entity-Relationship Model: Graphical representation of entities and their relationships

• Object-Based Models: Extend entity-relationship with object-oriented concepts

• Semi-structured Data Models: Allow data specification where individual data items of same type may have different sets of attributes

Database Languages:

Database Users and Administrators:

• Naive users: Use applications with predefined interfaces

• Application programmers: Write application programs

• Sophisticated users: Use query languages directly

• Database Administrators (DBA) : Central control of database system

Transaction Management: A transaction is a collection of operations that performs a single logical function in a database application . Transaction management ensures:

• Atomicity: Either all operations complete or none

• Consistency: Transaction preserves database consistency

• Isolation: Concurrent execution appears as serial execution

• Durability: Once transaction commits, changes persist

Database System Structure: Components include storage manager, query processor, transaction manager, and file manager .

Application Architectures:

1.2 Entity-Relationship Model

The Entity-Relationship (ER) model provides a high-level conceptual data model for database design .

Basic Concepts:

• Entity: A “thing” or object in the real world distinguishable from other objects

• Entity Set: Collection of similar entities (e.g., all customers)

• Attribute: Properties of an entity set

• Relationship: Association among several entities

• Relationship Set: Collection of similar relationships

Attribute Types:

• Simple vs. Composite: Simple attributes are atomic; composite can be subdivided

• Single-valued vs. Multi-valued: Single-valued has one value; multi-valued can have multiple

• Derived: Can be computed from other attributes

• Null values: Represent unknown or not applicable values

Constraints in ER Model:

Keys:

• Superkey: Set of attributes that uniquely identifies an entity

• Candidate Key: Minimal superkey

• Primary Key: Candidate key chosen by designer

E-R Diagrams: Graphical representation showing entity sets (rectangles), attributes (ovals), and relationship sets (diamonds) .

Weak Entity Sets: Entity sets that do not have sufficient attributes to form a primary key; identified by their association with a strong entity set .

Extended E-R Features:

• Specialization: Process of defining subgroups of an entity set

• Generalization: Process of defining a superclass from multiple entity sets

• Aggregation: Treating relationship set as an entity set for higher-level abstraction

Design of an E-R Database Schema: Systematic process of creating ER diagram representing enterprise data requirements .

Reduction of E-R Schema to Tables: Process of converting ER diagram to relational database tables .

The Unified Modeling Language (UML) : Alternative graphical language for database design .

Unit 2: Relational Model and Structured Query Language

2.1 Relational Model

Structure of Relational Databases: Data organized in tables (relations) consisting of rows (tuples) and columns (attributes) .

Relational Algebra: Procedural query language with operations :

• Select (σ) : Selects rows satisfying condition

• Project (π) : Selects columns

• Union (∪) : Combines tuples from two relations

• Set difference (−) : Tuples in one relation but not another

• Cartesian product (×) : Combines all tuples from two relations

• Rename (ρ) : Renames relations or attributes

Extended Relational Algebra Operations:

• Intersection (∩)

• Natural join (⋈) : Combines related tuples based on common attributes

• Division (÷) : For “all” queries

• Assignment (←) : Temporary relation assignment

Modification of Database: Insert, delete, and update operations expressed in relational algebra .

Views: Virtual relations defined by queries, not stored physically but computed when needed .

Tuple Relational Calculus: Non-procedural query language specifying what to retrieve without how .

Domain Relational Calculus: Similar to tuple calculus but uses domain variables .

2.2 Structured Query Language (SQL)

SQL is the standard language for relational database management .

Basic Structure:

SELECT [DISTINCT] attribute_list
FROM relation_list
WHERE condition

Set Operations:

• UNION: Combines results from two queries

• INTERSECT: Common tuples from two queries

• EXCEPT: Tuples in first but not second

Aggregate Functions:

• COUNT: Number of values

• SUM: Sum of values

• AVG: Average of values

• MAX: Maximum value

• MIN: Minimum value

Null Values: Special value representing unknown or missing data; comparisons with NULL yield UNKNOWN .

Nested Subqueries: Queries within queries using IN, EXISTS, NOT EXISTS, ANY, ALL .

Views: Create virtual tables using CREATE VIEW statement .

Complex Queries: Combining multiple operations, nested queries, and joins .

Modification of Database:

Joined Relations: Multiple join types including INNER JOIN, LEFT/RIGHT/FULL OUTER JOIN .

Data Definition Language (DDL) :

• CREATE TABLE: Define new relations

• ALTER TABLE: Modify relation schema

• DROP TABLE: Remove relation

Embedded SQL: SQL statements embedded in host programming languages (C/C++, Java) .

Dynamic SQL: SQL statements constructed and executed at runtime .

Unit 3: Integrity Constraints and Relational Database Design

3.1 Integrity Constraints

Integrity constraints ensure data accuracy and consistency .

Domain Constraints: Specify permissible values for attributes (e.g., value ranges, data types) .

Referential Integrity: Ensures that value appearing in one relation for given set of attributes also appears for same set of attributes in another relation .

Assertions: Specify conditions that must always be true for entire database; checked on every update .

Triggers: Statements automatically executed by system as side effect of database modification :

• Specify conditions and actions

• Can be activated before or after insert, delete, update

3.2 Security and Authorization

Authorization: Granting and revoking privileges to access data .

Authorization in SQL:

• GRANT: Give privileges to users

• REVOKE: Remove privileges from users

• Privilege types: SELECT, INSERT, UPDATE, DELETE, REFERENCES

Encryption: Protecting sensitive data through encoding; essential for data transmission and storage .

Authentication: Verifying identity of users accessing the database .

3.3 Relational Database Design

First Normal Form (1NF) : Domain of attributes must be atomic; no repeating groups .

Pitfalls in Relational Database Design: Problems that can occur with poor design including redundancy, update anomalies, insertion anomalies, deletion anomalies .

Functional Dependencies: Constraint between two sets of attributes; if two tuples agree on attributes α, they must agree on attributes β .

Decomposition: Breaking relation into multiple relations; must ensure :

Desirable Properties of Decomposition:

• Lossless join

• Dependency preservation

• No redundancy

Normal Forms:

Unit 4: Indexing, Hashing, and Transactions

4.1 Indexing and Hashing

Basic Concepts: Indexing structures speed up data access; trade-off between search speed and update overhead .

Ordered Indices:

• Primary index: Index on sorted file based on search key

• Clustering index: Index on sorted file with ordering key not same as search key

• Secondary index: Index on non-ordered file

B+ Tree Index Files: Balanced tree structure with high fanout :

• All paths from root to leaf have same length

• Leaf nodes contain pointers to records

• Supports equality and range queries efficiently

B-Tree Index Files: Similar to B+ tree but with pointers in internal nodes; less common .

Hashing:

Comparison of Ordered and Hashing:

• Hashing better for equality queries

• Ordered indices better for range queries

• Choice depends on query patterns

Index Definition in SQL: CREATE INDEX statement for performance optimization .

Multiple-Key Access: Using multiple indices for queries with conditions on multiple attributes .

4.2 Transactions

Transaction Concept: Unit of program execution accessing and updating data .

Transaction States :

• Active: Initial state; transaction executing

• Partially committed: After final statement

• Committed: After successful completion

• Failed: After discovery of abnormal condition

• Aborted: After rollback and database restored

Implementation of Atomicity and Durability:

Concurrent Executions: Multiple transactions executing simultaneously; increases system throughput .

Serializability: Ensuring concurrent execution results equivalent to some serial execution .

Recoverability: Properties ensuring recoverable schedules :

• Recoverable schedule: No transaction commits before transactions whose changes it read

• Cascadeless schedule: Transactions only read committed data

• Strict schedule: Only read/write committed data

Implementation of Isolation: Concurrency control mechanisms .

Transaction Definition in SQL: BEGIN TRANSACTION, COMMIT, ROLLBACK statements .

Testing for Serializability: Algorithms to check if schedule is serializable .

Unit 5: Concurrency Control and Recovery

5.1 Concurrency Control

Lock-Based Protocols: Most common approach using locks on data items :

Two-Phase Locking (2PL) : Protocol ensuring serializability :

• Growing phase: Acquire locks, cannot release

• Shrinking phase: Release locks, cannot acquire

• Strict 2PL: Hold exclusive locks until commit

Timestamp-Based Protocols: Assign timestamps to transactions; ensure conflict serializability by aborting violating transactions .

Validation-Based Protocols: Used in optimistic concurrency control; transactions validated before commit .

Multiple Granularity: Locking at different levels (database, table, page, tuple) .

Multiversion Schemes: Maintain multiple versions of data items to allow concurrent read-write .

Deadlock Handling: Situations where transactions wait indefinitely for each other :

Insert and Delete Operations: Special considerations for concurrency control .

Weak Level of Consistency: Applications may tolerate lower consistency for performance .

Concurrency in Index Structures: Specialized techniques for high concurrency .

5.2 Recovery System

Failure Classification:

• Transaction failure: Logical errors, system errors

• System crash: Power failure, software crash

• Disk failure: Storage media failure

Storage Structure:

• Volatile storage: Main memory; lost on crash

• Non-volatile storage: Disks; survives crashes

• Stable storage: Information never lost

Recovery and Atomicity: Ensuring transactions atomic despite failures .

Log-Based Recovery: Most common recovery technique :

• Undo logging: Record old values; undo uncommitted transactions

• Redo logging: Record new values; redo committed transactions

• Undo/Redo logging: Combination for flexibility

Log records: Contain transaction ID, data item ID, old value, new value

Recovery process: Scan log to determine committed/aborted transactions; undo/redo as needed

Shadow Paging: Maintain two page tables; atomic switch on commit .

Recovery with Concurrent Transactions: Handling multiple transactions during recovery .

Buffer Management: Interaction between buffer manager and recovery system .

Failure with Loss of Non-Volatile Storage: Handling catastrophic failures .

Advanced Recovery Techniques: ARIES, fuzzy checkpointing, etc. .

Remote Backup Systems: Maintaining backup database at remote site for disaster recovery .

Summary

Database Systems provides comprehensive coverage of:

• Introduction and Data Modeling: Database concepts, file system comparison, ER modeling

• Relational Model and SQL: Relational algebra, SQL queries, views

• Integrity and Design: Constraints, security, functional dependencies, normalization

• Indexing and Transactions: Index structures, transaction properties, serializability

• Concurrency and Recovery: Lock protocols, deadlock handling, log-based recovery

Understanding these concepts prepares students for careers as database administrators, application developers, or data architects, with practical skills in SQL and database design.

Study Notes: CS-410 Data Structures and Algorithms

Course Overview

Data Structures and Algorithms is a foundational computer science course that bridges the gap between programming and complex problem-solving. This course covers the principles of organizing data efficiently and designing algorithms that operate on these structures. The focus is on understanding the theoretical underpinnings, analyzing algorithm complexity, and implementing practical solutions .

Unit 1: Introduction to Data Structures and Algorithms

1.1 Introduction to Data Structures

A data structure is a specialized way of organizing and storing data in computer memory so that data can be accessed and manipulated efficiently . It is indispensable for the proper functioning of many computer algorithms.

Data Types:

• Primitive data types: Basic types provided by programming languages (int, float, char, boolean)

• Abstract Data Types (ADT) : Mathematical models with defined operations independent of implementation (e.g., List ADT, Stack ADT, Queue ADT)

Dynamic Memory Allocation: Ability to allocate memory during program execution, essential for implementing flexible data structures like linked lists and trees that can grow and shrink dynamically .

1.2 Classification of Data Structures

Linear Data Structures: Elements arranged in sequence

• Arrays, linked lists, stacks, queues

Non-Linear Data Structures: Elements not in sequence; hierarchical or network relationships

Static vs. Dynamic:

• Static: Fixed size (arrays)

• Dynamic: Size can change during execution (linked lists, trees)

1.3 Operations on Data Structures

Common operations include:

• Traversal: Accessing each element exactly once

• Search: Finding the location of an element

• Insertion: Adding a new element

• Deletion: Removing an element

• Sorting: Arranging elements in order

• Merging: Combining two structures

1.4 Choosing Appropriate Data Structures

Factors to consider:

• Nature of data to be processed

• Types of operations required

• Efficiency requirements (time and space)

• Ease of implementation

• Programming language support

1.5 Introduction to Algorithms

An algorithm is a finite sequence of well-defined steps to solve a problem . Key characteristics:

• Input: Zero or more inputs

• Output: At least one output

• Definiteness: Clear and unambiguous steps

• Finiteness: Terminates after finite steps

• Effectiveness: Each step is executable

Unit 2: Algorithms and Complexity Analysis

2.1 Complexity of Algorithms

Algorithm analysis determines the resources required to execute an algorithm:

2.2 Asymptotic Notations

Asymptotic notations describe the behavior of algorithms as input size grows:

Common complexity classes:

• O(1): Constant time

• O(log n): Logarithmic time

• O(n): Linear time

• O(n log n): Linearithmic time

• O(n²): Quadratic time

• O(2ⁿ): Exponential time

Recurrence Relations: Mathematical equations defining functions recursively; used to analyze recursive algorithms .

Amortized Analysis: Technique for analyzing a sequence of operations to show that average cost per operation is small, even if individual operations are expensive .

Unit 3: Arrays

3.1 Introduction to Arrays

An array is a collection of elements of the same type stored in contiguous memory locations. Each element can be accessed directly using an index.

Advantages:

Disadvantages:

3.2 Array Operations

• Static memory allocation: Size fixed at compile time

• Dynamic memory allocation: Size determined at runtime (using malloc/calloc in C, or lists in Python)

3.3 Two-Dimensional Arrays

Representation in computer memory:

Address calculation formula depends on ordering method.

3.4 Applications of Arrays

• Storing and processing collections of data

• Matrix operations

• Implementation of other data structures (stacks, queues, heaps)

Unit 4: Linked Lists

4.1 Introduction to Linked Lists

A linked list is a linear data structure where elements are stored in nodes, each containing a data field and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory.

Advantages:

Disadvantages:

4.2 Classification of Linked Lists

4.3 Operations on Linked Lists

• Traversal: Visiting each node sequentially

• Insertion: At beginning, end, or specified position

• Deletion: Removing node from beginning, end, or specified position

• Search: Finding node with given value

• Reverse: Reversing the list order

4.4 Memory Allocation and Garbage Collection

Dynamic memory allocation and deallocation are critical in linked list implementations. Garbage collection automatically reclaims memory no longer in use.

4.5 Applications

• Sparse matrix representation: Using arrays and linked lists to efficiently store matrices with mostly zero elements

• Polynomial representation: Storing polynomial terms for algebraic operations

Unit 5: Stacks

5.1 Introduction to Stacks

A stack is a linear data structure following Last-In-First-Out (LIFO) principle. Elements are added (pushed) and removed (popped) from one end called the top.

Primary operations:

• push(x): Add element x to top

• pop(): Remove and return top element

• peek()/top(): Return top element without removing

• isEmpty(): Check if stack is empty

• isFull(): Check if stack is full (in array implementation)

5.2 Design and Implementation

Stacks can be implemented using:

5.3 Applications of Stacks

• Expression evaluation: Infix, postfix, prefix conversions and evaluation

• Function call management: Recursion implementation

• Undo operations: In text editors

• Backtracking algorithms

• Balancing symbols: Checking parentheses in compilers

Unit 6: Queues

6.1 Introduction to Queues

A queue is a linear data structure following First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.

Primary operations:

• enqueue(x): Add element x at rear

• dequeue(): Remove and return front element

• front(): Return front element without removing

• rear(): Return rear element

• isEmpty(): Check if queue is empty

6.2 Design and Implementation

6.3 Double-ended Queue (Deque)

Allows insertion and deletion at both ends. Combines features of stacks and queues.

6.4 Priority Queue

Each element has associated priority; element with highest priority is removed first. Often implemented using heaps.

Applications:

6.5 Applications of Queues

• Process scheduling: CPU and disk scheduling

• Breadth-First Search in graphs

• Buffering: I/O buffers, print spooling

• Simulation: Queuing systems

Unit 7: Recursion

7.1 Introduction to Recursion

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. Every recursive solution requires:

7.2 Classic Recursive Problems

7.3 Dynamic Programming and Memoization

Dynamic Programming: Optimization technique for problems with overlapping subproblems and optimal substructure. Avoids recomputation by storing results.

Memoization: Top-down approach storing computed results to avoid redundant recursive calls.

7.4 Advantages and Limitations

Advantages:

• Elegant solutions for naturally recursive problems

• Simplifies code for tree/graph traversal

• Divide-and-conquer approach

Limitations:

• Overhead of function calls

• Stack overflow for deep recursion

• May be less efficient than iterative solutions

Unit 8: Trees

8.1 Introduction to Trees

A tree is a non-linear hierarchical data structure consisting of nodes connected by edges.

Terminology:

• Root: Topmost node

• Parent/Child: Direct relationship between nodes

• Leaf: Node with no children

• Subtree: Tree formed by any node and its descendants

• Height: Length of longest path from root to leaf

• Depth: Length of path from root to node

8.2 Binary Trees

Each node has at most two children: left and right.

Types:

• Strict/Proper binary tree: Each node has 0 or 2 children

• Complete binary tree: All levels filled except possibly last

• Full binary tree: All nodes have 0 or 2 children

• Perfect binary tree: All leaves at same level

8.3 Binary Tree Traversals

8.4 Binary Search Tree (BST)

Binary tree where for each node:

Operations:

8.5 Balanced Trees

AVL Trees: Self-balancing BST where height difference between left and right subtrees (balance factor) is at most 1. Rotations maintain balance after insertions/deletions.

Red/Black Trees: Self-balancing BST with color properties ensuring approximate balance.

B-Trees: Multi-way search trees optimized for disk storage; widely used in databases and file systems .

Splay Trees: Self-adjusting BST where recently accessed elements move to root .

Treaps: Random priority heap combined with BST .

Tries: Tree-like structure for strings; each path represents a word .

Unit 9: Graphs

9.1 Introduction to Graphs

A graph G = (V, E) consists of vertices (V) and edges (E) connecting them.

Types:

• Directed vs. Undirected: Edges have direction or not

• Weighted vs. Unweighted: Edges have associated weights

• Cyclic vs. Acyclic: Contains cycles or not

• Connected vs. Disconnected: Path exists between all vertex pairs

9.2 Graph Representation

9.3 Graph Traversals

Depth-First Search (DFS) :

• Uses stack (recursive or explicit)

• Explores as far as possible before backtracking

• Applications: Connected components, cycle detection, topological sort

Breadth-First Search (BFS) :

• Uses queue

• Explores neighbors before deeper levels

• Applications: Shortest path (unweighted), connected components

9.4 Applications of Graphs

Spanning Trees: Subgraph connecting all vertices with minimum edges

Shortest Path Algorithms :

• Dijkstra’s Algorithm: Single-source shortest path (non-negative weights)

• Bellman-Ford: Handles negative weights

• Floyd-Warshall: All-pairs shortest paths

Directed Acyclic Graphs (DAGs) :

Strongly Connected Components: Kosaraju’s and Tarjan’s algorithms

Unit 10: Sorting and Searching

10.1 Sorting Algorithms

Comparison Sorts: Based on comparing elements; lower bound Ω(n log n) .

Linear Time Sorts: Counting sort, radix sort, bucket sort (not based on comparisons) .

10.2 Searching Algorithms

10.3 Hashing

Hashing maps keys to array indices using a hash function, enabling O(1) average-case search, insert, delete.

Popular Hashing Methods:

Collision Resolution Techniques:

• Chaining: Each bucket contains linked list of colliding elements

• Open Addressing: Find next available slot (linear probing, quadratic probing, double hashing)

Load Factor: α = n/m (number of elements / table size). Affects performance; rehashing when threshold exceeded.

Unit 11: Priority Queues and Heaps

11.1 Priority Queues

Abstract data type where each element has priority; highest-priority element removed first.

11.2 Heaps

Complete binary tree with heap property:

Heap Operations:

Heap Sort: Build heap, repeatedly extract maximum.

Binomial and Fibonacci Heaps: Advanced heap structures for mergeable priority queues .

Unit 12: Advanced Topics

12.1 String Algorithms

• Pattern matching: KMP, Boyer-Moore

• Suffix trees: Applications in string search, LCS

12.2 Data Compression

12.3 Dynamic Programming

Technique for solving complex problems by breaking into overlapping subproblems.

Applications:

12.4 NP-Completeness

Class of problems for which no efficient solution is known:

• P: Problems solvable in polynomial time

• NP: Problems verifiable in polynomial time

• NP-Complete: Hardest problems in NP

• NP-Hard: At least as hard as NP-complete

Summary

Data Structures and Algorithms provides the essential foundation for all advanced computer science work:

• Data structures organize data for efficient access and manipulation

• Algorithm analysis using asymptotic notations helps compare efficiency

• Linear structures (arrays, linked lists, stacks, queues) handle sequential data

• Non-linear structures (trees, graphs) model hierarchies and relationships

• Recursion elegantly solves problems with self-similar structure

• Sorting and searching are fundamental operations with well-understood tradeoffs

• Hashing enables O(1) average-case operations

• Advanced topics like dynamic programming and NP-completeness prepare for graduate study

Mastering these concepts is essential for developing efficient software, acing technical interviews, and advancing in computer science

Study Notes: CS-412 Visual Programming

Course Overview

Visual Programming is a software development methodology that employs graphical representations of elements and their interconnections to create, structure, and manipulate code, rather than traditional text-based programming approaches . This course introduces the fundamental concepts, tools, and applications of visual programming languages (VPLs), exploring how they make programming more intuitive, accessible, and efficient for various domains.

Unit 1: Introduction to Visual Programming

1.1 What is Visual Programming?

Visual programming is a paradigm where programs are created by manipulating graphical elements rather than writing textual code . A visual programming language (VPL) uses graphic symbols as its basic units, arranging them spatially to describe computational tasks and processes . The core characteristic is replacing the one-dimensional string structure of traditional text languages with multi-dimensional graphical structures .

Visual programming languages must be implemented within visual program development environments that handle tasks such as:

• Icon editing

• Pattern analysis

• Semantic mapping

• Code generation

1.2 Distinction from Related Concepts

It is important to distinguish visual programming from related but distinct concepts:

1.3 Why Visual Programming?

The development of visual programming addresses several needs :

These advantages make visual programming particularly valuable as computers have become ubiquitous and users now come from all walks of life, not just the scientific community .

1.4 Historical Development of Visual Programming

Unit 2: Principles of Visual Language Design and Implementation

2.1 Formal Structure of Visual Languages

A visual programming language can be formally described as a triple (ID, Go, B) :

Each icon—whether basic or composite—has dual representation: a logical part (meaning) and a physical part (display graphics) .

2.2 Visual Program Implementation Process

Visual language implementation involves several processing stages :

1. Icon Editing: Users create and arrange visual elements

2. Pattern Analysis: Spatial structure analysis converts graphical programs into pattern strings

3. Syntax Analysis: Grammar rules generate parse trees from pattern strings

4. Semantic Mapping: Parse tree meaning derived via semantic rules associated with grammar productions

5. Program Execution/Compilation: Internal representation either interpreted directly or compiled into executable code

For large systems, implementation environments also require databases, view tools, browsers, and project management tools .

2.3 Syntax Specification Methods

Two main approaches define visual language syntax :

2.4 Visual Program Structure

Visual programs use two-dimensional or multi-dimensional structures rather than the linear relationships found in text language input streams . Basic spatial relationships include:

• Intersection

• Adjacency

• Containment

• Connection

The basic icon set divides into object icons (representing data) and operation icons (representing processing) .

Unit 3: Types of Visual Programming Languages

Several categories of visual programming languages have emerged, each with distinct characteristics .

3.1 Dataflow Languages

Dataflow languages represent programs as directed graphs where nodes represent operations and edges represent data flow between them.

LabVIEW (Laboratory Virtual Instrument Engineering Workbench) : Developed by National Instruments, widely used in engineering and scientific fields for data acquisition, instrument control, and industrial automation . Uses graphical block diagrams where blocks represent functions and wires represent data flow.

3.2 Block-Based Educational Languages

These languages use interlocking blocks resembling puzzle pieces to represent programming constructs, minimizing syntax errors .

Scratch exemplifies the “learning by doing” philosophy with colorful blocks representing loops, conditionals, and variables—users snap blocks together like building toys .

Blockly extends beyond education into application development, converting visual blocks into multiple text-based languages .

3.3 Game Development Visual Languages

Unreal Engine Blueprints enables developers to create game logic through node graphs without writing code—widely used in professional game development .

3.4 General-Purpose Visual Programming Frameworks

Modern frameworks provide extensible platforms for building visual programming applications.

Blackprint Features :

• Separate engine distribution for different runtime environments

• Online editor with TypeScript support

• Remote control for target environments (Node.js, Python)

• Extensible through modules

• MIT licensed open source

PishPosh Architecture :

• Modular plugins (Grid, Toolbox, PanZoom, Station, Connect)

• Reactive signals and event-driven agents

• Pure DOM + SVG implementation

3.5 Specialized Visual Languages

Unit 4: Visual Programming Paradigms

4.1 Flow-Based Programming

Flow-based programming represents applications as networks of “black box” processes exchanging data over predefined connections . Key characteristics:

• Nodes process data independently

• Edges represent data flow paths

• Parallel execution naturally supported

Examples: Node-RED, LabVIEW, Pure Data

4.2 State-Based Programming

Programs defined as sets of states and transitions between them:

4.3 Spreadsheet Paradigm

Query-by-Example (QBE) pioneered spreadsheet-like database queries where users fill two-dimensional tables to specify queries .

4.4 Constraint-Based Programming

Users specify relationships (constraints) between elements, and system maintains these relationships automatically.

4.5 Hybrid Systems

Modern platforms combine multiple paradigms. Blackprint, for example, supports dataflow with pausable and routable data flow, remote control, and code generation across multiple target languages .

Unit 5: Visual Programming Environments and Tools

5.1 Development Environment Components

Visual programming environments typically include :

5.2 Example Environment: Blackprint Sketch

Blackprint Sketch provides :

• Mirrored sketches on detachable windows

• Mini sketches for preview

• Hot reload functionality

• JSON export/import

• Multi-node selection and manipulation

• Cable arrangement with branching

• Variable nodes

• Hidden unused ports

• TypeScript definition files

5.3 Example Environment: PishPosh

PishPosh uses a subway map metaphor where :

• Stations represent nodes

• Connections represent edges

• Agents provide programmatic functionality (TimerAgent, GraphAgent)

• Event-driven architecture

5.4 No-Code/Low-Code Platforms

Visual programming has evolved into comprehensive no-code/low-code platforms :

These platforms democratize software creation, enabling non-technical users to build sophisticated applications.

Unit 6: Applications of Visual Programming

6.1 Education

Visual programming has revolutionized computer science education :

Educational benefits include :

• Reduced syntax barrier

• Immediate visual feedback

• Encouragement of experimentation

• Community support and project sharing

6.2 Scientific and Engineering Applications

6.3 Industrial Automation

• PLC Programming: Visual languages for programmable logic controllers

• SCADA Systems: Supervisory control and data acquisition interfaces

• Robotics: Microsoft VPL for robot control

• Process Control: LabVIEW in manufacturing

6.4 Multimedia and Creative Applications

6.5 Business and Data Processing

• Workflow Automation: Node-RED for IoT and automation

• Data Transformation: Visual ETL (Extract, Transform, Load) tools

• Business Process Modeling: Visual representations of organizational workflows

6.6 Web and Application Development

• No-Code Platforms: AppMaster, Bubble, Adalo

• Visual Web Design: Wix, Squarespace visual builders

• Mobile App Development: App Inventor

Unit 7: Visual Programming vs. Textual Programming

7.1 Comparative Analysis

7.2 Hybrid Approaches

Many modern systems combine visual and textual programming:

• Blockly generates JavaScript, Python, etc.

• Blackprint exports JSON executed by language-specific engines

• Unreal Blueprints can call C++ functions

This integration allows leveraging visual programming’s accessibility while maintaining textual programming’s power for advanced scenarios .

7.3 Transition from Visual to Textual Programming

For education and career development, visual programming serves as an effective stepping stone to textual languages . Students first grasp computational concepts visually before encountering syntax complexity.

Unit 8: Implementation Considerations

8.1 Technical Architecture

Modern visual programming environments require :

PishPosh demonstrates pure DOM + SVG implementation with reactive patterns . Blackprint uses ScarletsFrame framework with TypeScript support .

8.2 Performance Optimization

Visual environments face unique performance challenges:

• Rendering large graphs: Virtualization, level-of-detail

• Real-time updates: Efficient event propagation

• Background processing: Task scheduling for UI responsiveness

• Memory management: Careful cleanup of disconnected elements

PictoBlox exemplifies optimization for both Intel and Apple Silicon Macs with background task coordination preventing UI freezes .

8.3 User Experience Design

Successful visual environments prioritize :

• Predictable navigation

• Readable information density

• Stable keyboard shortcuts

• Consistent layout

• Minimal context switching

8.4 Cross-Language Support

Blackprint’s architecture illustrates challenges of cross-language visual programming :

• Each node must be reimplemented for each target language

• Basic nodes may be available across languages

• Language-specific nodes may not transfer

Unit 9: Current Trends and Future Directions

9.1 No-Code/Low-Code Movement

The democratization of software development through visual programming platforms represents a major industry trend . These platforms enable:

• Citizen developers creating business applications

• Rapid prototyping and iteration

• Reduced development costs

• Faster time-to-market

9.2 AI-Enhanced Visual Programming

Integration of artificial intelligence:

• Intelligent code completion in visual environments

• Automated node arrangement

• Pattern recognition for optimization

• Natural language to visual program conversion

PictoBlox incorporates AI blocks for educational projects .

9.3 Collaborative Visual Programming

Real-time collaboration features:

• Multi-user editing

• Shared debugging sessions

• Remote control of running applications

• Team-based development workflows

9.4 Internet of Things (IoT)

Visual programming particularly suits IoT development:

• Node-RED for IoT automation

• Visual programming for Arduino (Visuino)

• Sensor/actuator integration

9.5 Augmented and Virtual Reality

Emerging applications in immersive environments:

• VR programming interfaces

• AR-based visual programming

• 3D dataflow representations

9.6 Challenges and Limitations

Despite advances, visual programming faces ongoing challenges :

• Scalability: Managing very large programs visually

• Expressiveness: Representing complex algorithms

• Performance overhead: Interpretation costs

• Standardization: Lack of common visual languages

• Tool integration: Working with existing development ecosystems

Unit 10: Laboratory Work (Practical Component)

The laboratory component for a 3(2-1) credit course provides hands-on experience with visual programming tools and techniques.

10.1 Introduction to Visual Programming Environment

Activities:

• Install and configure a visual programming environment (Scratch, Blockly, LabVIEW)

• Explore the interface: canvas, toolbox, properties panel

• Create simple programs with basic blocks/nodes

• Execute and observe program behavior

10.2 Building Interactive Applications

Exercises :

• Scratch: Create animated story with sprites and dialogue

• App Inventor: Build simple Android app with buttons and text display

• Blockly: Generate JavaScript from visual blocks

10.3 Dataflow Programming

Activities :

• Implement number processing pipeline (input → calculation → output)

• Create temperature conversion program

• Build simple calculator with visual nodes

10.4 Event-Driven Programming

Exercises:

10.5 Game Development with Visual Scripting

Activities :

• Unreal Engine Blueprints introduction

• Create simple game mechanics (movement, scoring)

• Implement collision detection

10.6 Hardware Integration

Projects :

10.7 Advanced Visual Programming

Exercises:

• Create custom nodes/blocks

• Implement reusable visual components

• Export visual program to textual code

10.8 Project Work

Capstone Project: Design and implement complete visual program solving real-world problem, documenting:

• Problem statement

• Visual program design

• Implementation details

• Testing and results

Summary

Visual Programming represents a powerful paradigm that makes software development more accessible, intuitive, and efficient across numerous domains:

• Fundamental concepts establish visual languages as multi-dimensional graphical representations of computation

• Historical development spans from 1950s logic diagrams to modern no-code platforms

• Language types include dataflow (LabVIEW), block-based (Scratch, Blockly), game development (Unreal Blueprints), and general-purpose frameworks (Blackprint)

• Implementation principles require formal syntax definition, pattern analysis, and semantic mapping

• Applications range from education and scientific instrumentation to industrial automation and creative media

• Advantages include lower learning barriers, intuitive representation, and better stakeholder communication

• Limitations involve scalability, expressiveness, and performance considerations

• Current trends include no-code platforms, AI integration, and IoT applications

Visual programming continues to evolve, democratizing software creation while serving as both an educational stepping stone and a professional tool for specialized domains. Understanding its principles, tools, and applications prepares students to leverage this paradigm effectively in their careers.

Study Notes: CS-503 Design and Analysis of Algorithms

Course Overview

Design and Analysis of Algorithms is a foundational computer science course that focuses on creating efficient solutions to computational problems and rigorously analyzing their performance. The course emphasizes understanding algorithm design techniques, proving algorithm correctness, and evaluating time and space complexity . The 3(2-1) credit structure combines theoretical concepts with practical implementation.

Course Objectives:

• Design new algorithms and prove them correct

• Analyze asymptotic and absolute runtime and memory demands

• Apply classical sorting, searching, optimization, and graph algorithms

• Understand algorithm design techniques including recursion, divide-and-conquer, and greedy methods

Unit 1: Introduction to Algorithms and Complexity Analysis

1.1 What is an Algorithm?

An algorithm is a finite sequence of well-defined computational steps that transform input into output . It is a step-by-step procedure to achieve a required result, independent of any programming language .

Characteristics of Algorithms :

• Input: Accepts zero or more inputs

• Output: Produces at least one output

• Definiteness: Each step must be clear and unambiguous

• Finiteness: Must terminate after a finite number of steps

• Effectiveness: Every step must be basic and essential

• Independence: Should be independent of any programming code

Steps to Design an Algorithm :

1. Problem definition

2. Choose appropriate design technique

3. Draw flowchart/pseudocode

4. Testing

5. Analyze algorithm (time and space complexity)

6. Implementation

1.2 Analysis of Algorithms

Algorithm analysis determines the resources required for execution, primarily time complexity (running time) and space complexity (memory requirements) .

Types of Analysis :

• A Priori Analysis: Theoretical analysis before implementation, assuming constant factors like processor speed have no effect

• A Posteriori Analysis: Empirical analysis after implementation, collecting actual statistics on target machine

Cases of Complexity :

• Best Case: Minimum running time for any input of size n

• Average Case: Average running time over all inputs of size n

• Worst Case: Maximum running time for any input of size n

Most often, we focus on worst-case analysis as it provides an upper bound guarantee .

1.3 Asymptotic Notations

Asymptotic notations describe the behavior of functions as input size grows large .

Big-Oh Notation (O) : f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀ . Represents asymptotic upper bound.

Big-Omega Notation (Ω) : f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that f(n) ≥ c·g(n) for all n ≥ n₀ . Represents asymptotic lower bound.

Big-Theta Notation (Θ) : f(n) = Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀ . Represents asymptotic tight bound.

1.4 Common Complexity Classes

1.5 Recurrence Relations and Master’s Theorem

Many recursive algorithms are analyzed using recurrence relations. The Master’s Theorem provides a cookbook solution for recurrences of the form :

T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1

Master’s Theorem Cases :

1.6 Sorting Algorithms

Comparison-Based Sorts :

Linear Time Sorts :

• Counting Sort: O(n + k) where k is range of input

• Radix Sort: O(d(n + b)) where d is digits, b is base

• Bucket Sort: O(n) average case for uniformly distributed input

Unit 2: Advanced Data Structures

2.1 Balanced Trees

Red-Black Trees: Self-balancing binary search tree with following properties :

• Every node is either red or black

• Root is always black

• Red nodes cannot have red children (no two consecutive reds)

• Every path from root to leaf has same number of black nodes

• Operations: O(log n) for search, insert, delete

B-Trees: Balanced multi-way search trees optimized for disk storage :

• Nodes can have multiple keys (degree determines capacity)

• All leaves at same depth

• Operations: O(log n) with high fanout reduces disk I/O

• Widely used in databases and file systems

2.2 Advanced Heaps

Binomial Heaps :

• Collection of binomial trees

• Mergeable heap structure supporting union in O(log n)

• Operations: insert, extract-min, decrease-key in O(log n)

Fibonacci Heaps :

• Collection of trees with more relaxed structure

• Better amortized complexity than binomial heaps

• Operations: insert O(1), decrease-key O(1) amortized

• Used in Dijkstra’s and Prim’s algorithms for better performance

2.3 Specialized Data Structures

Tries (Prefix Trees) :

• Tree-like structure for strings

• Each path represents a word or prefix

• Operations: O(m) where m is string length

• Applications: Autocomplete, spell checking, IP routing

Skip Lists :

• Probabilistic data structure with multiple layers

• Average O(log n) for search, insert, delete

• Alternative to balanced trees with simpler implementation

Unit 3: Algorithm Design Techniques

3.1 Divide and Conquer

General Method :

1. Divide: Break problem into smaller subproblems

2. Conquer: Solve subproblems recursively

3. Combine: Merge solutions into final answer

Applications :

• Merge Sort: Divide array into halves, sort recursively, merge

• Quick Sort: Partition around pivot, sort subarrays recursively

• Binary Search: Divide search space in half each step

• Matrix Multiplication: Strassen’s algorithm O(n^2.81)

• Convex Hull: Finding smallest polygon containing points

3.2 Greedy Methods

General Method :

• Make locally optimal choice at each step

• Hope to find global optimum

• Does not always yield optimal solution (need proof)

Applications :

3.3 Dynamic Programming

General Method :

• Solve problems by combining solutions to subproblems

• Subproblems overlap (unlike divide-and-conquer)

• Store results to avoid recomputation (memoization)

• Requires optimal substructure property

Applications :

Unit 4: Advanced Problem-Solving Techniques

4.1 Backtracking

General Method :

• Systematically search solution space

• Build candidates incrementally

• Abandon (prune) when candidate cannot lead to valid solution

• Depth-first search of solution space

Applications :

4.2 Branch and Bound

General Method :

• Similar to backtracking but uses bounds to prune

• Maintain best solution found so far

• Use bounding function to eliminate branches

• Often used for optimization problems

Applications :

4.3 Graph Algorithms

Elementary Graph Algorithms :

• Breadth-First Search (BFS) : O(V + E), shortest path in unweighted graphs

• Depth-First Search (DFS) : O(V + E), topological sort, connected components

• Articulation Points: Vertices whose removal disconnects graph

• Biconnected Components: Maximal sets where any two vertices connected by two disjoint paths

Minimum Spanning Trees :

• Prim’s Algorithm: Grows tree from single vertex, O(E log V) with heap

• Kruskal’s Algorithm: Adds edges in increasing weight order, O(E log E)

Shortest Paths :

• Single Source: Dijkstra (non-negative weights), Bellman-Ford (negative weights allowed)

• All Pairs: Floyd-Warshall O(V³), Johnson’s O(V² log V + VE)

Maximum Flow :

• Ford-Fulkerson: O(E·max_flow)

• Edmonds-Karp: O(VE²)

• Applications: Network capacity, bipartite matching

Unit 5: Advanced Topics

5.1 String Matching

Problem: Find occurrences of pattern P in text T .

5.2 NP-Completeness Theory

Complexity Classes :

Cook’s Theorem : SAT (satisfiability) is NP-complete.

Proving NP-Completeness :

1. Show problem is in NP (can verify certificate in polynomial time)

2. Select known NP-complete problem

3. Construct polynomial-time reduction from known problem to target

4. Show reduction is correct

Common NP-Complete Problems:

5.3 Approximation Algorithms

For NP-hard problems where exact solution is infeasible, approximation algorithms find near-optimal solutions with guaranteed bounds .

5.4 Randomized Algorithms

Algorithms that use random choices during execution :

Applications:

5.5 Algebraic Computation

Fast Fourier Transform (FFT) :

• Computes discrete Fourier transform in O(n log n)

• Applications: Polynomial multiplication, signal processing

• Uses divide-and-conquer with complex roots of unity

Unit 6: Disjoint Sets and Amortized Analysis

6.1 Disjoint Set Operations

Disjoint Set ADT (Union-Find) :

• Maintains collection of disjoint sets

• Operations: MAKE-SET, UNION, FIND-SET

Representations:

Analysis: With union by rank and path compression, sequence of m operations on n elements takes O(m α(n)), where α(n) is inverse Ackermann function .

6.2 Amortized Analysis

Technique for analyzing sequence of operations where average cost per operation is small even if individual operations are expensive .

Methods :

• Aggregate method: Compute total cost, divide by number of operations

• Accounting method: Assign different charges to operations, build credit

• Potential method: Define potential function, measure state changes

Applications:

Summary

Design and Analysis of Algorithms provides the essential foundation for creating efficient computational solutions:

• Algorithm analysis using asymptotic notations (O, Ω, Θ) helps compare efficiency

• Sorting algorithms demonstrate different trade-offs in time, space, and stability

• Advanced data structures (Red-Black trees, B-trees, heaps) enable efficient operations

• Divide and conquer breaks problems into independent subproblems

• Greedy methods make locally optimal choices

• Dynamic programming handles overlapping subproblems with optimal substructure

• Backtracking and branch-and-bound systematically explore solution spaces

• Graph algorithms solve connectivity, shortest path, and flow problems

• NP-completeness identifies problems likely requiring exponential time

• Approximation and randomized algorithms provide practical solutions for hard problems

Mastering these concepts prepares students for technical interviews, advanced coursework, and careers requiring efficient software development.

Study Notes: CS-507 Computer Organization and Assembly Language

Course Overview

Computer Organization and Assembly Language provides a foundational understanding of how computer systems are structured and how software interacts with hardware at the lowest level. This course bridges the gap between high-level programming and the underlying machine architecture, enabling students to write efficient code and understand system behavior .

Course Objectives :

• Understand the basic organization of computer systems

• Learn the relationship between hardware and software

• Master assembly language programming concepts

• Develop skills for writing efficient, low-level code

• Understand how high-level language constructs are implemented

Unit 1: Introduction to Computer Organization and Architecture

1.1 Computer Organization vs. Computer Architecture

1.2 Basic Computer Structure

A computer system consists of three main functional units :

1. Central Processing Unit (CPU) : Brain of computer performing processing

2. Memory Unit: Stores data and instructions

3. Input/Output (I/O) Unit: Handles communication with external devices

Computer Functions :

• Data processing: Arithmetic and logical operations

• Data storage: Temporary and permanent storage

• Data movement: Transfer between components

• Control: Managing all operations

1.3 Von Neumann Architecture

The Von Neumann architecture (stored-program concept) has these characteristics :

• Single memory space for both instructions and data

• Sequential execution of instructions

• Control unit fetches instructions from memory

• Five components: memory, control unit, ALU, input, output

Von Neumann Bottleneck: Limited throughput between CPU and memory because both instructions and data share same bus .

1.4 Harvard Architecture

Harvard architecture separates instruction and data memory :

• Separate address and data buses

• Simultaneous access to instructions and data

• Used in many embedded systems and DSPs

• Modern processors often use modified Harvard (separate caches, unified main memory)

Unit 2: Central Processing Unit

2.1 CPU Components

2.2 Register Organization

User-Visible Registers :

• General Purpose: Available for any use

• Data Registers: Hold data for operations

• Address Registers: Hold memory addresses

• Condition Codes: Status flags (zero, carry, overflow, negative)

Control and Status Registers :

• Program Counter (PC) : Address of next instruction

• Instruction Register (IR) : Current instruction being executed

• Memory Address Register (MAR) : Address for memory access

• Memory Data/Buffer Register (MDR/MBR) : Data for memory transfer

• Program Status Word (PSW) : System state information

2.3 Instruction Cycle

The instruction cycle consists of these steps :

1. Fetch: Retrieve instruction from memory

2. Decode: Interpret instruction

3. Fetch Operands: Retrieve data needed

4. Execute: Perform operation

5. Store Results: Write back results

6. Repeat: Continue with next instruction

2.4 Interrupts

Interrupt: Signal that causes CPU to suspend current execution and handle special event .

Types of Interrupts :

• Hardware interrupts: External devices (I/O, timer)

• Software interrupts: Program-generated (system calls)

• Exceptions: Internal errors (division by zero, invalid instruction)

Interrupt Handling Process :

1. Complete current instruction

2. Save current state (PC, registers)

3. Identify interrupt source

4. Load Interrupt Service Routine (ISR) address

5. Execute ISR

6. Restore state and resume original program

Unit 3: Memory Organization

3.1 Memory Hierarchy

Memory hierarchy balances speed, capacity, and cost :

Principle of Locality :

3.2 Cache Memory

Cache Mapping Techniques :

Cache Write Policies :

3.3 Virtual Memory

Virtual memory provides illusion of larger memory space than physically available :

Address Translation :

Paging :

• Memory divided into fixed-size pages

• Page table maps virtual pages to physical frames

• Page fault occurs when page not in memory

Segmentation :

• Memory divided into variable-sized segments

• Logical units (code, data, stack)

3.4 Memory Management Techniques

Unit 4: Input/Output Organization

4.1 I/O Modules

I/O modules interface between CPU/peripherals and external devices :

4.2 I/O Techniques

DMA Operation :

1. CPU initializes DMA controller (source, destination, count)

2. DMA transfers data independently

3. DMA interrupts CPU when complete

4.3 I/O Addressing

4.4 Buses

Bus: Communication pathway connecting components .

Bus Arbitration determines which device controls bus when multiple request access.

Unit 5: Instruction Set Architecture

5.1 Instruction Formats

Instructions typically contain :

Instruction Length :

• Fixed length (RISC)

• Variable length (CISC)

Number of Addresses :

• 3-address: ADD R1, R2, R3 (R1 = R2 + R3)

• 2-address: ADD R1, R2 (R1 = R1 + R2)

• 1-address: ADD X (accumulator = accumulator + X)

• 0-address: Stack-based operations

5.2 Addressing Modes

5.3 Instruction Types

5.4 RISC vs. CISC

Unit 6: Assembly Language Fundamentals

6.1 Assembly Language Concepts

Assembly language is a low-level programming language that uses mnemonics to represent machine instructions . It provides a human-readable representation of machine code .

Assembler: Translates assembly code into machine language .

Basic Assembly Language Elements :

• Labels: Symbolic names for memory locations

• Mnemonics: Symbolic operation codes

• Operands: Data or addresses

• Comments: Documentation

• Directives: Instructions to assembler

6.2 Sample Assembly Program Structure (x86)

section .data
    msg db 'Hello, World!', 0xa  
    len equ $ - msg               

section .text
    global _start

_start:
    
    mov eax, 4                    
    mov ebx, 1                    
    mov ecx, msg                  
    mov edx, len                  
    int 0x80                      
    
    
    mov eax, 1                    
    mov ebx, 0                    
    int 0x80

6.3 Assembly Language for Different Architectures

x86 Architecture (Intel/AMD) :

• CISC architecture

• Variable instruction length (1-15 bytes)

• Few registers (EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP)

• Complex addressing modes

ARM Architecture :

• RISC architecture

• Fixed 32-bit instructions (ARM mode) or 16-bit (Thumb mode)

• 16 general-purpose registers

• Load-store architecture

• Conditional execution on most instructions

MIPS Architecture :

Unit 7: Addressing Modes and Data Transfer

7.1 x86 Addressing Modes

Register Addressing :

MOV EAX, EBX        
ADD ECX, EDX        

Immediate Addressing :

Direct Memory Addressing :

MOV EAX, [1000]     
MOV [2000], EBX     

Register Indirect Addressing :

MOV EAX, [EBX]      
MOV [ECX], EDX      

Base-Plus-Index Addressing :

MOV EAX, [EBX + ECX]        
MOV EDX, [EBX + 4*ECX]      

Base-Relative Addressing (struct access) :

MOV EAX, [EBP + 8]          
MOV EDX, [EAX + 4]          

7.2 ARM Addressing Modes

Register Addressing :

MOV R0, R1          
ADD R2, R3, R4      

Immediate Addressing :

MOV R0, #100        
ADD R1, R2, #50     

Register Indirect (load/store only) :

LDR R0, [R1]        
STR R2, [R3]        

Pre-indexed (update address before access) :

Post-indexed (access then update) :

Unit 8: Arithmetic and Logical Operations

8.1 Arithmetic Instructions (x86)

8.2 Logical Instructions (x86)

8.3 Condition Codes (Flags)

Common Status Flags :

• ZF (Zero Flag) : Result = 0

• SF (Sign Flag) : Result negative (MSB = 1)

• CF (Carry Flag) : Carry/borrow from arithmetic

• OF (Overflow Flag) : Signed overflow

• AF (Auxiliary Carry) : BCD operations

• PF (Parity Flag) : Even parity

8.4 Bit Manipulation Examples

Checking if number is even (x86) :

Clearing a bit :

Setting a bit :

Toggling a bit :

Unit 9: Control Flow

9.1 Unconditional Jumps

x86:

ARM:

9.2 Conditional Jumps/Branches

x86 Conditional Jumps (based on flags) :

ARM Conditional Branches :

ARM also supports conditional execution for most instructions, not just branches:

CMP R0, #10
ADDGT R1, R1, #1   

9.3 Loops

x86 Loop Instructions :

MOV ECX, 10
loop_start:
    
    LOOP loop_start  

Condition-based loops :

while_loop:
    CMP EAX, 0
    JZ loop_exit
    
    DEC EAX
    JMP while_loop
loop_exit:

ARM loops :

MOV R0, #10
loop_start:
    SUBS R0, R0, #1   
    BNE loop_start    

9.4 Procedures and Subroutines

x86 Call/Return :

CALL my_proc        

RET                 

my_proc:
    
    RET

ARM Call/Return :

BL my_proc          

BX LR               

my_proc:
    PUSH {LR}        
    
    POP {LR}         
    BX LR            

Parameter Passing Conventions :

• Registers: Fast but limited

• Stack: Unlimited but slower

• Mixed: First few in registers, rest on stack

Unit 10: Stack and Subroutines

10.1 Stack Operations

x86 Stack Instructions :

ARM Stack Instructions :

PUSH {R0-R3, LR}    
POP {R0-R3, PC}     

Stack Frame (Standard prologue/epilogue) :

x86:

my_function:
    PUSH EBP          
    MOV EBP, ESP      
    SUB ESP, 16       
    
    MOV ESP, EBP      
    POP EBP           
    RET

ARM:

my_function:
    PUSH {R7, LR}     
    MOV R7, SP        
    SUB SP, SP, #16   
    
    ADD SP, SP, #16   
    POP {R7, PC}      

10.2 Recursion

Recursive functions must save state before recursive call :

Factorial example (x86) :

factorial:
    CMP EAX, 1
    JG recursive
    MOV EAX, 1        
    RET
    
recursive:
    PUSH EAX          
    DEC EAX           
    CALL factorial    
    POP EBX           
    IMUL EAX, EBX     
    RET

Unit 11: Interrupts and System Calls

11.1 Software Interrupts

x86 INT instruction :

MOV EAX, 4          
MOV EBX, 1          
MOV ECX, msg        
MOV EDX, len        
INT 0x80            

ARM Software Interrupt (SVC) :

MOV R0, #1          
LDR R1, =msg        
MOV R2, #len        
MOV R7, #4          
SVC 0               

11.2 Interrupt Vector Table

The Interrupt Vector Table (IVT) or Interrupt Descriptor Table (IDT) stores addresses of interrupt handlers . Each interrupt type has corresponding handler address.

11.3 Exception Handling

Exceptions (faults, traps, aborts) are handled similarly to interrupts but generated internally by CPU when problems occur:

• Division by zero

• Invalid opcode

• Page fault

• General protection fault

Unit 12: Advanced Topics

12.1 Pipelining

Instruction pipelining improves throughput by overlapping execution stages :

5-Stage RISC Pipeline :

1. IF: Instruction Fetch

2. ID: Instruction Decode/Register Fetch

3. EX: Execute

4. MEM: Memory Access

5. WB: Write Back

Pipeline Hazards :

• Structural hazards: Resource conflicts

• Data hazards: Instruction depends on previous result

• Control hazards: Branches change program flow

Data Hazard Resolution :

12.2 Superscalar Processors

Multiple instructions issued per cycle :

• Out-of-order execution

• Speculative execution

• Register renaming

12.3 Assembly and High-Level Languages

Compiler output : Compilers generate assembly from high-level code
Inline assembly: Embed assembly in high-level languages

C inline assembly (GCC) :

asm volatile("movl %0, %%eax" : : "r"(value));

Interfacing assembly with C :

Unit 13: Laboratory Work

13.1 Basic Assembly Programming

Exercises :

1. Write “Hello, World” program

2. Simple arithmetic operations

3. Conditional branching

4. Loop implementations

13.2 Data Manipulation

Exercises :

1. Array processing

2. String operations

3. Bit manipulation

4. Table lookup

13.3 Subroutines and Stack Usage

Exercises :

1. Procedure calls with parameters

2. Recursive functions

3. Stack frame analysis

4. Parameter passing conventions

13.4 I/O and System Calls

Exercises :

1. Console input/output

2. File operations

3. System call interface

4. Interrupt handlers (if using emulator)

13.5 Debugging Tools

Tools :

• GDB (GNU Debugger)

• Emulators (QEMU, SPIM, MARS)

• Simulators (emu8086, MASM)

Debugging techniques :

Summary

Computer Organization and Assembly Language provides the essential foundation for understanding how software interacts with hardware:

• Computer organization deals with how hardware components are arranged and interconnected

• CPU components include ALU, control unit, registers, and internal buses

• Memory hierarchy balances speed, capacity, and cost through registers, cache, RAM, and disk

• I/O techniques range from programmed I/O to interrupt-driven and DMA

• Instruction set architecture defines the interface between hardware and software

• Addressing modes provide flexible ways to access operands

• Assembly language offers human-readable representation of machine code

• Arithmetic and logical operations implement computation at the lowest level

• Control flow instructions enable conditional execution and loops

• Stack and subroutines manage procedure calls and local data

• Interrupts and system calls bridge user programs and operating system

• Pipelining and superscalar execution improve performance through parallelism

Mastering these concepts enables students to write efficient low-level code, understand system behavior, debug complex issues, and appreciate how high-level language constructs are implemented.

Study Notes: CS-509 Theory of Automata

Course Overview

Theory of Automata is a foundational computer science course that deals with the study of abstract machines and the computational problems that can be solved using these machines . Automata theory has deep connections to formal languages, computability theory, and complexity theory, with practical applications in compiler design, text processing, software verification, and natural language processing .

Course Objectives :

• Explain different methods for defining languages

• Understand finite automata and their properties

• Differentiate between regular languages and non-regular languages

• Describe context-free languages, grammars, and pushdown automata

• Understand Turing machines and the limits of computation

Unit 1: Mathematical Preliminaries and Fundamentals

1.1 Sets and Functions

Sets: A set is a collection of elements . Basic notations include:

• Set representation: A = {1, 2, 3} or C = {a, b, c, …, z}

• Element of: 7 ∈ {7, 21, 57} (7 belongs to the set)

• Not an element: 8 ∉ {7, 21, 57} (8 does not belong)

• Universal set: All possible elements under consideration

• Empty set (∅): Set with no members

Set Operations :

• Union (A ∪ B): Elements in A or B (or both)

• Intersection (A ∩ B): Elements in both A and B

• Difference (A – B): Elements in A but not in B

• Complement (A̅): Elements not in A

• Subset (A ⊆ B): Every member of A is also a member of B

• Proper subset (A ⊂ B): A is a subset of B and A ≠ B

Powerset: The set of all subsets of a set S, denoted 2^S. If |S| = n, then |2^S| = 2^n .

Cartesian Product: A × B = {(a, b) | a ∈ A, b ∈ B}. |A × B| = |A| × |B| .

Functions: A function f: A → B maps each element of domain A to an element of range B .

1.2 Alphabets, Strings, and Languages

Alphabet (Σ): A finite, non-empty set of symbols . Examples:

• Σ = {0, 1} (binary alphabet)

• Σ = {a, b, c, …, z} (English alphabet)

String: A finite sequence of symbols from an alphabet . Key terminology:

• Length (|w|) : Number of symbols in the string

• Empty string (ε or λ) : String of length zero

• Substring: Any contiguous part of a string

• Reverse of a string: String written backwards

Kleene Closure (Σ*) : The set of all strings (including the empty string) that can be formed from alphabet Σ .

Language: A set of strings over an alphabet. Formally, L ⊆ Σ* .

Unit 2: Finite Automata

2.1 What is an Automaton?

Automaton (plural: automata) = an abstract computing device or mathematical model of computation .

Automata Theory = the study of abstract machines and the computational problems that can be solved using these machines .

2.2 Finite Automata (FA)

A Finite Automaton (FA) is a mathematical model for computers with an extremely limited amount of memory . It has no temporary memory—only states and transitions .

Formal Definition: A deterministic finite automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) where :

• Q: Finite set of states

• Σ: Finite input alphabet

• δ: Q × Σ → Q (transition function)

• q₀: Start state (q₀ ∈ Q)

• F: Set of accept states (F ⊆ Q)

How a DFA Processes Strings :

1. Start in q₀

2. For each symbol in the input string, apply the transition function to move to the next state

3. After processing all symbols, if the final state ∈ F, the string is accepted; otherwise, it is rejected

Extended Transition Function: δ*(q, w) represents the state reached after processing string w from state q .

Language of a DFA: L(M) = {w ∈ Σ* | δ*(q₀, w) ∈ F} .

2.3 Examples of Finite Automata

Example 1: DFA that accepts strings ending with ‘b’ :

State diagram with:

• Q = {q₀, q₁}

• Σ = {a, b}

• Start state: q₀

• Accept state: q₁

• Transitions:

  • δ(q₀, a) = q₀ (stay in start state on ‘a’)

  • δ(q₀, b) = q₁ (move to accept state on ‘b’)

  • δ(q₁, a) = q₀ (move back on ‘a’)

  • δ(q₁, b) = q₁ (stay in accept state on ‘b’)

Example 2: DFA for strings with even number of b’s :

States track parity:

Example 3: DFA for strings with no two consecutive b’s :

Three states track the last symbol seen and whether we’ve already seen “bb”.

2.4 Transition Graphs (TG)

A Transition Graph (TG) is a generalization of finite automata that allows:

• Multiple transitions on the same symbol from a state

• Transitions on strings (not just single symbols)

• More flexible representation

2.5 Deterministic vs. Non-deterministic Finite Automata

Deterministic Finite Automaton (DFA) :

Non-deterministic Finite Automaton (NFA) :

• Multiple possible transitions on same symbol

• May have ε-transitions (transitions on empty string)

• δ: Q × (Σ ∪ {ε}) → P(Q) (power set of Q)

• Accepts if any path leads to an accept state

Key Insight: NFA and DFA are equivalent in power—every NFA can be converted to a DFA that recognizes the same language . However, the DFA may have exponentially more states.

Unit 3: Regular Languages and Expressions

3.1 Regular Languages

A language is regular if there exists a finite automaton (DFA or NFA) that recognizes it .

3.2 Regular Expressions

Regular expressions (RE) provide an algebraic way to describe regular languages .

Definition by Recursion:

1. Basis:

   • ∅ is a regular expression denoting the empty language

   • ε is a regular expression denoting {ε}

   • For each a ∈ Σ, a is a regular expression denoting {a}

2. Inductive Step: If r and s are regular expressions denoting languages R and S, then:

   • (r + s) [or (r | s)] denotes R ∪ S (union)

   • (r · s) [or (rs)] denotes R ◦ S (concatenation)

   • (r) denotes R (Kleene closure)

Operator Precedence: * (highest), then concatenation, then + (lowest) .

Examples :

• a* : strings of zero or more a’s

• (a + b)* : any string over {a, b}

• a*b* : any number of a’s followed by any number of b’s

• (aa + bb)* : strings of even length composed of aa and bb

3.3 Kleene’s Theorem

Kleene’s Theorem is a fundamental result stating that regular expressions and finite automata are equivalent in expressive power :

• Part I: Every regular expression can be converted to a finite automaton (NFA with ε-transitions)

• Part II: Every finite automaton can be converted to a regular expression

• Part III: Finite automata and regular expressions define exactly the same class of languages: the regular languages

Thompson’s Construction: Algorithm to convert RE → NFA .

State Elimination Method: Algorithm to convert FA → RE .

3.4 Closure Properties of Regular Languages

Regular languages are closed under the following operations :

• Union (L₁ ∪ L₂)

• Intersection (L₁ ∩ L₂)

• Complement (L̅)

• Concatenation (L₁ · L₂)

• Kleene closure (L*)

• Difference (L₁ − L₂)

3.5 Pumping Lemma for Regular Languages

The Pumping Lemma provides a way to prove that certain languages are not regular .

Statement: If L is a regular language, then there exists a constant n (the pumping length) such that for every string w in L with |w| ≥ n, we can write w = xyz satisfying:

1. |xy| ≤ n

2. |y| ≥ 1

3. For all k ≥ 0, xyᵏz ∈ L

Application: To prove L is not regular:

1. Assume L is regular, let n be the pumping length

2. Choose a string w ∈ L with |w| ≥ n (cleverly chosen based on n)

3. Show that for any decomposition w = xyz satisfying conditions 1-2, pumping y zero times or multiple times yields a string ∉ L

4. Contradiction → L cannot be regular

Example: L = {aⁿbⁿ | n ≥ 0} is not regular .

3.6 Myhill-Nerode Theorem

The Myhill-Nerode Theorem provides an alternative characterization of regular languages based on equivalence relations on strings .

Key Idea: Define x ≡_L y if for all z, xz ∈ L ⇔ yz ∈ L. L is regular iff ≡_L has finitely many equivalence classes. The number of classes equals the number of states in the minimal DFA.

This approach is often considered more fundamental than the Pumping Lemma and leads directly to minimal DFA construction .

Unit 4: Context-Free Grammars and Languages

4.1 Context-Free Grammars (CFG)

A Context-Free Grammar (CFG) is a formalism for generating languages, more powerful than regular expressions .

Formal Definition: A CFG is a 4-tuple G = (V, Σ, R, S) where:

• V: Finite set of variables (non-terminals)

• Σ: Finite set of terminals (disjoint from V)

• R: Finite set of production rules of the form A → α, where A ∈ V and α ∈ (V ∪ Σ)*

• S: Start variable (S ∈ V)

Derivations: Starting from S, replace variables using production rules until only terminals remain.

4.2 Examples of CFGs

Example 1: Grammar for {aⁿbⁿ | n ≥ 0} :

Derivation of a²b²: S ⇒ aSb ⇒ aaSbb ⇒ aaεbb = aabb

Example 2: Grammar for PALINDROME over {a, b} :

S → aSa | bSb | a | b | ε

Example 3: Grammar for EVEN-EVEN (strings with even number of a’s and even number of b’s) :

S → SS | aA | bB | ε
A → aS | bA? (complex—simpler: S → aSa | bSb | ε works for even-length palindromes but not general EVEN-EVEN)

4.3 Parse Trees and Derivations

A parse tree represents the syntactic structure of a string according to a CFG .

Leftmost derivation: Always replace the leftmost variable
Rightmost derivation: Always replace the rightmost variable

4.4 Ambiguity

A CFG is ambiguous if there exists a string with two distinct parse trees (or two distinct leftmost derivations) .

Example: Grammar for arithmetic expressions:

E → E + E | E × E | id

String “id + id × id” has two parse trees (one where + is below ×, one where × is below +).

Some ambiguous grammars can be rewritten to be unambiguous; some languages are inherently ambiguous.

4.5 Regular Grammars

A regular grammar is a CFG where all productions are of the form :

Regular grammars generate exactly the regular languages .

Unit 5: Pushdown Automata

5.1 Definition and Structure

A Pushdown Automaton (PDA) is a finite automaton with an additional stack memory . It corresponds exactly to context-free grammars in expressive power.

Components :

Formal Definition: A PDA is a 7-tuple P = (Q, Σ, Γ, δ, q₀, Z₀, F) where:

• Q: Finite set of states

• Σ: Input alphabet

• Γ: Stack alphabet

• δ: Transition function mapping (state, input symbol or ε, stack top) to (state, stack string)

• q₀: Start state

• Z₀: Initial stack symbol

• F: Accept states

Acceptance Modes:

• Accept by final state: After reading entire input, PDA is in accept state

• Accept by empty stack: After reading entire input, stack is empty

5.2 PDA and CFG Equivalence

Theorem: A language is context-free if and only if there exists a PDA that recognizes it .

5.3 Deterministic vs. Non-deterministic PDA

Unlike finite automata, NPDA are strictly more powerful than DPDA. Languages recognized by DPDA are called deterministic context-free languages (a proper subset of CFLs).

Unit 6: Turing Machines

6.1 Introduction to Turing Machines

A Turing Machine (TM) is a more powerful computational model with random-access memory (infinite tape) . It captures the intuitive notion of “algorithm” and defines the limits of computation.

Components:

• Finite state control

• Infinite tape (divided into cells)

• Tape head (reads/writes, moves left/right)

• Blank symbol (⊔) initially on unused tape cells

Formal Definition: A TM is a 7-tuple M = (Q, Σ, Γ, δ, q₀, B, F) where:

• Q: Finite set of states

• Σ: Input alphabet (subset of Γ, not including blank)

• Γ: Tape alphabet (including Σ and blank)

• δ: Q × Γ → Q × Γ × {L, R} (transition function—may be partial)

• q₀: Start state

• B: Blank symbol (∈ Γ, ∉ Σ)

• F: Set of accept states

6.2 TM Computations

Configuration: Current state, tape contents, head position.

Halting: TM halts when no transition is defined for current (state, symbol) pair.

Acceptance: Input accepted if TM reaches an accept state.

6.3 Variations of Turing Machines

Equivalent in power :

• Multi-tape TMs

• Non-deterministic TMs

• Multi-head TMs

• Multi-dimensional tapes

6.4 Decidability and Recognizability

• Turing-decidable (recursive): Language L such that some TM always halts and correctly answers membership

• Turing-recognizable (recursively enumerable): Language L such that some TM accepts strings in L (may loop on strings not in L)

Unit 7: Computability and Undecidability

7.1 The Church-Turing Thesis

Thesis: Any effectively computable function can be computed by a Turing machine. This is not a theorem but a claim about the nature of computation, universally accepted.

7.2 The Halting Problem

The Halting Problem is the problem of determining, given a description of a program/algorithm and its input, whether the program will eventually halt .

Theorem (Turing, 1936) : The Halting Problem is undecidable—no Turing machine can solve it for all inputs.

Proof Sketch: Assume a TM H exists that decides halting. Construct a TM D that uses H to create a contradiction when D is run on its own description.

7.3 Other Undecidable Problems

• Post Correspondence Problem

• Entscheidungsproblem (first-order logic validity)

• Determining whether a CFG is ambiguous

• Determining whether two CFLs are equal

• Hilbert’s 10th problem (integer solutions to Diophantine equations)

7.4 Rice’s Theorem

Rice’s Theorem: Any non-trivial semantic property of programs (properties about the function computed, not the syntax) is undecidable.

Unit 8: Complexity Theory (Brief Introduction)

8.1 Time Complexity Classes

• P: Languages decidable in polynomial time by a deterministic TM

• NP: Languages decidable in polynomial time by a non-deterministic TM

• EXP: Languages decidable in exponential time

8.2 Space Complexity Classes

• Log: Languages decidable in logarithmic space

• NLog: Languages decidable in logarithmic space by non-deterministic TM

• PSPACE: Languages decidable in polynomial space

8.3 Relationships

Summary

Theory of Automata provides the essential foundation for understanding computation:

• Mathematical preliminaries (sets, functions, strings, languages) establish the formal basis

• Finite automata (DFA, NFA) recognize regular languages and have no temporary memory

• Regular expressions are algebraically equivalent to finite automata (Kleene’s Theorem)

• Context-free grammars generate languages using production rules and correspond to pushdown automata

• Turing machines are the most powerful model, capturing the essence of algorithms

• Computability theory reveals fundamental limitations: there are problems no computer can solve

• Complexity theory classifies problems by the resources (time, space) required to solve them

These concepts are not merely theoretical—they have direct applications in compiler design (parsing, CFGs), text processing (regular expressions), software verification, programming language design, and natural language processing

Study Notes: CS-511 Artificial Intelligence

Course Overview

Artificial Intelligence (AI) is the discipline concerned with building systems that think and act like humans or rationally on some absolute scale . This course provides a comprehensive introduction to the field, covering both foundational concepts and modern methods. The topics include intelligent agents, problem-solving via search, game playing, knowledge representation, logical and probabilistic reasoning, machine learning, and practical applications .

Course Objectives :

• Understand the fundamental principles and techniques of artificial intelligence

• Learn how to formulate and solve problems using AI algorithms

• Apply AI methods to real-world problems

• Gain hands-on experience through programming exercises and projects

• Explore both deterministic and probabilistic approaches to AI

Unit 1: Introduction to Artificial Intelligence

1.1 What is Artificial Intelligence?

AI can be viewed from four perspectives, organized along two dimensions: human vs. rational, and thought vs. action :

The rational agent approach is most widely adopted because it is more general than the “laws of thought” approach and more amenable to scientific development than approaches based on human behavior.

1.2 Foundations of AI

AI draws upon multiple disciplines:

• Philosophy: Logic, reasoning, mind as physical system

• Mathematics: Formal logic, probability, computation, algorithms

• Economics: Decision theory, game theory, utility

• Neuroscience: Physical substrate for mental activity

• Psychology: Human behavior, perception, language

• Computer engineering: Hardware, faster machines

• Control theory: Feedback, optimal control

• Linguistics: Knowledge representation, grammar

1.3 History of AI

1.4 Intelligent Agents

An agent is anything that can perceive its environment through sensors and act upon that environment through actuators .

Agent Function: Maps percept sequences to actions: f: P* → A

Agent Program: Implementation of the agent function

Performance Measure: Evaluates how well the agent achieves its goals

Types of Agents:

1.5 Environments

Environments can be characterized by properties :

Unit 2: Problem Solving and Search

2.1 Problem-Solving Agents

A problem-solving agent decides what to do by finding sequences of actions that lead to desirable states. The problem-solving approach consists of:

1. Goal formulation: Set of desirable world states

2. Problem formulation: Define states and actions to consider

3. Search: Find sequence of actions to reach goal

4. Execution: Follow recommended action sequence

2.2 Problem Formulation

A problem is defined by five components:

The state space forms a graph where nodes are states and edges are actions.

Example: 8-puzzle

• States: Configuration of tiles

• Initial state: Any given configuration

• Actions: Move blank left, right, up, down

• Transition model: New configuration after move

• Goal test: Check if goal configuration reached

• Path cost: Number of moves (each move cost 1)

2.3 Tree Search Algorithms

Basic tree search algorithm:

function TREE-SEARCH(problem):
    frontier ← {initial state}
    loop:
        if frontier empty: return failure
        node ← pop from frontier
        if node is goal: return solution
        frontier ← frontier + expand(node)

Search strategies differ in how they choose which node to expand next.

2.4 Uninformed Search Strategies

Uninformed (blind) search strategies have no additional information about states beyond problem definition.

Where:

• b = branching factor

• d = depth of shallowest solution

• m = maximum depth of state space

• l = depth limit

• C* = optimal solution cost

• ε = minimum edge cost

Bidirectional search runs two simultaneous searches—forward from initial state and backward from goal—hoping they meet in the middle. Complexity: O(bᵈ/²).

2.5 Informed (Heuristic) Search Strategies

Informed search uses domain-specific knowledge in the form of a heuristic function h(n) = estimated cost of cheapest path from node n to goal.

Greedy Best-First Search:

• Evaluates nodes using only heuristic: f(n) = h(n)

• Expands node closest to goal

• Fast but not optimal, incomplete

*A Search**:

• Combines path cost and heuristic: f(n) = g(n) + h(n)

• Where g(n) = actual cost from start to n

• Optimal if heuristic is admissible (never overestimates true cost)

• Optimally efficient for given heuristic

Properties of A*:

• Complete

• Optimal if heuristic admissible

• Time complexity: exponential in relative error of heuristic

• Space complexity: exponential (keeps all nodes in memory)

Heuristic Design:

• Relaxed problem: Remove constraints to generate simpler problem

• Pattern databases: Store exact solution costs for subproblems

• Dominance: If h₂(n) ≥ h₁(n) for all n, then h₂ dominates h₁ and is better for search

2.6 Local Search and Optimization

Local search algorithms operate on complete state descriptions, moving to neighbors of current state.

Unit 3: Adversarial Search and Game Playing

3.1 Games as Search Problems

Games are multi-agent environments where agents have conflicting goals. Game characteristics:

• Deterministic, turn-taking, perfect information: Chess, Go, Checkers

• Stochastic: Backgammon (dice rolls)

• Partial information: Poker, Bridge

Game formulation:

3.2 Minimax Algorithm

Idea: Optimal strategy leads to outcome at least as good as any other strategy when playing against optimal opponent.

Algorithm:

function MINIMAX(state):
    if TERMINAL(state): return UTILITY(state)
    if player == MAX: return max over actions of MINIMAX(RESULT(state, a))
    if player == MIN: return min over actions of MINIMAX(RESULT(state, a))

Properties:

3.3 Alpha-Beta Pruning

Idea: Prune branches that cannot affect final decision.

If at a MAX node, current value v ≥ β, further exploration is useless (MIN will avoid this branch).
If at a MIN node, current value v ≤ α, further exploration is useless (MAX will avoid this branch).

Effectiveness: With perfect ordering, reduces effective branching factor to approximately √b, allowing search twice as deep.

3.4 Imperfect Real-Time Decisions

For large games, cannot search to terminal nodes:

• Use evaluation function to estimate utility of non-terminal states

• Cutoff test replaces terminal test (depth limit + quiescence)

• Forward pruning ignores unpromising moves

Unit 4: Knowledge Representation and Reasoning

4.1 Knowledge-Based Agents

A knowledge-based agent maintains internal knowledge about the world and uses reasoning to decide actions.

Components:

4.2 Logic and Representation

4.3 First-Order Logic

Syntax:

• Constants: Objects (A, 2, John)

• Predicates: Relations (Brother, >)

• Functions: Map objects to objects (father-of)

• Variables: Placeholders (x, y)

• Connectives: ∧, ∨, ¬, ⇒, ⇔

• Quantifiers: ∀ (for all), ∃ (there exists)

Example: “All students are smart”
∀x Student(x) ⇒ Smart(x)

4.4 Inference in First-Order Logic

• Forward chaining: Start with known facts, apply implications to derive new facts

• Backward chaining: Start with query, work backwards to find supporting facts

• Resolution: Refutation proof by contradiction

Unification: Find substitution that makes two logical expressions identical.

4.5 Knowledge Engineering

Process of building knowledge base:

1. Identify task

2. Assemble relevant knowledge

3. Decide on vocabulary

4. Encode general knowledge

5. Encode specific problem instances

6. Pose queries and debug

Unit 5: Reasoning Under Uncertainty

5.1 Uncertainty in AI

Sources of uncertainty:

5.2 Probability Basics

• Prior probability: P(A) unconditional probability

• Conditional probability: P(A|B) = P(A∧B)/P(B)

• Chain rule: P(A∧B) = P(A|B)P(B) = P(B|A)P(A)

• Bayes’ rule: P(A|B) = P(B|A)P(A)/P(B)

Random variables: Represent aspects of world (Weather = sunny)

5.3 Bayesian Networks (Bayes Nets)

Graphical representation of probabilistic relationships:

Independence: Nodes independent given parents (local Markov property)

Inference: Compute posterior probability of query variables given evidence.

5.4 Markov Decision Processes (MDPs)

Framework for decision-making under uncertainty :

Components:

• Set of states S

• Set of actions A

• Transition model T(s, a, s’) = P(s’ | s, a)

• Reward function R(s, a, s’)

• Discount factor γ (0 ≤ γ ≤ 1)

Policy: π: S → A (action to take in each state)
Value function: Expected cumulative discounted reward

5.5 Reinforcement Learning

Learning from feedback rather than supervised examples :

• Agent interacts with environment

• Reward signal indicates success

• Goal: Learn policy maximizing cumulative reward

Key algorithms:

• Q-learning (model-free)

• SARSA

• Deep Q-Networks (DQN)

• Policy gradient methods

Unit 6: Machine Learning Fundamentals

6.1 Learning Paradigms

6.2 Supervised Learning

Classification: Assign discrete labels to inputs

Regression: Predict continuous values

• Linear regression

• Polynomial regression

• Neural networks

Key concepts:

• Training set, test set, validation set

• Overfitting, underfitting

• Bias-variance tradeoff

• Cross-validation

6.3 Unsupervised Learning

Clustering: Group similar examples

• k-means

• Hierarchical clustering

• DBSCAN

Dimensionality reduction: Reduce number of features

Unit 7: Deep Learning

7.1 Neural Networks Foundations

Artificial neuron: Weighted sum of inputs passed through activation function

Common activation functions:

Multi-layer perceptron (MLP) : Input layer, hidden layers, output layer

7.2 Training Neural Networks

• Loss functions: MSE (regression), cross-entropy (classification)

• Backpropagation: Compute gradients via chain rule

• Gradient descent: Update weights in direction of negative gradient

• Optimizers: SGD, Momentum, Adam, RMSprop

7.3 Deep Learning Architectures

Unit 8: Natural Language Processing

8.1 Text Processing Fundamentals

• Tokenization: Splitting text into words/subwords

• Stemming/Lemmatization: Reducing words to base form

• Part-of-speech tagging: Identifying word types

• Named entity recognition: Identifying entities (person, location, organization)

8.2 Word Representations

• Bag-of-words: Simple count vectors (loses word order)

• TF-IDF: Term frequency-inverse document frequency

• Word embeddings: Dense vector representations

• Word2Vec, GloVe: Pre-trained word vectors

• Contextual embeddings: ELMo, BERT, GPT

8.3 Sequence Models

• Language modeling: Predict next word given previous

• Machine translation: Convert text between languages

• Text summarization: Generate concise summaries

• Question answering: Answer questions based on context

• Dialogue systems: Conversational agents

8.4 Large Language Models

• Transformer architecture: Self-attention, multi-head attention

• Pre-training and fine-tuning: Learn general representations, adapt to tasks

• Prompt engineering: Designing effective prompts for desired outputs

• In-context learning: Learning from examples in prompt

• Applications: ChatGPT, GPT-4, Llama, Claude

Unit 9: Computer Vision

9.1 Image Understanding

• Image classification: Assign category to entire image

• Object detection: Locate and classify objects

• Image segmentation: Pixel-level classification

• Semantic segmentation: Label each pixel by class

• Instance segmentation: Distinguish individual objects

9.2 Advanced Vision Applications

• Action recognition: Identify activities in video

• Image generation: Create realistic images (GANs, diffusion models)

• Medical imaging: Disease detection, organ segmentation

• Face recognition: Identify individuals

• Optical character recognition (OCR) : Extract text from images

Unit 10: Generative AI

10.1 Generative Models

Models that learn to generate new data samples from the same distribution as training data.

Types:

• Autoregressive models: Generate sequentially (PixelRNN, WaveNet)

• Variational Autoencoders (VAE) : Probabilistic latent variable models

• Generative Adversarial Networks (GAN) : Generator + discriminator adversarial training

• Diffusion models: Gradually denoise random noise

• Flow-based models: Invertible transformations

10.2 Applications of Generative AI

• Text generation: Stories, articles, code, poetry

• Music composition: Generate melodies, harmonies

• Creative content generation: Art, design, video

• Data augmentation: Generate synthetic training data

• Drug discovery: Generate molecular structures

10.3 Challenges and Ethical Considerations

• Fairness and bias: Models can perpetuate or amplify biases

• Explainability: Understanding model decisions

• Hallucination: Generating false but plausible information

• Misinformation: Deepfakes, fake content

• Intellectual property: Ownership of generated content

• Safety and alignment: Ensuring AI behaves as intended

Unit 11: Ethics and Future of AI

11.1 AI Ethics Framework

• Transparency: Open about AI capabilities and limitations

• Fairness: Avoid discrimination and bias

• Accountability: Clear responsibility for AI decisions

• Privacy: Protect personal data

• Safety: Ensure systems operate reliably

• Human control: Maintain meaningful human oversight

11.2 AI Safety

• Alignment problem: Ensuring AI goals align with human values

• Robustness: Performing reliably under distribution shift

• Verification: Proving system properties

• Control: Maintaining ability to override AI decisions

11.3 Future Directions

• AGI (Artificial General Intelligence) : Human-level intelligence across domains

• Embodied AI: Robots interacting with physical world

• Neuro-symbolic AI: Combining neural networks with symbolic reasoning

• Quantum AI: Leveraging quantum computing for AI

• AI for science: Accelerating scientific discovery

Summary

Artificial Intelligence provides the essential foundation for understanding how to build intelligent systems:

• Intelligent agents perceive and act in environments to achieve goals

• Search algorithms (uninformed, informed, adversarial) find action sequences to solve problems

• Knowledge representation using logic enables reasoning about the world

• Probabilistic reasoning handles uncertainty through Bayesian networks and MDPs

• Machine learning enables systems to improve from data

• Deep learning provides powerful architectures for perception, language, and generation

• Natural language processing enables communication with machines

• Computer vision extracts meaning from visual data

• Generative AI creates novel content across modalities

• Ethical considerations are essential for responsible AI development

These concepts prepare students for advanced study in specialized areas (computer vision, NLP, robotics, machine learning) and for careers developing AI systems that solve real-world problems

Study Notes: CS-513 Web Programming

Course Overview

Web Programming is a comprehensive course covering the principles, technologies, and practices for developing modern web applications. The course objectives include gaining proficiency in client-side and server-side programming, understanding web architecture, and building dynamic, database-driven websites . The 3(2-1) credit structure combines theoretical concepts with hands-on laboratory work .

Unit 1: Introduction to Web Programming

1.1 Web Fundamentals

The World Wide Web (WWW) is an information system where documents and resources are identified by URLs and accessible via the internet. Key concepts include:

1.2 Evolution of the Web

1.3 Web Application Architecture

Traditional Architecture:

Modern Single-Page Application (SPA) Architecture:

• Initial page load includes application framework

• Subsequent interactions load only data (JSON/XML)

• Client-side rendering updates view dynamically

Three-Tier Architecture:

• Presentation Tier: User interface (HTML, CSS, JavaScript)

• Application Tier: Business logic (Server-side code)

• Data Tier: Database (MySQL, Oracle, MongoDB)

Unit 2: HTML and CSS Fundamentals

2.1 HTML (HyperText Markup Language)

HTML provides the structure and content of web pages.

Basic HTML Document Structure:

<!DOCTYPE html>
<html>
<head>
    <title>Page Title</title>
    <meta charset="UTF-8">
    <link rel="stylesheet" href="styles.css">
</head>
<body>
    <header>
        <h1>Main Heading</h1>
        <nav>
            <ul>
                <li><a href="index.html">Home</a></li>
                <li><a href="about.html">About</a></li>
            </ul>
        </nav>
    </header>
    <main>
        <section>
            <h2>Section Title</h2>
            <p>Paragraph of text.</p>
        </section>
    </main>
    <footer>
        <p>&copy; 2025</p>
    </footer>
</body>
</html>

Common HTML Elements:

2.2 HTML Forms

Forms are essential for collecting user input:

<form action="process.php" method="POST">
    <label for="name">Name:</label>
    <input type="text" id="name" name="name" required>
    
    <label for="email">Email:</label>
    <input type="email" id="email" name="email" required>
    
    <label for="password">Password:</label>
    <input type="password" id="password" name="password">
    
    <label for="country">Country:</label>
    <select id="country" name="country">
        <option value="us">United States</option>
        <option value="ca">Canada</option>
    </select>
    
    <label>
        <input type="checkbox" name="subscribe"> Subscribe to newsletter
    </label>
    
    <button type="submit">Submit</button>
</form>