Quiz Bowl

Time-Space trade off

More memory = Faster algorithm

Auxiliary Space

Allocated temporary space

Big O notation

Worst case scenario

Omega notation

Best case scenario

Theta notation

Average behavior

O(1)

Static operation count

O(log n)

The problem space is repeatedly halved

O(n²)

Perform n operations for every n element

Arrays

Contiguous, Faster

Linked-lists

Scattered with pointers, more memory

Singly Linked-lists

One directional, less memory

Doubly Linked-lists

Two directional, more memory

Stack

Last In, First Out

Recursion Stack

A region of memory used to manage function calls

Stack overflow

A problem that occurs when too many recursive calls fills the memory limit

Queue

First In, First Out

Circular buffer

When the rear index hits the end, it loops back to index 0 to reuse empty space

Stable Sort

Keeps the order of the duplicate array

Unstable Sort

Doesn't keep the original order of the duplicate array

Merge sort (Div)

The array is repeatedly halved until 1 unit remains

Merge sort (Mrg)

The stack frames are popped off the stack and takes two of the sorted half and merge them into a single sorted array

Quick sort

A chosen value is compared to its neighbours and is moved to the left if it is smaller and to the right if it is larger

Binary Search

In a SORTED array, if the target is smaller than the median, it ignores the right side, and vice vers for if the target us larger than the median

Binary Search Tree

Binary search performed on a tree; consists of Root, and Left & Right children

BST Traversal In-Order

Left > Root > Right

BST Traversal Pre-Order

Root > Left > Right

BST Traversal Post-Order

Left > Right > Root

Binary Heap

Standard way of doing priority queues because of its time complexity in finding the Min/Max being 0(1)

Hashing

Converts input data into fixed-length strings, which acts as a unique digital key

De Morgan's Law

‘(AB) = ‘A+‘B

‘(A+B) = ‘A’B

Idempotent Law

A • A = A

A + A = A

Sums of Products

OR of AND Terms

Products of Sums

AND of OR Terms

Karnaugh-Map

Used for simplifying Boolean Expression

Latches

Acts as a storage for 1 Bit and can change states as long as power is applied (level-triggered)

Flip-Flops

Acts as a storage for 1 Bit and can change states on certain transition of clock signals (edge-triggered)

Moore Machine

Output depends on the current state (synced with clock)

Mealy Machine

Output depends on both the current state and current input (changes immediately when input changes)

RISC

Simple and single-cycled instructions

CISC

Complex, Variable-length instructions

Programmes I/O

The CPU constantly asks/polls if the device is ready, thus wasting time

Interrupt-Driven I/O

The device sends an interrupt signal when ready, otherwise the CPU works on other tasks

Direct Memory Access (DMA)

Communication between Devices and Memory is done through a special controller, bypassing the CPU

Flynn's Taxonomy

Classification of computer architecture via instruction streams and data streams

SISD

The CPU sequentially works with one data stream, executing one instruction after another

SIMD

A single instruction is instructed on multiple processing units, allowing for parallel processing wherein the same operation can be done on different data simultaneously

MISD

An architecture that involves multiple control units wherein a set of instructions can be executed on a single data stream, allowing for reliability and fault tolerance

MIMD

Often used in modern CPUs, wherein multiple processors can execute different instructions while working on different data streams, allowing for true and efficient parallel processing

RAID

A technology that combines multiple disks into one logical disks to improve performance and/or redundancy

RAID 0 (Striping)

SPREADS the data into 2 or more drives, allowing for maximum speed and capacity but with no fault tolerance

RAID 1 (Mirroring)

COPIES the data into 2 or more logical drives. It offers good reliability and read speeds, but storage capacity is cut in half

RAID 5 (Striping with Distributed Parity)

Uses 3 or more drives. Balances performance, capacity, and redundancy. Can survive 1 drive failure.

RAID 6 (Double Distributed Parity)

Uses the same logic as RAID 5, but writes parity data twice, allowing for up to 2 data failures.

RAID 10 (Striping and Mirroring)

Combines RAID 0 & 1, uses 4 drives. Offers high reliability and high speed.

Microcontrollers

A “System on a Chip”, has internal RAM, ROM, and I/O ports.

Microprocessors

A CPU on a Chip. Has no internal RAM, ROM, and I/O Devices, unlike MCU.

Control Bus

A unidirectional bus, carrying the address of the data. It's width determines the maximum addressable memory of 2^n

Data Bus

A bidirectional bus which carries the actual data.

Control Bus

Carries the control signal such as Read, Write, and Interrupt.

Accumulator (AX)

Used for Arithmetic, Logic, and Data Transfers.

Base (BX)

Used as a base address for memory access

Counter (CX)

Used as a Loop counter and for shift/rotate operations

Data (DX)

Used for I/O Port addressing and holds the high bits for multiplication and division

Code Segment (CS)

Points to where the code is stored

Data Segment (DS)

Points to where the variables are stored

Stack Segment

Points to the Stack Memory

Extra Segment (ES)

Used for String Operations

Stack Pointer

Points to the top of the stack

Base Pointer

Points to the base address of the current functions Stack Frame

Source Index

Used in tandem with Data Segment, points to the source memory address during string operations

Destination Index (DI)

Used for String Operations, points to the destination memory address.

Program Counter/Instruction Pointer

Points to the address of the next instruction

RA 10173

Data Privacy Act

RA 10175

Cybercrime Law

RA 8293

Intellectual Property Code of the Ph

RA 9995

Anti Photo and Video Vouyerism

RA 8792

E-commerce Act

RA 9775

Anti Child Pornography Law

RA 11337

Innovative Startup Act