Bachelor's

Notes: Computer Science & Information Systems

1. The Foundation: Mathematics for Computer Science

Computer Science is built upon a foundation of mathematical logic and principles. It provides the
tools for analyzing algorithms, modeling systems, and ensuring computational correctness. A
strong grasp of these concepts is non-negotiable for solving complex computational problems.

1.1. Discrete Mathematics

This branch deals with countable, distinct elements and is crucial for computer science, forming
the backbone of data structures and algorithm design.

• Boolean Algebra: The algebra of truth values (TRUE/1 and FALSE/0). It uses logical
operations like AND (conjunction, ∧), OR (disjunction, ∨), and NOT (negation, ¬).
o Application: Digital circuit design, database query optimization, and conditional
statements in programming.
o Truth Tables: A tabular representation of all possible input combinations and their
corresponding outputs.
o Problem Link: Constructing truth tables for complex logical expressions is a direct
application. For a given expression, you evaluate each sub-part step-by-step to
determine the final truth value. For example, for an expression like (X1∨X2)→¬X3, you
would compute X1∨X2, then ¬X3, and finally the implication → between the two.
o Implication Rule: A → B is only false when A is true and B is false. Otherwise, it is true.
• Graph Theory: A graph G is a structure consisting of a set of vertices (nodes, V) and a set of
edges (E) connecting them. Formally, G = (V, E).
o Types: Undirected, directed (digraphs), bipartite, complete.
o Concepts: Paths, distances, cycles.
o Algorithms:
▪ Breadth-First Search (BFS): Explores neighbors first. Used to find the shortest
path in unweighted graphs. Time complexity: O(V+E).
▪ Depth-First Search (DFS): Explores as far as possible along a branch before
backtracking. Used for topological sorting, cycle detection. Time
complexity: O(V+E).
 o Application: Social networks (nodes are people, edges are connections), web
crawling (nodes are webpages, edges are links), network routing.
• Combinatorics: The study of counting, arrangement, and combination. This is essential for
analyzing algorithm complexity and probabilities.
o Permutations: Arrangements of objects where order matters.
▪ Permutations of n distinct objects: P(n) = n! = n × (n-1) × ... × 2 × 1
▪ Permutations with repetition: If you have n objects with n1 identical of one
type, n2 of another, etc., the number of distinct permutations is n! / (n1! ×
n2! × ...).
o Combinations: Selections of objects where order does not matter.
▪ Combinations of k items from n: C(n,k) = n! / (k!(n-k)!) (also written
as nCk or (n choose k)).
o Variations with Repetition: The number of ways to create a sequence of
length k from n distinct objects, where repetition is allowed, is n^k.
o Problem Link: Problems often involve counting the number of possible passwords,
words with specific letter constraints, or code sequences. This requires summing
variations with repetition or using combinations to choose positions for specific
characters.
▪ Example (Counting Sequences): The number of different character
sequences of length 1 to 4 in a four-letter alphabet {A, C, G, T} is 4^1 + 4^2
+ 4^3 + 4^4 = 4 + 16 + 64 + 256 = 340. This is a sum of variations with
repetition.
▪ Example (Complex Constraints): Counting 5-letter words with exactly one 'A'
and exactly two 'B's involves:
1. Choose 1 position for 'A': C(5,1) = 5
2. Choose 2 positions for 'B' from the remaining 4: C(4,2) = 6
3. The remaining 2 positions can be filled with any of the other 2 allowed
letters (C, D, for example): 2^2 = 4
4. Total words: 5 × 6 × 4 = 120.

1.2. Probability and Statistics

Essential for understanding uncertainty, machine learning, and performance analysis.

• Basic Probability: The likelihood of an event occurring.

o Probability of an Event A: P(A) = (Number of Favorable Outcomes) / (Total
Number of Possible Outcomes), assuming all outcomes are equally likely.
o Complement Rule: P(not A) = 1 - P(A).
o Theorem of Total Probability: Used to calculate the probability of an event based
on prior knowledge of conditions related to the event.
o Problem Link: A direct application is calculating the probability of a simple event,
like the chance of a device being functional given a known failure rate. For example,
if 3 out of 100 flashlights are faulty, the probability of a faulty one is P(Faulty) =
3/100 = 0.03. Therefore, the probability of a working one is P(Working) = 1 -
P(Faulty) = 1 - 0.03 = 0.97.
• Descriptive Statistics: Summarizing and describing the main features of a dataset.
 o Mean (Average): μ = (Σx_i) / N for a population, x̄ = (Σx_i) / n for a sample.
o Application: A core part of Data Science, used to understand data before applying
machine learning models. Code fragments often calculate averages to make
decisions, such as finding students with above-average scores.

1.3. Calculus and Algebra

