Unit - 1 : Discrete Structures and Optimization

Topic Explanation Example

Study of simple statements that are
Propositional Logic "It is raining."
either true or false.
Logic that deals with predicates,
Predicate Logic which are statements containing "x is greater than 5."
variables.
Propositional Logical equivalences between "¬(A ∧ B) is the
Equivalences propositions. same as (¬A ∨ ¬B)"
Standard ways to write logical Conjunctive Normal
Normal Forms
statements. Form (CNF)
Predicates are properties, and
Predicates and
quantifiers specify the scope (e.g., "For all x, x > 0."
Quantifiers
all, some).
"For all x, there
Quantifiers within quantifiers in
Nested Quantifiers exists a y such that x
logical statements.
+ y = 0."
Logical rules to deduce new "If A, then B. A is
Rules of Inference
statements from given ones. true, so B is true."
Operations like union, intersection,
Set Operations A∪B
difference on sets.
Representation and Ways to show relationships
A graph or matrix
Properties of Relations between elements.
Relations that are reflexive,
Equivalence Relations "Is equal to" relation
symmetric, and transitive.
A relation that is reflexive, "Is less than or equal
Partially Ordering
antisymmetric, and transitive. to" on numbers
Fundamental counting principles Counting outcomes
Basics of Counting
like addition and multiplication. in a coin toss
If more items than containers, at
Pigeonhole Principle least one container has more than 10 pigeons in 9 holes
one item.
Permutations and Different ways to arrange or select Arranging books on a
Combinations items. shelf
Inclusion-Exclusion Method to count elements in Counting students in
Principle overlapping sets. multiple clubs
 Topic Explanation Example
Mathematical Proof technique for proving Proving sum of first
Induction statements about integers. n numbers
Study of chance and likelihood of Rolling a die and
Probability
events. getting a 6
Updating probability
Formula to find conditional
Bayes’ Theorem after seeing new
probabilities.
evidence
Sets with an operation that
Integers with
Groups combines any two elements to form
addition
a third element.
Smaller groups within a larger Even integers under
Subgroups
group. addition
Like groups but without the Positive integers
Semi Groups
requirement of an identity element. under multiplication
Product and Quotients Combining and dividing structures Direct product of two
of Algebraic Structures in algebra. groups
Mapping between structures that Rotations of a square
Isomorphism
shows a one-to-one correspondence. and its symmetries
Structure-preserving map between Mapping of integers
Homomorphism
two algebraic structures. to their remainders
An isomorphism from a structure to Rotating a shape
Automorphism
itself. around its center
Integers with
Sets with two operations satisfying
Rings addition and
certain properties.
multiplication
Rings where the product of non-
Integral Domains Rational numbers
zero elements is non-zero.
Integral domains where division is
Fields Real numbers
possible.
Applications of Group Uses of group theory in real-life
Cryptography
Theory problems.
Network of friends
Simple Graph A set of points connected by lines.
on social media
A graph with multiple edges Multiple roads
Multigraph
between some vertices. between cities
 Topic Explanation Example
A graph where edges have weights Road map with
Weighted Graph
or costs. distances
Route from home to
Paths and Circuits Ways to traverse a graph.
school
Shortest Paths in Finding the minimum path in terms Shortest route on
Weighted Graphs of weight. Google Maps
Route to traverse
Eulerian Paths and Paths that visit every edge exactly
every bridge in a city
Circuits once.
once
Hamiltonian Paths and Paths that visit every vertex exactly Route to visit every
Circuits once. city exactly once
A graph that can be drawn without
Planner graph Map of subway lines
crossing edges.
Assigning colors to vertices so Coloring a map with
Graph Coloring
adjacent ones are different. minimum colors
Graphs whose vertices can be Teams in a
Bipartite Graphs
divided into two disjoint sets. tournament
Trees and Rooted Connected graphs with no cycles,
Family tree
Trees one root.
Codes where no code is a prefix of
Prefix Codes Morse code
another.
Depth-first search in
Tree Traversals Ways to visit all nodes in a tree.
a tree
Subgraphs that include all vertices;
Spanning Trees and sets of edges whose removal Minimum spanning
Cut-Sets increases the number of tree in a network
components.
Boolean Functions and Logic gates in
Functions with binary variables.
its Representation circuits
Simplifications of Reducing complexity of Boolean
Karnaugh maps
Boolean Functions functions.
Maximizing profit
Optimization of a linear objective
Linear Programming with resource
function.
constraints
Solving linear programs using a Finding feasible
Graphical Solution
graph. region on a graph
 Topic Explanation Example
Simplex and Dual Algorithms to solve linear Iterative methods for
Simplex Method programming problems. optimization
Impact of price
Study of how changes in parameters
Sensitivity Analysis change on supply
affect the solution.
chain
Optimization where variables are Scheduling tasks
Integer Programming
integers. with whole numbers
Transportation and Allocating resources
Optimization models for logistics.
Assignment Models efficiently
Project management tools for Charting tasks in a
PERT-CPM
planning and scheduling. project
Diagram Visual representation of tasks and
Gantt chart
Representation dependencies.
Critical Path Finding the longest path through a Determining project
Calculations project network. duration
Smoothing
Resource Levelling Balancing resource use over time.
workforce demands
Cost Consideration in Evaluating costs in project Budgeting for a
Project Scheduling timelines. construction project
 Unit - 2 : Computer System Architecture

Topic Explanation Example

Electronic devices that
Digital Computers Your laptop or smartphone.
process digital data.
Basic building blocks of
AND gate that outputs true
Logic Gates digital circuits that perform
only if both inputs are true.
logical operations.
Mathematical notation for A + B = C, where C is true
Boolean Algebra
expressing logic circuits. if A or B is true.
Techniques to simplify Karnaugh map simplifies
Map Simplifications
Boolean expressions. logic expressions.
Circuits where the output is
Combinational A circuit that adds two
only based on the current
Circuits binary numbers.
inputs.
Basic memory units that store Used in memory storage
Flip-Flops
one bit of data. like RAM.
Circuits where the output
Sequential Circuits depends on current and A clock-driven counter.
previous inputs.
A set of electronic circuits on
Microprocessors in
Integrated Circuits one small flat piece of
computers.
semiconductor material.
Converts binary input to
Circuits that convert coded
Decoders one active output in digital
inputs into coded outputs.
displays.
Circuits that select one of A switch that connects
Multiplexers many inputs to a single multiple inputs to one
output. output line.
Register holds a data value;
Registers and Storage devices that hold data
counter keeps track of the
Counters and count events.
number of occurrences.
RAM stores the data
Component that stores data
Memory Unit currently being used by the
and instructions.
computer.
Different kinds of data stored
Data Types Integer, float, character.
and processed by computers.
 Topic Explanation Example
Number Systems and Methods to represent numbers Binary (1010) to Decimal
Conversion and convert between systems. (10).
Methods to simplify Two's complement of 2 in
Complements subtraction operations in binary is 1110 for
binary. representing -2.
Representation of numbers
Fixed Point Storing 3.14 as 314 in fixed
with a fixed number of digits
Representation point form.
after the decimal point.
Representation of real
Floating Point 3.14 represented as 3.14 x
numbers in scientific notation
Representation 10^0.
for a wide range of values.
Error Detection Methods to detect errors in Parity bit checks for data
Codes data transmission. errors in transmitted data.
Algorithms for performing
Computer Binary addition and
arithmetic operations on
Arithmetic subtraction.
numbers.
Register Transfer Notation to describe MOV A, B (move content
Language operations in registers. of B to A).
Methods to transfer data
Bus and Memory Data moving from RAM to
between registers, memory,
Transfers CPU.
and processors.
Arithmetic, Logic, Addition (ADD), Logical
Basic operations performed at
and Shift AND (AND), Bit shifting
the micro level in CPUs.
Microoperations (SHL).
Stored Program A program stored in RAM
Structure where instructions
Organization and executed by CPU
are stored in memory.
Instruction Codes instructions.
Program Counter (PC)
Small storage locations in the
Computer Registers holds the address of the
CPU.
next instruction.
Computer Commands that the CPU ADD, SUB, JMP (jump to
Instructions executes. another instruction).
Mechanism to control the
Clock signals synchronize
Timing and Control timing of operations within
CPU operations.
the CPU.
 Topic Explanation Example
The sequence of steps the
Fetch, decode, execute, and
Instruction Cycle CPU takes to execute an
store cycle.
instruction.
Memory-Reference Instructions that involve LOAD and STORE
Instructions accessing memory locations. instructions.
Methods for data exchange Keyboard input, printer
Input-Output, between the computer and output, and interrupt
Interrupt external devices, and handling handling by CPU when a
interruptions. key is pressed.
The lowest-level
Machine Language programming language Binary code (101010).
understood by computers.
A low-level programming
MOV AX, BX (move
Assembly Language language using symbolic
content of BX to AX).
code.
Tool that converts assembly Converts MOV AX, BX to
Assembler
language to machine code. 101010 binary code.
Repeated execution of a set of For loop repeating a block
Program Loops
instructions. of code.
A set of instructions designed
A function that calculates
Subroutines to perform a frequently used
the sum of two numbers.
operation.
Code to read data from a
Input-Output Writing programs to manage
keyboard and display on
Programming I/O operations.
screen.
Memory used to store control Stores microinstructions in
Control Memory information for a microprogrammed control
microprogramming. unit.
Determining the order in Fetching next instruction
Address Sequencing
which addresses are accessed. address from memory.
Creation of the component Hardwired control unit vs.
Design of Control
that directs the operations of microprogrammed control
Unit
the processor. unit.
Arrangement of a set of
General Register AX, BX, CX, DX in x86
registers in the CPU for
Organization architecture.
general use.
 Topic Explanation Example
