Data Types, Data Structures, and Algorithms

This computer science section covers data types, data structures, and algorithms including Boolean algebra.

Data Types

Primitive Data Types

Integer: Whole numbers, positive or negative (e.g., 5, -12).

Real/Floating Point: Numbers with decimal points (e.g., 3.14, -0.001).

Character: A single symbol or letter (e.g., 'A', '7').

String: A sequence of characters (e.g., "Hello").

Boolean: Represents two states: True or False.

Representing Positive Integers in Binary

Binary numbers use base-2 (digits 0 and 1). For example, the decimal number 13 is 1101 in binary.

Representing Negative Numbers in Binary (Sign and Magnitude, Two’s Complement)

Sign and Magnitude: The most significant bit (MSB) represents the sign (0 = positive, 1 = negative). The remaining bits store the magnitude.

Two’s Complement: Used for negative numbers, where the MSB indicates the sign. To find the two's complement of a number, invert all bits and add 1 to the result.

Addition and Subtraction of Binary Integers

Binary Addition: Follows the same process as decimal addition, but values are carried over when the sum exceeds 1.

Example:

1011 (11 in decimal)

0101 (5 in decimal)

= 10000 (16 in decimal)

Binary Subtraction: Uses two’s complement to represent negative numbers, then adds them to perform subtraction.

Representing Positive Integers in Hexadecimal

Hexadecimal uses base-16 (digits 0-9, A-F). For example, 255 in decimal is FF in hexadecimal.

Converting Between Binary, Hexadecimal, and Denary

To convert:

Binary to Hexadecimal: Group binary digits into 4-bit sections, convert each group into its hexadecimal equivalent.

Denary to Binary/Hexadecimal: Repeatedly divide by 2 for binary or by 16 for hexadecimal.

Representation and Normalisation of Floating Point Numbers in Binary

A floating-point number is represented using sign, exponent, and mantissa.

Normalisation: Adjusts the mantissa so the leading digit is always non-zero (e.g., 1.xxxx in binary).

Floating Point Arithmetic (Addition and Subtraction)

To add or subtract floating-point numbers, ensure exponents are aligned before performing arithmetic on the mantissa.

Bitwise Manipulation and Masks

Shifts: Moving bits left or right, effectively multiplying or dividing by powers of 2.

Bitwise AND, OR, XOR: Logical operations applied to individual bits.

AND: Both bits must be 1.

OR: At least one bit must be 1.

XOR: Only one bit must be 1, not both.

Character Sets (ASCII and Unicode)

ASCII: A 7-bit character set representing 128 characters.

Unicode: A more extensive character set that includes characters from many languages, supporting over 143,000 characters.

Data Structures

Arrays, Records, Lists, Tuples

Arrays: A collection of elements, all of the same type, stored in contiguous memory. Can be single or multi-dimensional (up to 3 dimensions).

Records: A collection of fields with different data types, similar to a row in a database.

Lists: An ordered collection of elements that can be of mixed types.

Tuples: Similar to lists but immutable (cannot be changed after creation).

Data Structures to Store Data

Linked List: A sequence of nodes, where each node contains data and a pointer to the next node. Can be singly or doubly linked.

Graph: A collection of vertices (nodes) connected by edges. Can be directed (edges have direction) or undirected.

Stack: A last-in, first-out (LIFO) structure. Elements are added and removed from the top.

Queue: A first-in, first-out (FIFO) structure. Elements are added to the rear and removed from the front.

Tree: A hierarchical structure with a root node and child nodes. Binary Search Tree (BST) is a type of tree where each node has at most two children, and the left child is less than the parent, while the right child is greater.

Hash Table: Stores key-value pairs. A hash function computes an index into an array of buckets, from which the correct value can be found.

Creating, Traversing, Adding, and Removing Data from Structures

Arrays: Use indexing to access, add, and remove elements.

Linked Lists: Traverse by following the pointers from node to node. Add or remove nodes by adjusting pointers.

Graphs: Can be traversed using algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS).

Stacks/Queues: Add elements to the stack/queue using push (stack) or enqueue (queue), and remove them using pop (stack) or dequeue (queue).

Trees: Traverse using pre-order, in-order, or post-order traversal. Insert elements by comparing with the current node and placing them in the correct subtree.

Hash Tables: Insert elements by computing the hash key and placing the data in the appropriate bucket. Handle collisions using methods like chaining.

Boolean Algebra

Define Problems Using Boolean Logic

Boolean logic involves variables that take values True (1) or False (0). It is used to describe logical conditions and make decisions in computing.

Manipulating Boolean Expressions

Simplify Boolean expressions using Boolean identities, such as:

A AND 0 = 0, A OR 1 = 1.

Karnaugh Maps: Used to simplify Boolean expressions by grouping adjacent 1s in a truth table to form simpler expressions.

Boolean Algebra Rules

De Morgan’s Laws:

NOT(A AND B) = NOT(A) OR NOT(B)

NOT(A OR B) = NOT(A) AND NOT(B)

Distribution: A AND (B OR C) = (A AND B) OR (A AND C).

Association: (A AND B) AND C = A AND (B AND C).

Commutation: A AND B = B AND A.

Double Negation: NOT(NOT(A)) = A.

Logic Gate Diagrams and Truth Tables

Logic Gates:

AND Gate: Outputs true only if both inputs are true.

OR Gate: Outputs true if at least one input is true.

NOT Gate: Inverts the input.

NAND, NOR, XOR Gates: Variations of basic gates with combined logic.

Truth Tables: Show the output of a logic gate for all possible combinations of inputs.

Logic Associated with D-Type Flip Flops, Half and Full Adders

D-Type Flip Flops: Store a single bit of data. The output changes based on the input and the clock signal.

Half Adder: Adds two binary digits and produces a sum and carry output.

Full Adder: Adds three binary digits (including a carry-in bit) and produces a sum and carry output. Can be used to build more complex addition circuits.