• Calculus (Derivatives & Integrals): Used in optimization algorithms, particularly in
machine learning for finding the minimum of a loss function (gradient descent). The
derivative f'(x) gives the slope of a function, indicating the direction of fastest increase.
• Linear Algebra (Vectors & Matrices): The language of data. Datasets are often
represented as matrices, and operations like matrix multiplication are fundamental to neural
networks and image processing.
• Problem Link: Finding the maximum or minimum value of a function or determining its
range are problems rooted in calculus. Solving systems of equations is a linear algebra task.
For instance, finding the maximum integer value of a function like y = -x² + 2 involves
finding the vertex, which is a calculus/analytical geometry concept.

2. Data Representation and Number Systems

Computers represent all information using binary digits (bits). Understanding these
representations is fundamental to everything from programming to networking.

2.1. Number Systems

A number in a base-b system is represented as a sequence of digits d_k d_{k-1} ... d_1 d_0 .
d_{-1} d_{-2} ..., where the value is calculated as:
Value = Σ (d_i × b^i) for i from -m to k.

• Decimal (Base 10): Uses digits 0-9.

• Binary (Base 2): Uses digits 0 and 1. The native language of computers.
• Octal (Base 8): Uses digits 0-7. A compact way to represent binary.
• Hexadecimal (Base 16): Uses digits 0-9 and A-F. Used for memory addresses and color
codes.
• Conversion Between Bases:
o To Decimal: Apply the formula directly.
▪ Example: 1011.01_2 = 1×2^3 + 0×2^2 + 1×2^1 + 1×2^0 + 0×2^{-1} + 1×2^{-
2} = 8 + 0 + 2 + 1 + 0 + 0.25 = 11.25_10.
▪ Problem Link: Involves converting large numbers from one base to another
to count zeros or ones in a different base representation. This tests the
understanding of positional notation.
o From Decimal (Integer Part): Repeatedly divide the number by the target base; the
remainders (in reverse order) form the new number.
 o From Decimal (Fractional Part): Repeatedly multiply the fractional part by the
target base. The integer parts of the results (in order) form the fractional part of the
new number.
o Binary ↔ Octal/Hex: Group binary digits into sets of 3 (for octal) or 4 (for hex) and
convert each group.
▪ Example: 11010110_2 → (011)(010)(110) → 3 2 6 → 326_8.
• Fractional Number Representation:
o Problem Link: Numbers like 0.1 in decimal have repeating representations in binary
(0.0001100110011..._2), which can lead to rounding errors in floating-point
arithmetic. Converting decimal numbers to binary and performing arithmetic requires
careful handling of these fractional parts. For example, adding A=25.2 and B=59.7 in
binary requires precise conversion and can highlight rounding issues.

2.2. Units of Information

• Bit: A single binary digit (0 or 1).
• Byte: 8 bits. The standard addressable unit of memory.
• Larger Units:
o 1 Kilobyte (KB) = 1024 Bytes = 2^10 Bytes
o 1 Megabyte (MB) = 1024 KB = 2^20 Bytes
o 1 Gigabyte (GB) = 1024 MB = 2^30 Bytes

• Problem Link: Direct conversion problems, such as converting a number of bits into
kilobytes or megabytes

o Formula: Bytes = Bits / 8, KB = Bytes / 1024.

o Example: 40960 bits / 8 = 5120 bytes. 5120 bytes / 1024 = 5 KB.

2.3. Encoding Information

• Character Encoding: Assigning binary codes to characters.
o Fixed-length vs. Variable-length codes: ASCII is fixed-length (7 or 8 bits); Huffman
coding is variable-length for compression.
o Prefix-free (Prefix) Codes: No code word is a prefix of another. This allows for
unambiguous decoding without needing special separators.
▪ Problem Link: Problems define a non-uniform, prefix-free code. A word is
given, allowing one to deduce the codes for individual letters, and then find
the code for another word. The key is to match the binary string to the known
codes progressively.
o Problem Link: Requires decoding a binary string using a given table of variable-
length codes. The algorithm is to read the string bit-by-bit, checking after each bit if
the current sequence matches a code in the table. If it does, output that character
and reset the sequence.
• Image Encoding:
o Bitmap: A grid of pixels, each with a color value. For black and white, 1 bit per pixel
is often sufficient (1=black, 0=white).
o
 o Problem Link: A black-and-white bitmap is encoded line-by-line. The resulting long
binary string is then converted to a more compact octal notation. This tests the
ability to visually parse a grid into a binary sequence and then perform base
conversion.

• Audio/Video Encoding & File Size Calculation:

o Core Formula:
File Size (bits) = (Width in pixels) × (Height in pixels) × (Color Depth in
bits per pixel) × (Frame Rate in fps) × (Time in seconds) × (Number of
Channels)
File Size (Bytes) = File Size (bits) / 8
File Size (MB) = File Size (Bytes) / (1024 × 1024)
o Problem Link: These problems provide parameters for two different recording
settings (e.g., mono vs. stereo, different resolutions) and ask to calculate the resulting
file size by applying the formula and comparing the relative changes in each
parameter.
▪ Example: Studio 1 (Mono) produces a 28 MB file. Studio 2 uses:
▪ Stereo (2 channels) → multiplier of 2
▪ Resolution 3.5 times higher → multiplier of 3.5
▪ Sampling Frequency 2 times lower → multiplier of 0.5
▪ Relative File Size: 28 MB × 2 × 3.5 × 0.5 = 98 MB.

3. Programming and Algorithms

This is the heart of computer science: the process of designing step-by-step procedures to solve
problems.

3.1. Programming Fundamentals

• Control Structures:
o Sequence: Executing statements one after another.
o Selection (Branching): Using if, else if, else statements to make decisions.
o Iteration (Loops): Using for and while loops to repeat actions.
• Data Structures:
o Lists/Arrays: Ordered collections, accessible by index. Time complexity: access O(1),
search O(n).
o Dictionaries/Associative Arrays: Unordered collections of key-value pairs. Time
complexity: access O(1) on average.
• Python-Specific Operations:
o Slice Operator: e.g., s[start:stop:step]. s[::2] extracts every second character
from a string s.
o The zip() function: Used to iterate over multiple lists in parallel. It creates an
iterator of tuples.
 • Problem Link: Code tracing problems provide a fragment of code and ask for the output.
This tests understanding of loops, conditionals, list/dictionary manipulation, and function
application. Identifying the correct slice operator is a direct test of syntax knowledge.
o Example Code Analysis: A loop calculates the total sum of scores from two lists
using zip. It then calculates the average. Another loop uses zip to iterate through
names and scores, populating a dictionary with students whose average is above the
class average. The output is the dictionary.

3.2. Algorithmic Paradigms

• Recursion: A function that calls itself. It must have a base case (a condition to stop) and a
recursive case (where it calls itself with a modified input).
o Problem Link: Problems involve calculating the value of a recursively defined
function F(n) or tracing all outputs of a recursive procedure. This tests the ability to
unwind the recursive calls until the base case is reached.
o Example (Recursive Function): Given F(n) = F(n-1) + F(n-3) and base cases,
calculating F(42999) requires understanding how to build the solution from the base
cases upwards (dynamic programming) due to the large input size.
o Example (Recursive Output): A procedure F(n) prints 2n+1 and, if n>1, prints 3n-
8 and then calls F(n-1) and F(n-4). To find the sum of all outputs for F(50), one must
trace the entire tree of recursive calls, summing all printed values. This often leads to
a exponential explosion of calls.
• K-Nearest Neighbors (KNN): A simple, instance-based machine learning algorithm used
for classification.
o How it works: For a new data point z, find the k closest points in the training data.
The class of z is determined by the majority class among these k neighbors. Ties are
often broken by considering the distance to the nearest neighbor of the tied classes.
o Distance Metric: Often Manhattan distance (L1: |x1-x2| + |y1-y2|) or Euclidean
distance (L2: √((x1-x2)² + (y1-y2)²)).
o Problem Link: A function implementing KNN is provided. Questions test
understanding of its mechanics: calculating distances, counting class votes, and
breaking ties based on the closest distance. The provided code typically uses
Manhattan distance and implements the tie-breaking logic.

3.3. Algorithm Analysis (Computational Complexity)

• Big O Notation: Describes the upper bound of the runtime or memory requirements of an
algorithm as the input size (n) grows. It describes the worst-case scenario.
o O(1): Constant time. Operation time is independent of input size.
o O(log n): Logarithmic time. Very efficient (e.g., binary search).
o O(n): Linear time. Time grows proportionally with n.
o O(n²): Quadratic time. Common with nested loops.
o O(2^n): Exponential time. Highly inefficient for large n (e.g., brute-force solutions to
some problems).
o O(n⁴): Polynomial time.
• Problem Link:
 o One type of problem states an algorithm's complexity (e.g., O(n⁴)) and asks how
much longer it will take if the input size is increased by a factor k. The answer
is k^4 times longer.
▪ Formula: Time_New / Time_Old = (k * n)^c / (n^c) = k^c, where c is the
exponent in the complexity class.
▪ Example: For O(n⁴) and k=3, the increase is 3^4 = 81 times.
o Another type asks to estimate the execution time for an algorithm with exponential
complexity O(2^n) for a given n. Since 2^n grows extremely fast, this illustrates the
intractability of exponential algorithms.
▪ Example: For n=10 and 1 second per operation, 2^10 = 1024 operations,
taking about 17 minutes. For n=50, 2^50 is over a quadrillion operations, which
would take millions of years.