Data structure where data is
Call stack for function calls
Stack Organization added/removed in a Last In
in programming.
First Out (LIFO) manner.
Format for ADD instruction
Different ways to encode
Instruction Formats in x86: opcode, destination,
instructions for the CPU.
source.
Techniques to specify the Immediate, direct, indirect
Addressing Modes
operands of an instruction. addressing.
CPU design with a small,
RISC Computer highly optimized instruction ARM processors.
set.
CPU design with a large set of
CISC Computer Intel x86 processors.
instructions.
Using multiple processors
Simultaneous processing of
Parallel Processing to run different parts of a
multiple tasks.
program.
Technique where multiple CPU fetches next
Pipelining instruction phases are instruction while executing
overlapped. current one.
Breaking down a
Division of an arithmetic multiplication operation
Arithmetic Pipeline
operation into multiple stages. into steps that can be
processed simultaneously.
Overlapping the execution of Fetch-decode-execute
Instruction Pipeline
multiple instructions. overlap in modern CPUs.
SIMD (Single Instruction,
Processing of multiple data
Vector Processing Multiple Data) operations
elements in parallel.
in graphics processing.
Specialized processors for Used in scientific
Array Processors performing operations on computations and
large arrays of data. simulations.
External devices connected to
Peripheral Devices Keyboard, mouse, printer.
a computer.
Interface for data exchange
Input-Output USB ports for connecting
between computer and
Interface external devices.
peripherals.
 Topic Explanation Example
Asynchronous Data Data transfer without a Data sent from keyboard to
Transfer synchronized clock signal. CPU at irregular intervals.
Different methods to transfer
DMA (Direct Memory
Modes of Transfer data between computer
Access), programmed I/O.
components.
Mechanism to handle multiple CPU prioritizes a printer
Priority Interrupt interrupts by prioritizing interrupt over a keyboard
them. interrupt.
Direct Memory Access,
allows devices to access A hard drive transferring
DMA
memory without CPU data directly to RAM.
intervention.
Serial Data transmission one bit at a RS232 serial port
Communication time over a single channel. communication.
Primary storage area for data
Main Memory and instructions currently RAM in your computer.
being used.
Secondary storage for data not
Auxillary Memory Hard drives, SSDs.
in immediate use.
Memory that allows data to be Cache memory that speeds
Associative Memory accessed based on content up access to frequently
rather than address. used data.
Fast, small memory that
CPU cache holding data for
Cache Memory stores frequently accessed
quick access.
data to speed up processes.
Technique that uses disk Swapping data between
Virtual Memory space as an extension of RAM and hard drive to
RAM. simulate more memory.
Memory Hardware that manages MMU (Memory
Management memory access and Management Unit) in a
Hardware organization. CPU.
A server with multiple
Systems with multiple CPUs
Multiprocessors processors handling large
working together.
workloads.
 Topic Explanation Example
Bus, ring, mesh networks
Interconnection Architectures that connect
connecting CPUs in a
Structures multiple processors.
multiprocessor system.
Methods to manage resource Arbitration mechanisms to
Interprocessor
access conflicts among ensure orderly access to
Arbitration
processors. shared memory.
Message passing,
Interprocessor Techniques for processors to
semaphores for
Communication and communicate and synchronize
coordinating tasks in a
Synchronization tasks.
multiprocessor system.
Ensuring consistency of data Protocols to keep data
Cache Coherence stored in cache memory in uniform across all caches in
multiprocessor systems. a system.
Modern Intel and AMD
CPUs with multiple
processors with multiple
Multicore Processors processing units on a single
cores for better
chip.
performance.

.
 Unit - 3 : Programming Languages and Computer Graphics
Topic Explanation Example
Basic ideas and
Programming structures that
In Python, print("Hello, World!") uses the
Language define a
concept of a function to display text.
Concepts programming
language.
Different styles
Paradigms and and approaches Object-oriented programming in Java uses
Models to classes and objects.
programming.
Tools and
Programming settings used to Visual Studio Code is a popular programming
Environments develop environment for various languages.
software.
Simulated
Virtual computers and
Java Virtual Machine (JVM) allows Java
Computers and when variables
programs to run on different hardware.
Binding Times are assigned
values.
Rules that
Programming define the
In Python, if x > 5: is a syntax for a conditional
Language structure of
statement.
Syntax code in a
language.
Steps involved
in converting
Stages in Compiling, linking, and running are stages in
code to
Translation translating C code.
executable
programs.
Mathematical
Formal models
Finite State Machines model the behavior of
Transition describing how
regular expressions.
Models program states
change.
 Topic Explanation Example
Characteristics
Properties of
of data types An integer in Python can hold whole numbers
Types and
and their like 3, 4, and 5.
Objects
instances.
Basic single-
Scalar and value types and
An integer is scalar, while a list in Python is
Composite Data complex types
composite.
Types made of
multiple values.
Basic building
Keywords like int, float, and symbols like +, - in
Tokens blocks of a
C.
program.
Names used to
identify
Identifiers int age; declares an identifier age in C.
variables,
functions, etc.
Types of data a
Data Types language int, float, and char are data types in C.
supports.
Control the
Sequence order of if, else, while, and for are control statements in
Control execution of C.
statements.
Mechanisms to
Subprogram
define and call void functionName() {} defines a function in C.
Control
functions.
Collection of
Arrays elements of the int arr[10]; declares an array of integers in C.
same type.
Custom data
types that struct { int id; char name[20]; } defines a
Structures
group different structure in C.
types of data.
A data type that
can hold
Union union { int i; float f; } defines a union in C.
different types
of data, but
 Topic Explanation Example
only one at a
time.
Sequence of
String char str[] = "Hello"; declares a string in C.
characters.
Variables that
Pointers store memory int *ptr; declares a pointer to an integer in C.
addresses.
Blocks of code
int add(int a, int b) { return a + b; } defines a
Functions that perform
function in C.
specific tasks.
Reading from
FILE *fp = fopen("[Link]", "r"); opens a file for
File Handling and writing to
reading in C.
files.
Inputs passed
Command Line to a program int main(int argc, char *argv[]) in C allows
Arguments when it is handling command line arguments.
executed.
Directives for
the compiler to
#include <stdio.h> includes standard input-
Preprocessors process before
output header in C.
actual
compilation.
Blueprint for
Class creating objects class Car { } in C++.
in OOP.
Instance of a Car myCar; creates an object of the Car class in
Object
class. C++.
Creating an
Instantiation object from a Car myCar = new Car(); in C++.
class.
Mechanism for
a new class to
Inheritance use properties class ElectricCar : public Car { } in C++.
of an existing
class.
 Topic Explanation Example
Wrapping data
and methods Private variables and public methods in a C++
Encapsulation
into a single class.
unit (class).
A class that
cannot be
Abstract Class instantiated and class Shape { virtual void draw() = 0; } in C++.
is meant to be
subclassed.
Ability to use a
Overloading functions or using virtual functions
Polymorphism function in
in C++.
different ways.
Basic elements
of a program
such as
Tokens int, float, return in C++.
keywords,
operators, and
identifiers.
Names given to
Identifiers variables, int age; where age is an identifier in C++.
functions, etc.
Storage
locations that
hold values
Variables and
which can int x = 5; const int y = 10; in C++.
Constants
change
(variables) or
not (constants).
Symbols that
perform
Operators operations on +, -, *, / in C++.
variables and
values.
Statements that
Control
control the flow if, else, while, for in C++.
Statements
of execution.
 Topic Explanation Example
Functions Methods of
Parameter giving input to void func(int a, int b); in C++.
Passing functions.
Functions in a
base class that
Virtual
can be virtual void display(); in a C++ class.
Functions
overridden in
derived classes.
Special
functions for
Constructors
initializing and Car() { } and ~Car() { } in a C++ class.
and Destructors
cleaning up
objects.
Defining
multiple
functions with
Overloading void func(int a); void func(double a); in C++.
the same name
but different
parameters.
Writing generic
template <class T> class MyClass { T var; } in
Templates and reusable
C++.
code.
Managing
errors and
Exception and
unusual events try { } catch (exception e) { } in C++.
Event Handling
during program
execution.
Reading from
Streams and
and writing to ifstream inFile; ofstream outFile; in C++.
Files
files.
Programs that
Multifile Using #include to include headers and separate
are split into
Programs implementation files in C++.
multiple files.
Markup
language for <html><body>Hello, World!</body></html>
HTML
creating web creates a simple webpage.
pages.
 Topic Explanation Example
