Introduction to Computer Science
Comprehensive Lecture Notes
Department of Computer Engineering | Spring 2025
1. Fundamentals of Computing
1.1 What is a Computer?
A computer is an electronic device capable of receiving, storing, processing, and
outputting data. Modern computers follow the stored-program concept, where both
instructions and data reside in memory simultaneously.
• Hardware: Physical components including CPU, RAM, storage devices, and
I/O peripherals.
• Software: Programs and operating systems that instruct hardware on what
tasks to perform.
• Firmware: Low-level software embedded directly into hardware devices (e.g.,
BIOS/UEFI).
1.2 Number Systems
Computers operate on binary (base-2) arithmetic, but engineers often work with
hexadecimal (base-16) for compactness. Understanding number system conversions
is fundamental.
1. Binary (Base-2): Uses digits 0 and 1. Each position represents a power of 2.
Example: 1011₂ = 11₁₀
2. Octal (Base-8): Uses digits 0–7. Useful in file permission systems (e.g., Unix
chmod 755).
3. Hexadecimal (Base-16): Uses 0–9 and A–F. Commonly used in memory
addresses and color codes.
2. Data Representation
2.1 Encoding Text
Text is encoded using standardized character sets that map characters to numeric
values stored in binary.
• ASCII: American Standard Code for Information Interchange. 7-bit encoding,
covers 128 characters including English letters, digits, and control characters.
• Unicode (UTF-8/UTF-16): Universal encoding standard supporting over
143,000 characters from all writing systems worldwide.
• UTF-8: Variable-length encoding (1–4 bytes per character). Backward
compatible with ASCII. Most widely used on the web.
2.2 Representing Numbers
Integers and floating-point numbers are stored differently in computer memory,
following IEEE standards.
• Two's Complement: Standard method for representing signed integers.
Inverting all bits and adding 1 gives the negative equivalent.
• IEEE 754 Float: Floating-point standard using sign bit, exponent field, and
mantissa. Supports single (32-bit) and double (64-bit) precision.
◦ Single precision: 1 sign bit + 8 exponent bits + 23 mantissa bits
◦ Double precision: 1 sign bit + 11 exponent bits + 52 mantissa bits
3. Algorithms and Problem Solving
3.1 What is an Algorithm?
An algorithm is a finite, ordered sequence of well-defined instructions designed to
solve a specific problem or accomplish a task. Key properties include:
• Finiteness: Must terminate after a finite number of steps.
• Definiteness: Each step must be precisely and unambiguously defined.
• Effectiveness: Operations must be basic enough to be carried out exactly in
principle.
• Input/Output: Zero or more inputs; one or more outputs.
3.2 Complexity Analysis
Big-O notation describes how an algorithm’s time or space requirements grow
relative to input size. Understanding complexity helps choose efficient algorithms.
4. O(1) – Constant time: Execution time does not change with input size.
Example: array index access.
5. O(log n) – Logarithmic: Grows slowly as input increases. Example: binary
search on a sorted array.
6. O(n) – Linear: Grows proportionally to input. Example: iterating through all
elements once.
7. O(n log n) – Linearithmic: Common in efficient sorting algorithms like Merge
Sort and Heap Sort.
8. O(n²) – Quadratic: Nested iterations over input. Example: Bubble Sort,
Selection Sort.
3.3 Sorting Algorithms
Sorting is one of the most fundamental operations in computer science. Common
sorting algorithms differ significantly in performance:
• Bubble Sort: Repeatedly swaps adjacent elements if out of order. O(n²)
average. Simple but inefficient for large datasets.
• Merge Sort: Divide-and-conquer approach. Splits array recursively, sorts,
then merges. O(n log n) guaranteed. Stable sort.
• Quick Sort: Selects a pivot and partitions array. O(n log n) average, O(n²)
worst case. Very fast in practice due to cache efficiency.
• Heap Sort: Builds a max-heap, then extracts maximum elements. O(n log n)
guaranteed. In-place but not stable.
4. Programming Concepts
4.1 Variables and Data Types
Variables are named storage locations in memory. Data types define the kind of
value a variable can hold and the operations that can be performed on it.
• Primitive types: int, float, double, char, boolean – directly stored in memory.
• Reference types: Objects, arrays, strings – variable holds a reference
(memory address) to the actual data.
• Type casting: Converting one data type to another. Implicit (widening) vs
explicit (narrowing) casting.
4.2 Control Structures
Control structures direct the flow of execution in a program. The three fundamental
constructs are sequence, selection, and iteration.
9. Sequence: Statements execute one after another in the order they appear.
10. Selection (Conditionals): if/else, switch–case statements allow different
code paths based on conditions.
11. Iteration (Loops): for, while, do-while loops repeat a block of code until a
condition is met.
4.3 Functions and Scope
Functions (also called methods or procedures) are reusable blocks of code that
perform a specific task. They promote modularity and reduce code repetition.
• Parameters vs Arguments: Parameters are defined in the function
signature; arguments are the actual values passed when calling the function.
• Return values: Functions may return a computed result to the caller using
the return statement.
• Scope: Variables declared inside a function are local (not accessible outside).
Global variables are accessible throughout the program.
• Recursion: A function that calls itself. Requires a base case to prevent
infinite recursion. Useful for tree traversal, factorial, Fibonacci.
5. Data Structures
5.1 Arrays and Linked Lists
• Array: Contiguous memory block storing same-type elements. O(1) access
by index, O(n) for insertion/deletion in the middle.
• Singly Linked List: Each node stores data and a pointer to the next node.
O(1) insertion at head, O(n) search.
• Doubly Linked List: Each node has pointers to both next and previous
nodes. Enables efficient bidirectional traversal.
5.2 Stacks and Queues
• Stack (LIFO): Last In, First Out. push() adds to top, pop() removes from top.
Used in function call management, undo mechanisms.
• Queue (FIFO): First In, First Out. enqueue() adds to rear, dequeue() removes
from front. Used in task scheduling, BFS graph traversal.
• Priority Queue: Elements are dequeued in order of priority rather than
insertion order. Typically implemented using a heap.
5.3 Trees
A tree is a hierarchical data structure with a root node and subtrees of children.
Trees are widely used in databases, file systems, and compilers.
• Binary Tree: Each node has at most two children (left and right).
• Binary Search Tree (BST): Left child < parent < right child. O(log n) search in
balanced trees.
• AVL Tree: Self-balancing BST. Height difference between left and right
subtrees is at most 1. Guarantees O(log n) operations.
• Tree Traversals: In-order (left–root–right), Pre-order (root–left–right), Post-
order (left–right–root), Level-order (BFS).
6. Operating Systems Overview
6.1 Core Functions of an OS
An operating system manages hardware resources and provides services to
applications. Major functions include:
• Process Management: Scheduling CPU time among processes using
algorithms like Round Robin, FCFS, and Priority Scheduling.
• Memory Management: Virtual memory, paging, segmentation. Prevents
processes from accessing each other’s memory.
• File System Management: Organizes data on storage devices. Common file
systems: FAT32, NTFS, ext4, APFS.
• I/O Management: Coordinates communication between hardware devices
and software through device drivers.
6.2 Processes vs Threads
• Process: An independent program in execution with its own memory space.
Process isolation prevents crashes from propagating.
• Thread: A lightweight unit of execution within a process. Shares memory
space with sibling threads. Enables concurrency within an application.
• Deadlock: Occurs when two or more processes wait indefinitely for resources
held by each other. Prevented via resource ordering or timeout mechanisms.
7. Key Terminology Summary
The following terms are essential for any computer science student:
• Bit/Byte: Smallest unit of data (bit = 0 or 1). 8 bits = 1 byte.
• Compiler vs Interpreter: Compiler translates entire source code to machine
code at once; interpreter executes line by line.
• API: Application Programming Interface – a defined set of rules for how
software components interact.
• Cache: High-speed storage layer that stores frequently accessed data for
faster retrieval.
• Latency vs Throughput: Latency = time for one operation; throughput =
number of operations per unit time.
• Boolean Logic: AND, OR, NOT, XOR gates form the basis of all digital circuit
design.
• Abstraction: Hiding implementation details to reduce complexity.
Fundamental principle in all areas of computer science.
Study Notes — These notes cover the core curriculum for an introductory computer science course.
Review each section regularly and practice implementing the data structures and algorithms
described above.