4. Computer Systems & Architecture

This area covers the hardware and low-level software that execute programs.

4.1. Hardware Components

• Von Neumann Architecture: The fundamental design of most computers, with a Central
Processing Unit (CPU), Memory, and Input/Output devices, all connected by a bus.
• CPU: The brain of the computer. Key concepts:
oCISC vs. RISC: Complex (many, powerful instructions) vs. Reduced (fewer, simpler
instructions) Instruction Set Computers.
o Registers: Small, fast memory locations inside the CPU (e.g., Program Counter,
Accumulator).
o Parallelism: Techniques like pipelining (overlapping instruction stages) and
superscalar execution (multiple execution units) to perform multiple operations
simultaneously.
• Memory Hierarchy:
o Registers → Cache → RAM (Main Memory) → SSD/HDD (Secondary Storage)
o Volatile (RAM): Loses data when power is off.
o Non-Volatile (ROM, SSD, HDD): Retains data without power.
• Problem Link: Correctly identifying that RAM is internal, volatile memory and
is not considered an external storage device, unlike HDDs, SSDs, and flash drives.

4.2. Digital Logic

• Logic Gates: Physical devices that implement Boolean functions (AND, OR, NOT, XOR, etc.).
They are the building blocks of digital circuits.
• Truth Tables: A table showing the output of a logic circuit for every possible input
combination.
 • Problem Link: Given a Boolean expression and input values, compute the output by
evaluating the expression step-by-step, just as a logic circuit would. This is a direct
application of Boolean algebra.

4.3. Networking
• IP Addresses: A unique identifier for a device on a network (e.g., [Link]). IPv4
addresses are 32 bits long, typically represented in dotted-decimal notation.
• Network Mask: A 32-bit number that distinguishes the network part of an IP address from
the host part. A 1 bit in the mask corresponds to a network bit; a 0 bit corresponds to a host
bit.
o Network Address: Found by applying a bitwise AND between the IP address and the
mask. This is the address of the network itself and cannot be assigned to a host.
o Broadcast Address: The last address in a network, used to send data to all hosts. It is
formed by setting all host bits to 1. This address cannot be assigned to a host.
o Usable Host Addresses: All addresses between the network address and the
broadcast address.
• Problem Link: Given an IP address and a subnet mask, you must calculate the range of
valid IP addresses that can be assigned to computers (excluding the network and broadcast
addresses). This involves converting the IP and mask to binary, performing a bitwise AND to
find the network address, and then determining the first and last host addresses.
o Example: For IP [Link] and mask [Link]:
1. Convert to binary (simplified): IP ~ 01100010.01010001.10011010.11000011,
Mask ~ 11111111.11111100.00000000.00000000.
2. Bitwise AND gives network address: 01100010.01010000.00000000.00000000 -
> [Link].
3. Broadcast address: Set all host bits to
1: 01100010.01010011.11111111.11111111 -> [Link].
4. Usable host range: [Link] to [Link]. The largest assignable IP
is [Link].

5. Databases and Information Systems

• Relational Databases: Data is organized into tables (relations) of rows and columns.
o Tables: The main object in a relational database. Each row is a record (tuple), and
each column is an attribute (field).
• Problem Link: Directly asking to identify the primary object in a relational database, which
is a table.

5.1. Memory Requirements for Data Storage

• Principle: To store text composed of N different symbols, each symbol
requires ceil(log₂(N)) bits. The total memory is then rounded up to bytes and multiplied by
the number of items.
• Problem Link: These problems involve calculating the minimum memory needed to store a set
of identifiers.
1. Bits per symbol: b = ceil(log₂(Alphabet_Size)).
2. Total bits for one identifier: total_bits_id = b * (Number_of_Symbols_per_Id).
3. Bytes per identifier: bytes_per_id = ceil(total_bits_id / 8).
4. Total Memory: Total_Bytes = (bytes_per_id * Number_of_Identifiers) +
(Overhead_per_Item * Number_of_Identifiers).
o Example: Storing 7,564,230 serial numbers using a 17-symbol alphabet, with the total
memory just exceeding 31 MB (≈ 31,000,000 bytes). The goal is to find the minimum
serial number length L.
▪ b = ceil(log₂(17)) = ceil(~4.09) = 5 bits/symbol.
▪ total_bits_id = 5L.
▪ bytes_per_id = ceil(5L / 8).
▪ The inequality is: 7,564,230 * ceil(5L / 8) > 31,000,000.
▪ Testing values of L shows that L=7 is the smallest that satisfies the inequality