Dynamic
HTML, allows
Using JavaScript with HTML and CSS to create
DHTML interactive and
animations.
animated
websites.
Markup
language for
<note><to>Tove</to><from>Jani</from></note
XML storing and
> represents a note.
transporting
data.
Writing scripts
to automate
Scripting JavaScript code to validate a web form.
tasks on the
web.
Programming
public class HelloWorld { public static void
language for
Java main(String[] args) { [Link]("Hello,
building web
World!"); } } in Java.
applications.
Java programs
that run on a
A servlet handling form data submission in a
Servlets server and
web application.
handle web
requests.
Small Java
programs that A Java applet displaying an animation on a
Applets
run in a web webpage.
browser.
Hardware for
Video-Display
displaying Monitors, projectors, and VR headsets.
Devices
graphics.
Techniques for
Raster-Scan
rendering Raster-scan uses pixels (like in monitors),
and Random-
images on random-scan uses lines (like in vector displays).
Scan Systems
screens.
Graphics Displays High-resolution monitors used by graphic
Monitors designed for designers.
 Topic Explanation Example
high-quality
graphics.
Devices used to
Input Devices interact with Mouse, keyboard, and graphic tablets.
computers.
Basic elements
Points and Drawing a point or a line on a screen using
of computer
Lines coordinates.
graphics.
Methods to
Line Drawing
draw lines on a Bresenham's algorithm for line drawing.
Algorithms
screen.
Mid-Point Methods to
Circle and draw circles
Midpoint circle algorithm to draw a circle.
Ellipse and ellipses on
Algorithms a screen.
Scan Line Technique to
Polygon Fill fill polygons Filling a triangle on the screen with a solid color.
Algorithm with color.
Algorithms to
Boundary-Fill fill areas
Filling a closed area in a drawing program.
and Flood-Fill bounded by a
color or border.
Moving objects
Translation Shifting a shape 10 units to the right.
in graphics.
Changing the
Scaling Doubling the size of a square.
size of objects.
Rotating
Rotation objects around Rotating a triangle 45 degrees clockwise.
a point.
Mirroring
Reflection objects across Reflecting a shape across the x-axis.
an axis.
Shear Slanting the
Transformation shape of an Shearing a rectangle to create a parallelogram.
s object.
 Topic Explanation Example
Matrix
Using matrices
Representations
for geometric
and Using a matrix to rotate a point in 2D space.
transformations
Homogeneous
.
Coordinates
Combining
Composite multiple
Applying scaling and rotation together.
Transforms transformations
into one.
Converting
Transformation
points from one
s Between Converting 3D coordinates to 2D screen
coordinate
Coordinate coordinates.
system to
Systems
another.
Steps to create
Viewing
a view of a Transforming 3D objects to 2D for display.
Pipeline
scene.
Coordinate
Viewing
system for
Coordinate
viewing Setting up a camera in 3D space to view objects.
Reference
transformations
Frame
.
Window to Mapping a
View-Port portion of the
Zooming into a specific part of a drawing.
Coordinate scene to the
Transformation display area.
Functions that
Viewing define how a glOrtho() in OpenGL to define orthographic
Functions scene is projection.
viewed.
Line and Methods to cut
Polygon lines and
Cohen-Sutherland line clipping algorithm.
Clipping polygons to fit
Algorithms within a view.
Representing
Polygon
3D objects A 3D model of a cube made of square polygons.
Surfaces
using polygons.
 Topic Explanation Example
Surfaces
Quadric defined by Representing a sphere or cylinder in 3D
Surfaces quadratic graphics.
equations.
Curves defined
Spline by
Using Bezier curves to draw smooth curves.
Representation mathematical
functions.
Types of spline
Bezier and B- Drawing a smooth curve with control points
curves used in
Spline Curves using Bezier curves.
graphics.
Smooth
Bezier and B- surfaces
Creating a smooth 3D surface with B-Splines.
Spline Surfaces defined by
spline curves.
Techniques to
Illumination simulate Phong shading model to add realistic lighting to
Models lighting in a 3D scene.
graphics.
Polygon Techniques to
Gouraud shading to smooth colors across a
Rendering draw and shade
polygon.
Methods polygons.
Steps and
Viewing coordinate
Converting 3D coordinates to 2D screen
Pipeline and systems for
coordinates in OpenGL.
Coordinates displaying a 3D
scene.
Techniques to
General project 3D
Projection scenes onto 2D Perspective projection to give a 3D effect on a
Transforms and and remove 2D screen.
Clipping parts outside
the view.
 Unit – 4 : Database Management Systems
Concept Explanation Example
Framework for organizing and Relational model organizes data
Data Models
defining data. in tables.
Structure defining a database's A database schema includes
Schemas
organization. tables and relationships.
Actual data stored in the A table row represents a data
Instances
database at a moment. instance.
Separates database into three User sees only the external
Three-Schema
layers: internal, conceptual, schema; not the internal
Architecture
external. storage.
Ability to change schema
Data Adding a column without
without altering the
Independence affecting existing queries.
application.
Database Languages to define, SQL for querying and updating
Languages manipulate, and control data. databases.
Centralized Single server hosts the entire Traditional databases on one
DBMS database. mainframe.
Client/Server Database functions are split Web applications with a
DBMS between clients and servers. database server.
Entity- Visual representation of
Diagram showing customers
Relationship database entities and
and orders relationship.
Diagram relationships.
Data organized in tables with Customer table with columns
Relational Model
rows and columns. for name, address.
Primary key constraint ensures
Constraints Rules enforcing data integrity.
unique IDs.
Relational Mathematical operations on Join operation combines data
Algebra tables. from two tables.
Relational Non-procedural query Query specifying conditions to
Calculus language. retrieve data.
Guidelines for relational Rule: All data must be
Codd Rules
database systems. accessible in table form.
SQL Data SQL statements to define
CREATE TABLE statement.
Definition database structure.
 Concept Explanation Example
Defines the type of data stored
Data Types Integer, text, date types.
in each column.
Constraints in
Rules applied to columns. NOT NULL constraint.
SQL
SQL Queries Statements to retrieve data. SELECT * FROM Customers;
INSERT INTO Customers
Insert Statement Adds new records to a table.
(Name) VALUES ('John');
DELETE FROM Customers
Delete Statement Removes records from a table.
WHERE Name = 'John';
UPDATE Customers SET
Update Statement Modifies existing records. Name = 'Jane' WHERE Name =
'John';
CREATE VIEW
Virtual tables representing ActiveCustomers AS SELECT
Views
data. * FROM Customers WHERE
Active = 1;
CREATE PROCEDURE
Stored Predefined SQL code executed
AddCustomer(Name
Procedures as a function.
VARCHAR);
CREATE FUNCTION
Functions SQL code that returns a value. GetCustomerCount()
RETURNS INT;
Database Actions executed in response Trigger on insert to log
Triggers to database events. changes.
Security vulnerability allowing
Input ' OR '1'='1' causes
SQL Injection unauthorized SQL code
unauthorized access.
execution.
Functional Relationship between columns If A determines B, knowing A
Dependencies ensuring consistency. means knowing B.
Process to minimize data Breaking a table into two to
Normalization
redundancy. remove duplicate data.
Steps to execute database Optimizing SELECT
Query Processing
queries efficiently. statements for speed.
Transaction Ensures database operations COMMIT and ROLLBACK
Processing are completed fully. statements.
 Concept Explanation Example
Concurrency Manages simultaneous data Locking rows during updates to
Control access. prevent conflicts.
Database Using backup to recover lost
Restores database after failure.
Recovery data.
Store data as objects, like in Object database storing user
Object Databases
OOP. objects.
Object-Relational Combines relational and object PostgreSQL with JSONB data
Databases database features. type.
Protects data from User authentication and access
Database Security
unauthorized access. control.
Temporal Database tracking history of
Handle time-varying data.
Databases changes.
Multimedia Store and manage multimedia Database containing images
Databases data. and videos.
Deductive Apply logical rules to derive Database using rules to infer
Databases data. new facts.
Database managing product
XML Databases Store and query XML data.
catalog in XML format.
Databases for mobile
Mobile Databases SQLite used in mobile apps.
applications.
Geographic
Database with maps and
Information Manage spatial data.
location data.
Systems
Genome Data Databases for genetic Database storing DNA
Management information. sequences.
Distributed Spread across multiple Data replicated across servers
Databases locations. in different regions.
Store and analyze large Central repository for business
Data Warehouses
volumes of data. analytics.
Discover patterns in large Finding customer buying
Data Mining
datasets. trends.
Online analytical processing Summarizing sales data across
OLAP
for data analysis. regions.
Online transaction processing Processing customer orders in
OLTP
for day-to-day operations. real-time.
 Concept Explanation Example
Identify relationships between
Association Rules Market basket analysis in retail.
data items.
Categorize data into Classifying emails as spam or
Classification
predefined groups. not.
Group similar data points Customer segmentation based
Clustering
together. on purchase behavior.
Regression Predict a continuous value. Predicting house prices.
Support Vector Supervised learning model for Classifying images of cats and
Machine classification/regression. dogs.
K-Nearest Classify based on the nearest Recommending movies based
Neighbour data points. on user similarity.
Hidden Markov Statistical model for sequential
Speech recognition systems.
Model data.
Condense data into a brief Generating executive
Summarization
summary. summaries from reports.
Dependency Model dependencies between Bayesian networks for
Modeling variables. probabilistic dependencies.
Study relationships in Analyzing social media
Link Analysis
networks. connections.
Sequencing Analyze sequence patterns in
DNA sequencing analysis.
Analysis data.
Social Network Study social structures using Analyzing influence in social
Analysis networks. media.
Big Data Volume, variety, velocity, and Analyzing large sets of social
Characteristics veracity of big data. media data.
Types of Big Structured, unstructured, semi-
Text, images, and logs.
Data structured.
Big Data Framework for processing big
Hadoop ecosystem.
Architecture data.
Processing model for large Counting word frequency in
Map-Reduce
data sets. documents.
Open-source framework for Distributed storage and
Hadoop
big data processing. processing.
Distributed File Manages files across multiple Hadoop Distributed File
System servers. System (HDFS).
 Concept Explanation Example
Non-relational databases for MongoDB storing JSON-like
NOSQL
flexible data models. documents.
Querying Methods to retrieve data from
Using MongoDB queries.
NOSQL NoSQL databases.
Managing Administering NoSQL
Indexing data in Couchbase.
NOSQL databases.
Organizing data for fast Creating indexes in
Indexing NOSQL
retrieval. Elasticsearch.
NoSQL databases hosted in
NOSQL in Cloud Amazon DynamoDB.
cloud environments.
 Unit – 5 : System Software and Operating System
Concept Explanation Example
Basic code the computer's
Machine Language hardware understands Binary code like 10101011
directly.
Low-level code that's slightly
Assembly Language easier to read than machine MOV AX, 1
language.
Programming languages that
High-Level
are easy for humans to Python, Java
Languages
understand.
Programs that translate high- Turning Python code into
Compilers
level code into machine code. binary code
Programs that execute high- Running JavaScript code in a
Interpreters
level code line by line. web browser
Bringing a program into Loading a game from the
Loading
memory for execution. hard drive
Combining multiple code files Creating a single program
Linking
into a single executable. from various modules
Adjusting program addresses Changing where a program
Relocation
to run in memory. runs in RAM
Shortcuts in code to simplify #define MAX 100 in C
Macros
tasks. programming
Tools to find and fix bugs in Using GDB to find errors in
Debuggers
programs. a program
The organization of an OS,
Operating System Windows has a GUI and
including its components and
Structure command-line interface
interactions.
Tasks and functions an OS
OS Operations and Managing files, running
performs for users and
Services programs
programs.
Requests programs make to
System Calls open() in C to open a file
the OS to perform tasks.
OS Design and The creation and setup of an
Designing Linux kernel
Implementation operating system.
 Concept Explanation Example
Starting up the computer and Turning on a PC and loading
System Boot
loading the OS. Windows
Managing the execution order Windows Task Manager
Process Scheduling
of programs. allocating CPU time
Actions taken on running Starting, pausing, or stopping
Process Operations
programs. a program
Interprocess Ways programs talk to each Chat applications sending
Communication other. messages
Web browsers (clients)
Client-Server Programs interacting over a
requesting data from
Systems network.
websites (servers)
Process Ensuring programs run Multiple programs accessing
Synchronization together without conflicts. the same file without errors
Critical-Section Managing access to shared Two bank transactions
Problem resources without conflict. updating the same account
Ensuring two programs don’t
Algorithm for process
Peterson’s Solution access a critical section
synchronization.
simultaneously
Tools to manage resource Traffic lights controlling cars
Semaphores
access among processes. at an intersection
Writing programs to use A video editing software
Multicore
multiple CPU cores using all CPU cores to render
Programming
effectively. faster
Multithreading Patterns for using multiple Web servers handling
Models threads in programs. multiple requests at once
Tools to help implement Using pthreads in C
Thread Libraries
multithreading. programming
Automatically managing
OpenMP automatically
Implicit Threading threads without programmer
parallelizing a loop
intervention.
Problems that arise with using Deadlocks and race
Threading Issues
threads. conditions
Allocating CPU time to Round-robin scheduling in a
CPU Scheduling
different tasks. multitasking OS
Managing the order of thread Scheduling threads in a web
Thread Scheduling
execution. server
 Concept Explanation Example
Multiple-Processor Allocating tasks across Load balancing in a multi-
Scheduling multiple CPUs. CPU system
Real-Time CPU Scheduling for tasks that need
Flight control systems
Scheduling precise timing.
Deadlock Understanding situations Two programs waiting on
Characterization where tasks can't proceed. each other indefinitely
Methods to manage and Killing one process to
Handling Deadlocks
resolve deadlocks. resolve a deadlock
Ensuring a program never
Techniques to avoid
Deadlock Prevention holds onto resources
deadlocks from occurring.
indefinitely
Dynamically checking if
Deadlock Avoidance granting a resource will cause Banker's algorithm
a deadlock.
Running a detection
Identifying when a deadlock
Deadlock Detection algorithm when a process
has occurred.
gets stuck
Recovery from Steps to recover from a Restarting one of the stuck
Deadlock deadlock situation. programs
Assigning one continuous
Contiguous Memory Early operating systems like
block of memory to a
Allocation MS-DOS
program.
Moving processes between Loading parts of a program
Swapping
main memory and disk. as needed
Dividing memory into fixed- Modern OS memory
Paging
size pages. management
Dividing memory into Different segments for code,
Segmentation
variable-sized segments. data, and stack
Loading pages into memory
Demand Paging Virtual memory systems
only when needed.
Replacing old pages in LRU (Least Recently Used)
Page Replacement
memory with new ones. algorithm
Assigning physical memory Assigning memory to
Allocation of Frames
to virtual pages. different running programs
Excessive paging causing Constant swapping making
Thrashing
slowdowns. the system unresponsive
 Concept Explanation Example
Memory-Mapped Mapping disk files into Accessing files as if they
Files memory for faster access. were part of RAM
Mass-Storage Organization of large data Hard drive partitions and file
Structure storage. systems
Managing the order of disk Optimizing access times by
Disk Scheduling
read/write requests. reordering requests
Using multiple disks for RAID 5 for improved data
RAID Structure
redundancy and performance. reliability
Ways to access and retrieve Sequential and random
Access Methods
stored data. access
Directory and Disk Organization of files and
Hierarchical folder structure
Structure folders on disk.
File-System Making a file system
Mounting a USB drive
Mounting accessible to the OS.
Allowing multiple users or
File Sharing Network file sharing
programs to access files.
File-System Internal organization of a file
NTFS, FAT32
Structure system.
Directory Methods for organizing and Linked lists or B-trees for
Implementation storing directory entries. directories
Techniques for managing file Contiguous, linked, and
Allocation Methods
storage space. indexed allocation
Free-Space
Tracking unused disk space. Bitmap or free list
Management
Efficiency and Optimizing file system Caching frequently accessed
Performance operations. data
Backups and journaling file
Recovery Restoring data after failures.
systems
Devices that facilitate input
I/O Hardware Keyboards, mice, printers
and output.
Application I/O How programs interact with Using an API to read from a
Interface I/O devices. file
Kernel I/O Part of the OS managing I/O Handling device drivers and
Subsystem operations. I/O scheduling
 Concept Explanation Example
Converting high-level I/O
Transforming I/O Reading a file involves
requests to hardware
Requests multiple hardware steps
operations.
Ensuring only authorized
Protection User permissions
access to resources.
Table defining access rights User A can read file X, User
Access Matrix
for users and resources. B can write to file Y
Mechanisms to enforce access
Access Control Passwords and user roles
policies.
Revocation of Removing access Revoking a user's access to a
Access Rights permissions. shared folder
Security risks from malicious
Program Threats Viruses and worms
software.
System and Network Security risks to systems and
DDoS attacks and hacking
Threats networks.
Encrypting messages for
Cryptography Techniques for securing data.
privacy
Verifying the identity of
User Authentication Passwords, biometrics
users.
Measures to protect against
Security Defenses Firewalls, antivirus software
threats.
Emulating multiple OS
Running Windows on a Mac
Virtual Machines environments on one physical
using VMware
machine.
Creating virtual versions of Virtual servers in cloud
Virtualization
hardware or software. computing
Linux Design Core ideas behind Linux OS
Modular design, open source
Principles structure and function.
Loadable pieces of the OS Device drivers that can be
Kernel Modules
kernel. added or removed
Linux Process How Linux handles running
Using ps to view processes
Management programs.
Allocating CPU time in Completely Fair Scheduler
Linux Scheduling
Linux. (CFS)
 Concept Explanation Example
Linux Memory How Linux manages RAM vmstat for monitoring
Management and virtual memory. memory usage
Linux's method for storing
Linux File Systems Ext4, Btrfs
and organizing files.
How Linux handles dd command for copying
Linux I/O
input/output operations. data
Linux Interprocess Methods for Linux processes
Pipes, message queues
Communication to communicate.
Linux Network How Linux manages network
TCP/IP stack implementation
Structure connections.
Windows Design Core ideas behind Windows User-friendly interface,
Principles OS structure and function. backward compatibility
Windows System Main parts of the Windows Kernel, user interface, file
Components OS. system
Providing remote access to Remote Desktop Protocol
Terminal Services
Windows desktops. (RDP)
Quickly switching between Switching users without
Fast User Switching
user accounts. logging off
Windows File Windows' method for storing
NTFS
System and organizing files.
Windows How Windows handles
Network and Sharing Center
Networking network connections.
Network-based OS Operating systems designed
Network File System (NFS)
Types for network use.
The layout and organization
Network Structure Client-server, peer-to-peer
of a network.
Communication Rules for data exchange over
TCP/IP, HTTP
Protocols a network.
Ensuring network reliability Redundant servers and
Network Robustness
and fault tolerance. failover mechanisms
Managing files across
Distributed File
multiple networked Google File System (GFS)
Systems
computers.
 Unit – 6 : Software Engineering

Topic Description Example

Methods used to plan, manage, and
Software Process Waterfall, Agile,
control the development of
Models Scrum
software projects.
Basic framework for managing
Generic Process Plan, Design,
software development processes,
Model Implement, Test
including activities and tasks.
Fixed models that define specific
Prescriptive Process
stages and steps in software Waterfall model
Models
development.
Planning and controlling project
Gantt charts, resource
Project Management resources and schedules to achieve
allocation
project goals.
Component Based Building software by combining Using libraries or
Development pre-built components or modules. plugins
Technique to modularize cross-
Aspect-Oriented Adding logging to
cutting concerns like logging or
Software Development different modules
security.
Mathematical techniques to ensure Proving a program is
Formal Methods
software correctness. free of bugs
Flexible methods for iterative and Scrum, Extreme
Agile Process Models
incremental software development. Programming (XP)
Agile methodology emphasizing
Extreme Daily stand-ups, pair
frequent releases and customer
Programming (XP) programming
feedback.
Rapid changes in
Adaptive Software Agile approach focused on
features based on
Development adapting to changing requirements.
feedback
Agile framework that organizes
Scrum work into time-boxed iterations 2-week sprint cycles
called sprints.
Agile approach focusing on rapid
Dynamic System Phased delivery of
development and iterative
Development Model system components
delivery.
 Topic Description Example
Agile method focusing on
Feature Driven Feature-based
designing and building features
Development milestones
incrementally.
Family of agile methodologies
Crystal Clear for
Crystal tailored to different team sizes and
small teams
project criticality.
Applying software engineering
Developing e-
Web Engineering principles to web application
commerce platforms
development.
“The system must
Functional Specifications describing what the
allow users to log
Requirements software should do.
in.”
“The system must
Non-Functional Specifications describing how the
load in under 2
Requirements software performs tasks.
seconds.”
Eliciting Process of gathering information Interviews, surveys
Requirements about what the software should do. with stakeholders
Creating scenarios that describe “User logs in to
Developing Use Cases
how users interact with the system. check their account.”
Examining and structuring
Requirement Analysis Creating diagrams
requirements to ensure they are
and Modelling and models
well-defined.
Checking requirements for Peer reviews and
Requirements Review
completeness and correctness. inspections
Software
A document
Requirements Document detailing all functional
specifying system
Specification (SRS) and non-functional requirements.
capabilities
Document
Hiding database
Simplifying complex systems by
Abstraction complexity with an
focusing on high-level functions.
API
High-level structure of the System architecture
Architecture
software system. diagrams
Reusable solutions for common Singleton pattern for
Patterns
design problems. unique instances
 Topic Description Example
Dividing a system into distinct Separating data
Separation of
sections to handle different aspects handling from UI
Concerns
of functionality. logic
Designing a system in discrete
Modular code
Modularity modules that can be developed and
libraries
updated independently.
Encapsulation of data to prevent
Private variables in a
Information Hiding external access to implementation
class
details.
Designing modules to be
Functional Separate functions
independent and have minimal
Independence for different tasks
impact on each other.
Cohesion and Measures of how closely related High cohesion, low
Coupling and dependent modules are. coupling
Object-Oriented Designing software by modeling Designing classes for
Design real-world entities as objects. users and orders
Defining data structures to support Creating database
Data Design
software functionality. schemas
Structuring a system into
Defining software
Architectural Design components and defining their
layers
interactions.
Designing the layout and
Designing forms and
User Interface Design interaction elements of the
buttons
software.
Component Level Designing individual software Detailed design of a
Design components in detail. module or class
Criteria for assessing software Ensuring software is
McCall’s Quality
quality including reliability, bug-free and user-
Factors
maintainability, and usability. friendly
ISO 9126 Quality Standard for measuring software Functionality,
Factors quality across various dimensions. efficiency, reliability
Process of identifying and fixing Code reviews and
Quality Control
defects in software. testing
Ensuring that software meets Following best
Quality Assurance quality standards throughout practices and
development. standards
 Topic Description Example
Identifying, analyzing, and
Creating risk
Risk Management mitigating potential risks in a
mitigation plans
project.
Strategies to reduce the impact of Backup systems and
Risk Mitigation
identified risks. redundancy
Monitoring and Ongoing process of tracking and
Risk status updates
Management controlling risks throughout the
and reviews
(RMMM) project lifecycle.
Probability that software will
Ensuring minimal
Software Reliability perform without failure over a
downtime
specific period.
Estimating the size of the software Lines of code (LOC)
Software Sizing to help in planning and cost or function points
estimation. (FP)
Techniques for estimating software
LOC and FP based Using LOC or FP to
effort and cost based on lines of
Estimations estimate project cost
code or function points.
Estimating Cost and Calculating the resources and time Using past data for
Effort needed for software development. cost prediction
Models used to estimate software
Estimation Models COCOMO model
project size, cost, and effort.
Model for estimating the cost and
Constructive Cost Using COCOMO to
effort required for a software
Model (COCOMO) predict project costs
project.
Planning the timeline and Creating project
Project Scheduling
assigning resources for a software timelines and
and Staffing
project. assigning roles
Visual representation of the project
Time-line Charts Gantt charts
schedule and milestones.
Ensuring that the software meets
Verification and Testing to confirm
requirements and performs as
Validation functionality
expected.
Distinctions between mistakes in
Error, Fault, Bug, and code (error), defects (fault), Debugging to find
Failure problems (bug), and system issues and fix bugs
(failure).
 Topic Description Example
Testing individual components
Unit and Integration Testing functions and
(unit) and their interactions
Testing their integration
(integration).
Testing based on internal logic Unit tests (white-
White-box and Black-
(white-box) or external box), functional tests
box Testing
requirements (black-box). (black-box)
Testing the software using the
Testing typical
Basis Path Testing most common paths through the
execution paths
code.
Control Structure Testing software based on its Testing loops and
Testing control flow structures. conditionals
Creating specific scenarios to test Writing tests based
Deriving Test Cases
different parts of the software. on requirements
Testing phases where alpha is Internal testing
Alpha and Beta
internal and beta is external to find (alpha), user testing
Testing
issues before release. (beta)
Testing to ensure new changes Running existing
Regression Testing
haven’t introduced new bugs. tests after updates
Assessing how well the software Load testing for high
Performance Testing
performs under various conditions. traffic
Testing the software’s behavior Simulating high load
Stress Testing
under extreme conditions. to test stability
Managing changes and keeping
Change Control and Using Git for version
track of different versions of
Version Control control
software.
Using existing software
Reusing libraries or
Software Reuse components or systems in new
modules
projects.
Modifying existing software to
Software Re-
improve it or adapt to new Refactoring old code
engineering
environments.
Decompiling
Analyzing software to understand
Reverse Engineering software to study its
its components and design.
design
 Unit – 7 : Data Structures and Algorithms

Topic Explanation Example

A collection of elements identified by
Arrays [1, 2, 3, 4, 5]
index or key.
Storing non-zero
A matrix mostly filled with zeros,
Sparse Matrix elements of a large
storing only non-zero elements.
matrix.
A collection where the last element
Undo operations in
Stacks added is the first to be removed
software.
(LIFO).
A collection where the first element
Line at a ticket
Queues added is the first to be removed
counter.
(FIFO).
A queue where each element has a
Priority Queues priority; higher priority elements are Task scheduling.
removed first.
A series of elements where each A chain of nodes in a
Linked Lists
element points to the next one. list.
A hierarchical structure with nodes
Trees Family tree.
connected by edges.
Multiple hierarchical
Forest A collection of disjoint trees.
organizations.
A tree where each node has at most
Binary Tree Binary tree structure.
two children.
A binary tree where null pointers are
Threaded Binary Traversal
used to point to the in-order
Tree improvement.
predecessor or successor.
A binary tree where each node's left
Binary Search
child is less, and the right child is Searching numbers.
Tree
greater than the node.
A self-balancing binary search tree
Self-adjusting search
AVL Tree where the difference in heights of
tree.
subtrees is at most one.
A self-balancing tree data structure
B Tree Database indexing.
that maintains sorted data and allows
 Topic Explanation Example
searches, sequential access, insertions,
and deletions.
A type of B tree where all values are
File systems
B+ Tree found in leaf nodes, and internal nodes
indexing.
only store keys.
An improved version of B+ tree with Database indexing
B Tree*
better space utilization. with less space.
Data Structure for Structures like hash sets or trees that Set operations
Sets manage a collection of unique items. (union, intersection).
A collection of nodes (vertices) Social network
Graphs
connected by edges. connections.
Methods to arrange data in a particular Bubble sort,
Sorting Algorithms
order. quicksort.
Searching Methods to find specific data within a Binary search in a
Algorithms collection. sorted array.
A method to map data to a fixed-size Hash tables for fast
Hashing
value for quick access. data retrieval.
Measures of the efficiency of
Time and Space O(n) time
algorithms in terms of time and
Complexities complexity.
memory usage.
Mathematical notation to describe the
Asymptotic O(n log n) for merge
growth rate of an algorithm's time or
Notation sort.
space complexity.
T(n) = T(n/2) + O(n)
Recurrence Equations that define sequences with
for divide and
Relations recursive terms.
conquer.
An algorithm design paradigm that
Divide and
solves a problem by breaking it into Merge sort.
Conquer
smaller subproblems.
A method for solving complex
Dynamic problems by breaking them down into Fibonacci sequence
Programming simpler subproblems and storing calculation.
results.
An approach that makes the locally Kruskal’s algorithm
Greedy Algorithms
optimal choice at each step. for MST.
 Topic Explanation Example
An approach for solving problems
Solving Sudoku
Backtracking incrementally, one step at a time, and
puzzles.
removing those that fail.
A method for solving optimization
Traveling Salesman
Branch and Bound problems by dividing the problem into
Problem.
subproblems and bounding solutions.
Diagrams that represent possible
Decision trees in
Comparison Trees comparisons made by sorting
sorting.
algorithms.
Lower Bounds Methods to establish the minimum
Proving sorting
through time complexity for problems by
requires O(n log n).
Reductions reducing them to known problems.
An algorithm for traversing or
Breadth-First Finding shortest path
searching tree or graph data structures
Search in unweighted graph.
level by level.
An algorithm for traversing or
searching tree or graph data structures Exploring all paths
Depth-First Search
by going as deep as possible before in a maze.
backtracking.
Algorithms to find the shortest path
Shortest Paths Dijkstra’s algorithm.
between nodes in a graph.
Algorithms to find the maximum flow
Ford-Fulkerson
Maximum Flow from a source to a sink in a flow
algorithm.
network.
Minimum Algorithms to find the smallest tree Prim’s or Kruskal’s
Spanning Trees connecting all nodes in a graph. algorithms.
Classification of problems based on
P and NP Class Traveling Salesman
their solvability and verification in
Problems Problem.
polynomial time.
Concepts for determining problem
NP-completeness Reducing one
difficulty and transforming problems
and Reducibility problem to another.
to show their complexity.
Number Theoretic Algorithms related to properties and Finding prime
Algorithms operations on numbers. numbers.
Polynomial Operations on polynomials, like Polynomial
Arithmetic addition and multiplication. multiplication.
 Topic Explanation Example
Fast Fourier An algorithm to compute the Discrete
Signal processing.
Transform Fourier Transform efficiently.
String Matching Algorithms to find patterns or Knuth-Morris-Pratt
Algorithms substrings within a string. algorithm.
Parallel Algorithms that perform multiple Parallel sorting
Algorithms operations simultaneously. algorithms.
Approximate
Approximation Algorithms that find approximate
solutions for NP-
Algorithms solutions to optimization problems.
hard problems.
Algorithms that use randomness to
Randomized Randomized
make decisions or improve
Algorithms quicksort.
performance.
 Unit – 8 : Theory of Computation and Compilers
Concept Description Example
A set of strings made from
Formal Language symbols according to Binary numbers (0s and 1s)
specific rules.
Non-Computational Problems that cannot be Deciding if a mathematical
Problems solved by any algorithm. proof is correct.
A method to show that
Cantor's proof that real
Diagonal Argument some infinities are larger
numbers are uncountable.
than others.
A paradox in set theory
The set of all sets that do
Russell’s Paradox showing some sets can't
not contain themselves.
exist.
A machine with a single
Deterministic Finite A vending machine with
state transition for each
Automaton (DFA) one way to process coins.
input.
Non-Deterministic A machine with multiple
A maze with multiple paths
Finite Automaton possible state transitions for
to the exit.
(NDFA) an input.
Both DFA and NDFA Both can recognize the
Equivalence of DFA
recognize the same set of pattern of even numbers of
and NDFA
languages. 1s.
Languages that can be Strings with any number of
Regular Languages expressed with regular a's followed by any number
expressions. of b's.
Rules for generating regular
Regular Grammars S → aS
languages.
a*b* matches any number
Patterns used to match
Regular Expressions of 'a's followed by any
strings in regular languages.
number of 'b's.
Used to show that a
A tool to prove a language
Pumping Lemma language like a^n b^n is
is not regular.
not regular.
Languages that cannot be
Non-Regular
expressed with regular Balanced parentheses.
Languages
expressions.
 Concept Description Example
The process of converting a Converting int x = 10; into
Lexical Analysis sequence of characters into keywords, identifiers, and
tokens. numbers.
Pushdown Automaton A machine with a stack for
Parsing nested parentheses.
(PDA) handling nested structures.
Non-Deterministic A PDA with multiple
Handling multiple ways to
Pushdown Automaton possible actions for a given
parse nested structures.
(NPDA) input.
Rules for generating
Context Free Grammar S → aSb
context-free languages.
Chomsky Normal A way to simplify context- Rules are either A → BC
Form free grammars. or A → a.
Another way to simplify Rules are A → aα, where α
Greibach Normal Form
context-free grammars. is a string of non-terminals.
A grammar that can
Arithmetic expressions
Ambiguity generate the same string in
with multiple valid parses.
different ways.
A tree showing how a string For aabb, showing its
Parse Tree
is derived from a grammar. derivation using `S → aSb
Equivalence of PDA Both can handle nested
Both can describe the same
and Context Free structures like balanced
languages.
Grammars parentheses.
A theoretical machine that A machine that can add
Turing Machine (TM) can simulate any computer two numbers by simulating
algorithm. human steps.
A computer running
Universal Turing A TM that can simulate any
different software
Machines other TM.
programs.
Models of Computation Different models for
TMs, lambda calculus, and
and Church-Turing computing, all equivalent in
recursive functions.
Thesis power.
Recursive languages are Recursive: Palindromes;
Recursive and
always decidable; Recursively enumerable:
Recursively-
recursively enumerable may Halting problem
Enumerable Languages
not be. languages.
 Concept Description Example
Languages that require
Context-Sensitive Syntax of natural
context for their grammar
Languages languages.
rules.
A grammar that can
Grammars with no
Unrestricted generate complex
restrictions on their
Grammars languages like {a^n b^n
production rules.
c^n}.
Regular < Context-Free <
Chomsky Hierarchy of Classification of languages
Context-Sensitive <
Languages by their generative power.
Recursively Enumerable.
Construction of TM for Building a TM to solve A TM that checks if a
Simple Problems basic problems. string is a palindrome.
Problems with no
Unsolvable Problems The Halting Problem.
algorithmic solution.
The problem of determining
Deciding if a given
Halting Problem if a program will stop or run
program will halt.
forever.
Post Correspondence A problem about matching Matching sequences from
Problem strings using pairs of tiles. two lists of strings.
Unsolvable Problems Problems that can't be
Deciding equivalence of
for Context-Free solved even with context-
context-free grammars.
Languages free languages.
Analyzing how
Measuring and Classifying algorithms as
computational resources
Classifying Complexity O(n), O(n^2), etc.
grow with input size.
Tractable: Sorting;
Tractable and Problems that can or cannot
Intractable: Traveling
Intractable Problems be solved efficiently.
Salesman Problem.
The grouping of operations
Associativity (a + b) + c = a + (b + c)
doesn't affect the result.
The order in which Multiplication before
Precedence
operations are performed. addition in expressions.
Grammar Changing grammars to Converting a grammar to
Transformations simplify parsing. Chomsky Normal Form.
Parsing from the start
Top-Down Parsing Recursive descent parsing.
symbol to the input.
 Concept Description Example
Recursive Descent A top-down parsing method Parsing expressions with a
Predictive Parsing using recursive procedures. recursive function.
A top-down parsing
Parsing simple expressions
LL(1) Parsing technique using one
like a(bc)*.
lookahead symbol.
Parsing from the input to
Bottom-Up Parsing Shift-reduce parsing.
the start symbol.
A bottom-up parser using
Parsing complex
LR Parser lookahead to resolve
expressions with a stack.
ambiguities.
A variant of LR parsing that Parsing programming
LALR(1) Parser
is more efficient. languages efficiently.
A grammar with attributes Adding type-checking
Attribute Grammar
for semantic rules. rules to a grammar.
Syntax Directed Rules that attach meanings Associating expressions
Definitions to grammar rules. with values.
Inherited: Propagate type
Attributes that pass
Inherited and information; Synthesized:
information up or down the
Synthesized Attributes Compute expression
parse tree.
values.
A graph showing
Graph for computing
Dependency Graph dependencies between
attribute values in order.
attributes.
Ensuring attributes are
The order in which
Evaluation Order computed before they are
attributes are computed.
used.
S-attributed: Synthesized
S-attributed and L- Definitions for handling
only; L-attributed: Both
attributed Definitions attributes in parse trees.
inherited and synthesized.
Verifying types in Checking if int + float is
Type-Checking
expressions and statements. valid.
How memory is structured Allocation of variables and
Storage Organization
for program variables. arrays in memory.
A tree representing function Visualizing function calls
Activation Tree
calls and returns. in a program.
 Concept Description Example
Data structure holding Records for local variables
Activation Record
function call information. and return addresses.
Stack Allocation of Using a stack to manage Stack frames for function
Activation Records function calls and returns. calls.
Parameter Passing Methods for passing data to Passing by value,
Mechanisms functions. reference, or pointer.
A table that holds
Tracking variable names
Symbol Table information about variables
and types.
and functions.
Intermediate Abstract code forms used in Intermediate code between
Representations compiling. source and machine code.
Translation of Converting variable Generating code to allocate
Declarations declarations into code. memory for variables.
Translating variable x = 5 becomes code to
Assignments
assignments into code. store 5 in x.
The sequence in which Handling loops and
Control Flow
statements are executed. conditionals.
Translating logical
Boolean Expressions Translating if (a && b) and
expressions and function
and Procedure Calls call func().
calls.
Creating machine code from
Generating assembly code
Code Generation intermediate
from high-level code.
representations.
Managing the execution Handling jumps and
Control-flow
path in code. branches in machine code.
Analyzing how data moves Tracking variable values
Data-flow Analysis
through a program. across different statements.
Improving code within a Simplifying calculations
Local Optimization
single function. within a loop.
Improving code across Reducing redundant
Global Optimization functions or the entire calculations across
program. functions.
Enhancing loops to run Unrolling loops to reduce
Loop Optimization
more efficiently. overhead.
 Concept Description Example
Replacing multiple
Peep-Hole Making small optimizations
instructions with a single
Optimization in short code sequences.
one.
Ordering instructions to Reordering code to avoid
Instruction Scheduling
improve performance. pipeline stalls.

.
 Unit – 9 : Data Communication and Computer Networks

Topic Explanation Example

The process of
Data exchanging Sending an email from one computer to
Communication information another.
between devices.
Components of Hardware and
a Data software needed
Modem, router, and network cables.
Communication for
System communication.
Types of
communication
channels: Simplex
Simplex, Half- (one-way), Half-
Simplex: Radio broadcasting; Duplex:
Duplex, Duplex Duplex (two-way
Phone call.
Modes but not at the same
time), Duplex
(two-way
simultaneously).
Analog signals
Analog and vary continuously, Analog: Traditional radio; Digital: Digital
Digital Signals digital signals are radio.
discrete.
Channels with no
interference vs.
Noiseless and Noiseless: Fiber optics; Noisy: Traditional
those with
Noisy Channels telephone lines.
interference
affecting signals.
Bandwidth is the
capacity of a
channel;
Bandwidth,
Throughput is Bandwidth: 100 Mbps; Throughput: 95
Throughput,
actual data Mbps; Latency: 10 ms.
and Latency
transferred;
Latency is the
delay.
 Topic Explanation Example
Sending
Digital and
information as Digital: Sending an email; Analog: Analog
Analog
digital or analog TV broadcast.
Transmission
signals.
Data Encoding Methods to
Encoding: ASCII for text; Modulation: AM
and Modulation represent and
radio transmission.
Techniques transmit data.
Broadband uses
Broadband and
multiple signals; Broadband: Cable internet; Baseband:
Baseband
Baseband uses one Ethernet.
Transmission
signal.
Combining
Multiplexing multiple signals TV cable carrying multiple channels.
into one channel.
The physical
Transmission medium through
Fiber optic cables, Wi-Fi signals.
Media which data is
transmitted.
Transmission Mistakes in data
Corrupted files during download.
Errors transmission.
Techniques to
Error Handling
detect and correct Error-checking codes, retransmission.
Mechanisms
errors.
The layout of
Network Star topology: Central hub connecting
network
Topologies devices.
connections.
Networks
Local Area
covering a small
Networks Office network.
area like a
(LANs)
building.
Metropolitan Networks
Area Networks covering a city or City-wide Wi-Fi network.
(MANs) large campus.
Wide Area Networks
Networks covering large Internet, corporate VPNs.
(WANs) geographic areas,
 Topic Explanation Example
often connecting
multiple LANs.
Networks that use
Wireless
radio signals Wi-Fi network in a coffee shop.
Networks
instead of cables.
A global network
connecting
millions of
private, public,
Internet World Wide Web (WWW).
academic,
business, and
government
networks.
Frameworks to
understand and
Network Models OSI model, TCP/IP suite.
design network
communications.
Divides network
communication
Layered OSI model layers: Physical, Data Link,
into layers for
Architecture Network, etc.
easier
management.
A model with
Layers: Physical, Data Link, Network,
OSI Reference seven layers that
Transport, Session, Presentation,
Model describe network
Application.
communication.
Set of protocols
TCP/IP used for internet TCP for reliable communication, IP for
Protocol Suite and network addressing.
communication.
Types of
Physical, addresses used to
Logical, Port, identify devices
IP address, MAC address, Port number.
and Specific and
Addresses communication
channels.
 Topic Explanation Example
Methods used to
Switching
route data through Circuit switching, Packet switching.
Techniques
a network.
Wrapping data
Framing into packets for Adding headers and trailers to data packets.
transmission.
Methods to find
Error Detection
and fix errors in Checksums, parity bits.
and Correction
transmitted data.
Techniques to
Flow and Error Flow control: Buffer management; Error
manage data flow
Control control: Retransmission.
and handle errors.
A method for
managing data
Sliding Window Sending multiple packets before waiting for
transmission
Protocol acknowledgment.
between sender
and receiver.
A protocol for
sending data over
HDLC High-level Data Link Control protocol.
networks with
error checking.
Methods for
multiple devices CSMA/CD for Ethernet, TDMA for mobile
Multiple Access
to access a networks.
network.
A protocol for
network devices to
CSMA/CD Ethernet networks.
avoid collisions on
a shared channel.
A protocol to
prevent collisions
CSMA/CA Wi-Fi networks.
in wireless
networks.
A method to
reserve bandwidth
Reservation Reserved channels in cellular networks.
for
communication.
 Topic Explanation Example
A method where a
central device
Polling Network printer checks for print jobs.
checks each
device for data.
A method where a
special token is
Token Passing passed around to Token Ring network.
control access to a
network.
Frequency
Division Multiple
Access, divides
FDMA FM radio stations.
the frequency
spectrum into
channels.
Code Division
Multiple Access,
CDMA uses unique codes Mobile phone networks.
to separate
signals.
Time Division
Multiple Access,
TDMA divides time into GSM mobile networks.
slots for
communication.
Hardware used to
Network connect and
Routers, switches, hubs.
Devices manage network
communication.
High-capacity
Backbone networks that
Internet backbone.
Networks connect various
smaller networks.
A network within
Virtual LANs
a network, Separate departments within a company.
(VLANs)
allowing logical
 Topic Explanation Example
separation of
devices.
Addressing
IPv4 Structure scheme for
and Address devices on a [Link] address.
Space network, with 32-
bit addresses.
Methods to
allocate IP
Classful and
addresses; classful
Classless Classful: A, B, C; Classless: CIDR.
uses fixed sizes,
Addressing
classless uses
variable sizes.
Datagram: Data
packet;
Datagram, Fragmentation:
Fragmentation, Breaking data into Fragmenting a large file for transmission.
and Checksum smaller parts;
Checksum: Error
detection.
New version of IP
with 128-bit
IPv6 Packet addresses,
[Link]
Format improving
addressing and
routing.
Mapping
ARP translates IP
Logical to
addresses to MAC Resolving [Link] to a MAC address.
Physical
addresses.
Address (ARP)
Direct: Same
Direct and
network; Indirect:
Indirect Direct: Local network; Indirect: Across the
Different
Network Layer internet.
networks, needs
Delivery
routing.
Routing Methods for
Dijkstra’s algorithm.
Algorithms determining the
 Topic Explanation Example
best path for data
to travel.
TCP: Reliable,
connection-
oriented; UDP:
TCP, UDP, and TCP: Web browsing; UDP: Streaming
Unreliable,
SCTP Protocols video; SCTP: VoIP.
connectionless;
SCTP: Reliable,
message-oriented.
Techniques to
Flow Control manage the rate of Buffering to prevent overflow.
data transmission.
Methods to detect
and correct errors
Error Control Retransmitting lost packets.
in data
transmission.
Techniques to
Congestion
avoid network TCP: Slow start; SCTP: Congestion
Control in TCP
congestion and window.
and SCTP
manage data flow.
Uniform Address used to
Resource locate resources [Link]
Locator (URL) on the web.
Translates domain
Domain Name
names to IP [Link] to [Link]
Service (DNS)
addresses.
System for
Electronic Mail SMTP for sending, POP/IMAP for
sending and
Architecture receiving.
receiving emails.
Protocols for
email: SMTP
SMTP, POP, SMTP: Sending email; POP/IMAP: Reading
(sending), POP
and IMAP email.
(retrieving), IMAP
(managing).
Protocols for
TELNET and
remote access and TELNET: Remote login; FTP: File transfer.
FTP
file transfer.
 Topic Explanation Example
Malicious
software designed
Malwares Viruses, worms.
to harm or exploit
systems.
Techniques for
Cryptography
securing and Cryptography: Encryption; Steganography:
and
hiding Hiding data in images.
Steganography
information.
Encryption using
Secret-Key the same key for
AES encryption.
Algorithms both encryption
and decryption.
Encryption using a
Public-Key
pair of keys: RSA encryption.
Algorithms
public and private.
A method to
Digital verify the
Signing a document digitally.
Signature authenticity of
digital messages.
Virtual Private Secure networks
Networks created over VPN for secure remote access.
(VPNs) public networks.
Security systems
that monitor and
Firewalls control incoming Blocking unauthorized access.
and outgoing
network traffic.
Cellular
GSM and technologies for GSM: SIM cards; CDMA: Verizon's
CDMA mobile network.
communication.
GSM provides
Services and
standard mobile
Architecture of Voice calls, SMS.
communication
GSM
services.
Middleware and Software that
Middleware connecting apps to servers.
Gateway for enables
 Topic Explanation Example
Mobile communication
Computing between different
systems.
Protocols enabling
Mobile IP and
mobile devices to
Mobile
maintain Handoff between cell towers.
Communication
connections while
Protocol
moving.
Satellites used for
transmitting data,
Communication
television, and GPS satellites.
Satellites
communication
signals.
Networks using
Wireless
wireless
Networks and Wi-Fi networks, Mesh topology.
communication,
Topologies
and their layout.
Network design
Cellular for mobile
Cellular phone networks.
Topology communication in
cells.
Networks formed
Mobile Adhoc by mobile devices
Temporary networks at a conference.
Networks without fixed
infrastructure.
Technologies for
Wireless
transmitting data
Transmission
without wires, and Bluetooth, Wi-Fi.
and Wireless
local wireless
LANs
networks.
Systems used to
Wireless
determine the
Geolocation GPS tracking apps.
location of
Systems
wireless devices.
Technologies for
GPRS for mobile internet; SMS for text
GPRS and SMS mobile data and
messages.
messaging.
 Topic Explanation Example
Cloud computing
service models:
Software as a
SaaS, PaaS, SaaS: Google Docs; PaaS: Heroku; IaaS:
Service, Platform
IaaS AWS EC2.
as a Service,
Infrastructure as a
Service.
Cloud services
that are either
Public and Public: AWS; Private: Corporate data
available to the
Private Cloud center.
public or restricted
to private use.
Creating virtual
versions of
Virtualization Virtual machines on a server.
resources like
servers or storage.
A server that is
created and
Virtual Server operated virtually Cloud-based web hosting.
rather than as a
physical server.
Storing data on
remote servers
Cloud Storage Google Drive, Dropbox.
accessible over the
internet.
Storage systems
Database for managing and
MySQL, Oracle.
Storage accessing
databases.
Managing
resources like
Resource
computing power Allocating server resources.
Management
and storage in a
network.
Service Level A contract that
Agreement defines the Guaranteeing 99.9% uptime.
(SLA) expected
 Topic Explanation Example
performance and
service levels.
Internet of Things:
Connecting
Basics of IoT Smart thermostats, wearable devices.
everyday devices
to the internet.
 Unit – 10 : Artificial Intelligence (AI)

Concept Explanation Example

A test to determine if a machine
Chatbots in customer
Turing Test can exhibit intelligent behavior
service.
indistinguishable from a human.
An entity that acts to achieve the
An autonomous car
Rational Agent best outcome based on its
optimizing its route.
knowledge and beliefs.
A way to model all possible states Solving a puzzle by
State Space
and actions in a problem to find a exploring all possible
Representation
solution. moves.
Heuristic Search Methods that use rules of thumb A GPS finding the
Techniques to find solutions faster. quickest route.
Using strategies and algorithms to Chess programs like
Game Playing
play games optimally. Stockfish.
An algorithm to decide the best A chess program
Min-Max Search move by minimizing the possible evaluating possible
maximum loss. moves.
An optimization of Min-Max Speeding up a chess
Alpha Beta Cutoff search to ignore branches that game AI by pruning less
won't affect the final decision. promising moves.
A way of representing knowledge Using "If-Then"
Logic using formal statements that can statements in a rule
be true or false. system.
Graphs representing knowledge
A map of family
Semantic Networks with nodes and links showing
relationships.
relationships.
Structures that represent A "car" frame with
Frames stereotypical situations in attributes like "color" and
knowledge bases. "model".
Statements that define how to
"If it rains, then take an
Rules derive conclusions from given
umbrella."
information.
Sequences of actions or events in A script for booking a
Scripts
a particular scenario. flight online.
 Concept Explanation Example
A diagram showing how
A representation of knowledge
Conceptual "buying" relates to
that shows how concepts are
Dependency "paying" and "receiving
related.
goods".
Structured frameworks that define
Medical terms organized
Ontologies relationships between concepts in
in a disease ontology.
a domain.
Computer programs that mimic
A medical diagnosis
Expert Systems the decision-making ability of a
system.
human expert.
Methods to manage situations Weather forecasting
Handling
where information is incomplete using probabilistic
Uncertainty
or uncertain. models.
The process of defining steps to Creating a schedule for a
Planning
achieve a goal. project.
Planning with a sequential order A simple daily routine
Linear Planning
of steps. plan.
Planning that allows multiple
Non-Linear Planning a wedding with
steps to occur simultaneously or
Planning parallel tasks.
out of sequence.
A method where goals are stacked
Goal Stack To-do lists with tasks that
and addressed in a last-in, first-out
Planning depend on each other.
manner.
Planning a vacation by
Hierarchical Breaking down tasks into smaller,
breaking it into booking
Planning manageable sub-tasks.
flights, hotels, etc.
A formalism for representing
Planning a robot's actions
STRIPS actions and goals in planning
to assemble furniture.
systems.
Partial Order Planning where the order of some Organizing a party
Planning actions is flexible. without strict task order.
The rules and structure for
Grammar and English grammar rules
constructing sentences in a
Language for sentence formation.
language.
 Concept Explanation Example
Methods for analyzing sentence Breaking down a
Parsing
structure to understand its sentence into parts of
Techniques
meaning. speech.
Understanding the meaning of Interpreting "She banked
Semantic Analysis sentences beyond just their the river" vs. "She went
grammatical structure. to the bank".
Understanding implied
Understanding language in
meaning, like "Can you
Pragmatics context and its use in
pass the salt?" in a dinner
communication.
setting.
Distinguishing between entities
that act autonomously (agents) A robot (agent) vs. a
Agents and Objects
and those that are just data database entry (object).
(objects).
A system where multiple agents
Online gaming with
Multiagent System interact and collaborate to achieve
multiple players.
goals.
An extension of the web where Linked data on the web
Semantic Web information is given well-defined connecting different
meaning. datasets.
Agent Methods used by agents to Chat systems in multi-
Communication exchange information. user environments.
Knowledge Using structured frameworks to Sharing medical research
Sharing using share and understand information data using standardized
Ontologies among different systems. terminology.
Mathematical sets where elements A "tall" person could be
Fuzzy Sets have degrees of membership 70% tall for a given
rather than being just in or out. definition.
Functions that define how each
A function determining
Membership point in a space is mapped to a
how "warm" a
Functions value between 0 and 1,
temperature is.
representing membership degree.
Converting exact
Processes of converting crisp
Fuzzification and temperature readings to
inputs to fuzzy values and vice
Defuzzification fuzzy terms like "hot" or
versa.
"cold".
 Concept Explanation Example
Relationships where degrees of
Degree of "similarity"
Fuzzy Relations connection between elements are
between two objects.
represented.
Deciding on air
Rules that use fuzzy logic to make
Fuzzy Rules and conditioning settings
decisions based on fuzzy input
Fuzzy Inference based on fuzzy
values.
temperature input.
Adjusting the
A control system using fuzzy
Fuzzy Control temperature in a room
logic to handle uncertain or
System based on fuzzy input
imprecise information.
from various sensors.
Genetic Algorithms Optimization techniques inspired Evolving designs for
(GA) by natural evolution. better performance.
Encoding Methods to represent solutions or Binary or decimal
Strategies individuals in a genetic algorithm. encoding of solutions.
Processes like crossover and Mixing parts of two
Genetic Operators mutation used to evolve solutions solutions to create a new
in GA. one.
Measures used to evaluate how
Scoring a design based
Fitness Functions well a solution meets the desired
on efficiency and cost.
criteria.
The iterative process of selection, Running multiple
GA Cycle crossover, mutation, and generations of evolution
evaluation in genetic algorithms. to improve solutions.
A type of machine learning where Training a spam filter
Supervised
the model is trained on labeled with examples of spam
Learning
data. and non-spam emails.
A type of machine learning where Grouping similar
Unsupervised
the model finds patterns in customers based on
Learning
unlabeled data. purchasing behavior.
Training a robot to
A type of machine learning where
Reinforcement navigate a maze by
an agent learns by receiving
Learning rewarding successful
rewards or penalties.
moves.
 Concept Explanation Example
A basic neural network with one
Simple image recognition
Single Perceptron layer of neurons used for binary
tasks.
classification.
A neural network with multiple
Multi Layer Advanced image and
layers that can model complex
Perceptron (MLP) speech recognition.
patterns.
Neural networks that organize
Self Organizing Clustering similar types
data into a lower-dimensional
Maps of data for visualization.
space.
A type of recurrent neural
Memorizing and recalling
Hopfield Network network used for pattern
patterns or images.
recognition.