Algorithms and Algorithm Design

Algorithms

• Types of Algorithms:
  • Sequential search: checks each item in a list one by one
  • Binary search: divides the list in half and searches for the target value
  • Bubble sort: compares adjacent items in a list and swaps them if in wrong order
  • Selection sort: finds the smallest (or largest) item in a list and moves it to the beginning (or end)
  • Insertion sort: inserts each item into its correct position in a sorted list
• Algorithm Design:
  • Step-by-step procedure for solving a problem
  • Includes input, processing, and output
  • Examples: finding the maximum value in a list, finding the average of a list
• Algorithm Efficiency:
  • Measured by time and space complexity (Big O notation)
  • Examples:
    • O(1) - constant time complexity (accessing an array by index)
    • O(n) - linear time complexity (finding an item in an array)
    • O(n^2) - quadratic time complexity (bubble sort)

Data Representation

• Number Systems:
  • Binary: base 2, uses 0s and 1s
  • Denary: base 10, uses 0-9
  • Hexadecimal: base 16, uses 0-9 and A-F
• Data Types:
  • Integer: whole numbers, e.g. 1, 2, 3
  • Float: decimal numbers, e.g. 3.14, -0.5
  • Character: single characters, e.g. 'a', 'A', '!'
  • String: sequences of characters, e.g. "hello", 'goodbye'
• Data Storage:
  • Bit: single binary digit (0 or 1)
  • Byte: group of 8 bits
  • Word: group of bytes (varies by computer system)

Computer Systems

• Hardware Components:
  • CPU (Central Processing Unit): executes instructions
  • Memory (RAM): temporary storage for data and programs
  • Storage Device (HDD/SSD): long-term storage for data and programs
  • Input/Output Devices: keyboards, mice, monitors, speakers
• Memory Hierarchy:
  • Level 1 Cache: fastest, smallest memory
  • Level 2 Cache: slower, larger memory
  • Main Memory (RAM): slower, larger memory
  • Storage Device: slowest, largest memory
• Input/Output Operations:
  • Input: data entered by user, e.g. keyboard, mouse
  • Output: data displayed to user, e.g. monitor, speakers

Networks

• Network Topology:
  • Physical: how devices are connected
  • Logical: how data is transmitted
• Network Protocols:
  • TCP/IP: Transmission Control Protocol/Internet Protocol
  • HTTP: Hypertext Transfer Protocol
  • FTP: File Transfer Protocol
• Network Devices:
  • Hub: connects multiple devices, broadcasts data
  • Switch: connects multiple devices, filters data
  • Router: connects multiple networks, routes data

Database Management

• Database Concepts:
  • Entity: person, place, or thing, e.g. customer, product
  • Attribute: characteristic of an entity, e.g. name, address
  • Record: single entry in a database, e.g. one customer's information
• Database Models:
  • Flat File: simple, text-based database
  • Hierarchical: tree-like structure, e.g. file system
  • Relational: tables with relationships, e.g. customers and orders
• Database Operations:
  • CRUD: Create, Read, Update, Delete
  • Querying: selecting specific data from a database

Algorithms

• Types of Algorithms:
  • Sequential search: checks each item in a list one by one, used for small lists or when data is not sorted
  • Binary search: divides the list in half and searches for the target value, requires a sorted list
  • Bubble sort: compares adjacent items in a list and swaps them if in wrong order, has a high time complexity
  • Selection sort: finds the smallest (or largest) item in a list and moves it to the beginning (or end), used for small lists
  • Insertion sort: inserts each item into its correct position in a sorted list, efficient for small lists or partially sorted lists
• Algorithm Design:
  • Involves breaking down a problem into smaller steps, with input, processing, and output
  • Examples: finding the maximum value in a list, finding the average of a list, and solving a Sudoku puzzle
• Algorithm Efficiency:
  • Measured by time and space complexity (Big O notation), which describes the performance of an algorithm as input size increases
  • Examples: O(1) - constant time complexity (accessing an array by index), O(n) - linear time complexity (finding an item in an array), O(n^2) - quadratic time complexity (bubble sort)

Data Representation

• Number Systems:
  • Binary: base 2, uses 0s and 1s, used in computers for representation and processing
  • Denary: base 10, uses 0-9, used for human calculation and representation
  • Hexadecimal: base 16, uses 0-9 and A-F, used for programming and data representation
• Data Types:
  • Integer: whole numbers, e.g. 1, 2, 3, used for counting and calculation
  • Float: decimal numbers, e.g. 3.14, -0.5, used for precise calculations
  • Character: single characters, e.g.'a', 'A', '!', used for text representation
  • String: sequences of characters, e.g."hello", 'goodbye', used for text representation
• Data Storage:
  • Bit: single binary digit (0 or 1), the basic unit of data
  • Byte: group of 8 bits, used for data storage and transfer
  • Word: group of bytes (varies by computer system), used for data processing and storage

Computer Systems

• Hardware Components:
  • CPU (Central Processing Unit): executes instructions, performs calculations and operations
  • Memory (RAM): temporary storage for data and programs, used for fast access
  • Storage Device (HDD/SSD): long-term storage for data and programs, used for large storage
  • Input/Output Devices: keyboards, mice, monitors, speakers, used for user interaction
• Memory Hierarchy:
  • Level 1 Cache: fastest, smallest memory, used for frequent data access
  • Level 2 Cache: slower, larger memory, used for less frequent data access
  • Main Memory (RAM): slower, larger memory, used for temporary data storage
  • Storage Device: slowest, largest memory, used for long-term data storage
• Input/Output Operations:
  • Input: data entered by user, e.g. keyboard, mouse, used for user interaction
  • Output: data displayed to user, e.g. monitor, speakers, used for user interaction

Networks

• Network Topology:
  • Physical: how devices are connected, e.g. wired, wireless, used for data transmission
  • Logical: how data is transmitted, e.g. protocols, routes, used for data transmission
• Network Protocols:
  • TCP/IP: Transmission Control Protocol/Internet Protocol, used for internet communication
  • HTTP: Hypertext Transfer Protocol, used for web communication
  • FTP: File Transfer Protocol, used for file transfer
• Network Devices:
  • Hub: connects multiple devices, broadcasts data, used for simple network connectivity
  • Switch: connects multiple devices, filters data, used for efficient network connectivity
  • Router: connects multiple networks, routes data, used for network connectivity and routing

Database Management

• Database Concepts:
  • Entity: person, place, or thing, e.g. customer, product, used for data representation
  • Attribute: characteristic of an entity, e.g. name, address, used for data description
  • Record: single entry in a database, e.g. one customer's information, used for data storage
• Database Models:
  • Flat File: simple, text-based database, used for small datasets
  • Hierarchical: tree-like structure, e.g. file system, used for organized data
  • Relational: tables with relationships, e.g. customers and orders, used for complex data
• Database Operations:
  • CRUD: Create, Read, Update, Delete, used for data manipulation
  • Querying: selecting specific data from a database, used for data analysis and retrieval