Exhaustive Compendium of Computer Science Principles and Applications

Introduction to Computer Science

• Definition of Computer Science: A discipline focused on building a scientific foundation for various computing topics including hardware, software, programming, networks, graphics, robots, databases, security, algorithmic solutions, and information processing.

• Hardware: The physical components of a system, such as the computer case, monitor, keyboard, mouse, hard disk drive, motherboard, and video card.

• Software: A set of instructions and documentation telling a computer how to perform tasks, including applications and operating systems.

• Programming: The process of designing and building executable programs to accomplish specific tasks.

• Networks: A set of connected computers for sharing resources. The Internet is the most common example; shared resources include printers and file servers.

• Computer Graphics: The discipline of generating images via computers, essential for digital photography, film, video games, and displays.

• Robots: Machines programmable by a computer to carry out complex actions automatically. Control can be external or embedded.

• Database: Also called an electronic database; an organized collection of data for rapid search and retrieval.     * DBMS: A Database Management System extracts information in response to queries.

• Security: Controls implemented to ensure confidentiality, integrity, and availability of data, software, hardware, and firmware.

• Algorithmic Solutions: An algorithm is defined as a specific set of instructions designed to perform a task.

• Information Processing: The manipulation of digitized information by computers and electronic equipment, collectively known as Information Technology (IT). Systems include business software and mainframes.

• Applications of Computer Science: Telecom, Banks, Hospitals, Software Development, Service Industry (e.g., Pak Army), and Freelancing.

• Job Market Trends:     * Pakistan: Sites like Figure 1 and 2 show higher opportunities in CS compared to other fields when filtered by function or industry.     * International: Forbes ranks Software Developer as the #1 job in the US. Critical areas include AI, Machine Learning, Data Science, Virtual Reality, IoT, Back-End/Front-End Development, UI Design, Full-Stack Engineering, IT Management, and Quality Assurance.

• Applicability for non-CS Students: Basic CS concepts are mandatory for fields like Business, Engineering, and General Sciences to apply CS tools to their specific studies.

Breadth First Learning Strategy

• Strategy Comparison:     * Breadth First Learning: Introduces almost all CS courses at a basic level first to provide a "bigger picture" of the degree program.     * Depth First Learning: Covers one specific course in exhaustive detail before moving to the next.

• Core Topics in This Course:     1. Search Engine Usage: Effective searching techniques.     2. History of Computing: Evolution from basic ideas to modern electronics.     3. Data Storage: Physics and logic of storing data in hardware.     4. Data Manipulation: Arithmetic operations ($+$, $-$, $imes$, $/$) and advanced operators.     5. Operating Systems: The "overall in-charge" of the computer.     6. Networking and the Internet: Inter-computer communication.     7. Algorithms: Sequential steps for tasks.     8. Programming Languages: Focus on the basics of $C++$.     9. Software Engineering: From requirements gathering to testing.     10. Data Abstraction: Hiding complexities; involves Arrays, Stacks, Queues, and Trees.     11. Database Systems: Organizing data using DBMS like Microsoft Access.     12. Artificial Intelligence (AI): Systems that act intelligently and make inferential decisions.     13. Social Impact: CS effects on society and human setups.     14. Security/Ethics: Content filtering, spam, and international data laws.     15. Word Processing: Functionalities of Microsoft Word.     16. Presentations: Animation and design in Microsoft PowerPoint.     17. Spreadsheets: Calculations using Microsoft Excel.     18. Web Development: Creation of web pages using tools like Dreamweaver.

Search Engine Mastery and Techniques

• Search Engine Mechanics: Engines like Google, Yahoo, and MSN index web pages to retrieve data based on queries. Google maintains the highest market share.

• The Query: The set of words provided for searching (e.g., "Virtual University").

• Case Insensitivity: Search engines do not distinguish between "COMPUTER SCIENCE" and "computer science."

• Query Formulation: Specificity is key. Using medical terms like "Headache" is more effective than "Head Hurts." Using "Rector of Virtual University" is better than "Head of Virtual University."

• Special Operations:     * Flip a Coin: Typing "Flip a Coin" provides a digital coin toss.     * Weather: "Weather [Location]" (e.g., "Weather Lahore").     * Calculations: Typing equations directly (e.g., $12 imes 391$) triggers a calculator.     * Conversions: "100 Euros in PKR," "Kph in Mph," or "m in cm."

• Search Operators (1):     * @: Search social media (e.g., "Fifa World Cup @facebook").     * pkr: Search by price (e.g., "Laptop pkr 50000").     * #: Search hashtags (e.g., "#education").     * - (Minus): Exclude words (e.g., "Jaguar -cars" to find the animal, not the vehicle).     * "" (Double Quotes): Exact match search (e.g., "Tallest Building in Pakistan").     * * (Wild Card): Fills in unknown words (e.g., "* is thicker than water").

• Search Operators (2):     * .. (Two dots): Range searching (e.g., "laptop pkr25000..pkr35000").     * Boolean OR: Finds results for either term or both.     * Boolean AND: Finds results containing both terms, though not necessarily together.     * site: Search within a specific website (e.g., "virtual university site:youtube.com").     * related: Find similar websites (e.g., "related:youtube.com").     * info: Information about a website.     * cache: View a stored version of a site if it is down.     * filetype: Search specific formats (e.g., "Virtual University" filetype:pdf).

• Search Operators (3):     * stocks: Trend data for companies (e.g., "stocks:aapl").     * map: Location search (e.g., "map: Lahore").     * movie: Details on film (e.g., "movie: Steve jobs").     * define: Term definitions (e.g., "Define: Computer").     * Image Search: https://images.google.com allows searching using words or other images.     * Advanced Operators:         * intitle: Term must be in the title.         * allintitle: All terms must be in the title.         * inurl / allinurl: Search within the URL text.         * intext / allintext: Search specific text in the body of the document.         * AROUND(n): Proximity search (e.g., "Education AROUND(3) 'virtual university'" searches for the terms within 3 words of each other).

• Security Contexts (What Not to Search):     * Avoid Ads: Your name, location, or medical issues to prevent targeted advertising.     * Security Agencies: Avoid terms related to bombs, suicide attacks, killers, poisons, or making viruses (e.g., the "Pressure cooker bomb story" alert).     * Cyber-security Attacks: Avoid searching for "Free Music" or "Free Software" as hackers often use these as bait for viruses.     * Unpleasant Results: Images like "Smokers Lungs" or "Skin Condition."

Roots and Evolution of Computing

• Ancient Roots: The Abacus (China, Greece, Rome) used beads on rods for basic counting.

• Gear Technology (Middle Ages - Modern Era):     * Blaise Pascal (1623–1662): Developed mechanical gear machines.     * Gottfried Wilhelm Leibniz (1646–1716): Advanced gear-based calculation.     * Charles Babbage (1792–1871): Envisioned the Analytical Engine that could print results on paper to reduce transcription errors.

• Punch Cards: Herman Hollerith (1860–1929) used holes in paper cards to tabulate the 1890 U.S. Census; this work led to the creation of IBM.

• Transition to Electronics:     * Electromechanical Machines: George Stibitz (1940, Bell Labs) and the Mark I (1944, Harvard/IBM) used electronically controlled relays.     * ENIAC (Electronic Numerical Integrator and Calculator): Developed by Mauchly and Eckert (University of Pennsylvania).         * Stats: 1,800 square feet, 20,000 vacuum tubes, 1,500 relays, 10,000 capacitors, 70,000 registers, 200 kW electricity, 30 tons, cost $487,000 (approx. 62.5 million PKR).

• Era of Rapid Advancement:     * Invention of transistors and Integrated Circuits.     * Moore's Law Effect: Processing power doubling roughly every 2 years.     * 1976: Steve Jobs and Stephen Wozniak launched the desktop computer.     * 1981: IBM launched the PC.     * The rise of the Web and Smartphones.

Data Representation: Bits and Units

• Definition of Bit: The basic unit of storage; a binary digit representing 0 or 1.

• Bit Patterns:     * 1 Bit = $2^1 = 2$ patterns (0, 1)     * 2 Bits = $2^2 = 4$ patterns (00, 01, 10, 11)     * $n$ Bits = $2^n$ patterns.

• Standard Units:     * Byte: 8 Bits.     * KB (Kilobyte): $2^{10} = 1024$ bytes.     * MB (Megabyte): $2^{20} = 1,048,576$ bytes.     * GB (Gigabyte): $2^{30} = 1,073,741,824$ bytes.     * TB (Terabyte): $2^{40} = 1,099,511,627,776$ bytes.

• Decimal to Binary Conversion: Representation uses base 2. For example, decimal 65 is encoded in ASCII as $01000001$ ($64 + 1$).

Logic and Boolean Operations

• Logic Pioneer: George Boole (1815–1864).

• Basic Operations:     * AND: Output is 1 only if both inputs are 1.     * OR: Output is 1 if at least one input is 1.     * XOR (Exclusive OR): Output is 1 if inputs are different; 0 if inputs are the same.     * NOT: Inverts the input (0 becomes 1, 1 becomes 0).

• Hexadecimal Notation: A shorthand for long bit strings using base 16. Four bits are represented by one hex symbol (0-9, A-F).     * Example: $111010000101010100010111$ is divided into groups of 4 ($1110, 1000, 0101, 0101, 0001, 0111$) to become $E85517$.

Storing Data: Main Memory and Mass Storage

• Flip-flops: Circuits capable of storing a single bit.

• Main Memory Organization: Organized into cells, typically 8 bits (1 byte) each. Each cell has a unique address.

• RAM (Random Access Memory): Allows independent access to cells in any order.     * DRAM (Dynamic RAM): Stores bits as electric charge; requires refreshing.     * SDRAM (Synchronous DRAM): Uses techniques to decrease retrieval time.

• Mass Storage (Secondary Storage): Magnetic disks, CDs, DVDs, Flash drives, SSDs.     * Magnetic Disks: Thin spinning disks with magnetic coating. Read/write heads traverse tracks (divided into sectors).         * Zoned-bit recording: Adjacent tracks form zones to equalize sector density.         * Seek Time: Moving head between tracks.         * Rotation Delay: Time for the disk to rotate to the correct sector.         * Access Time: Sum of seek time and rotation delay.

• Optical Systems: Uses lasers to read variations in reflective surfaces.     * CD (Compact Disk): 12cm, 700MB capacity, single-track spiral.     * DVD (Digital Versatile Disk): Multi-layered; GB capacity.     * BD (Blu-ray Disk): Blue-violet laser allows finer precision and 5x capacity of DVDs.

• Flash Drives and SSDs:     * Flash: Stores bits by trapping electrons in silicon dioxide chambers. No physical motion required.     * SSD (Solid State Disk): Large flash devices replacing magnetic disks; faster but more expensive.     * SD Cards: Up to TB capacity (SDHC = 32GB; SDXC = TBs).

Representing Text, Numeric Values, Images, and Sound

• Text Representation:     * ASCII: 7 bits (128 characters), with the 8th bit usually 0. Includes control characters (tabs, carriage returns).     * Unicode: Uses 21 bits; supports thousands of characters (Chinese, Hebrew, etc.).     * UTF-8: Variable length (24-32 bits); allows for expansion up to $16,777,216$ symbols.

• Numeric Values:     * Binary Notation: Uses $2^n$ representations.     * Two's Complement: Stores whole numbers (integers); left bit is the sign bit.     * Floating Point: Stores fractional values using a sign bit, exponent field (excess notation), and mantissa field (normalized form).

• Image Storage:     * Pixel: Picture Element. Bitmaps encode pixel appearance.     * Handling Color: RGB encoding uses 3 bytes per pixel (one for Red, Green, and Blue).     * Luminance/Chrominance: Separates brightness from color.     * Image Scaling: Scaling bitmaps causes pixelation; Geometric/Vector structures (TrueType/PostScript) define lines and curves to avoid this.

• Sound Representation:     * Sampling: Measuring sound amplitude at intervals.         * Telephone: 8,000 samples/sec.         * CD: 44,100 samples/sec (16 bits for Mono, 32 for Stereo).     * MIDI (Musical Instrument Digital Interface): Stores "directions" for building music (sheet music approach) rather than the sound itself. Highly storage-efficient.

Binary Arithmetic and Notation Variances

• Binary Addition Rules:     * $0 + 0 = 0$     * $0 + 1 = 1$     * $1 + 0 = 1$     * $1 + 1 = 10$ (Sum 0, Carry 1).

• Radix Point: The binary version of a decimal point. Fractional parts represent powers of 2 in the denominator ($2^{-1} = 1/2$, $2^{-2} = 1/4$, etc.).

• Excess Notation: A system where bit patterns are shifted so that the pattern starting with a 1 represents zero (e.g., Excess-8 uses $1000$ as zero).

• Truncation Errors: Occur when the mantissa field cannot accommodate all bits of a fraction (e.g., trying to store $1/10$ in binary).     * Mitigation: Add small quantities together before adding to a large quantity.     * Significance: A hospital system malfunctioned on Sept 19, 1989, because 32,768 days (the limit for a 16-bit 2's complement integer) had passed since Jan 1, 1900, causing a negative overflow.

Data Compression Techniques

• Lossless: No information lost (Run-length encoding, Huffman/frequency-dependent encoding, dictionary encoding/LZW).

• Lossy: Information lost but barely perceptible (JPEG, MP3, MPEG).

• Specific Methods:     * LZW (Lempel-Ziv-Welsh): Adaptive dictionary encoding used in GIFs.     * JPEG (Joint Photographic Experts Group): Uses Discrete Cosine Transform and averages chrominance values to exploit eye sensitivity.     * TIFF (Tagged Image File Format): Often uncompressed; stores metadata like camera settings.     * MPEG (Motion Picture Experts Group): Uses I-frames (entire images) and relative encoding (differences between frames).     * MP3: Uses temporal masking (loud sounds hiding soft ones) and frequency masking.

• Transmission Speeds: Measured in bits per second ($bps$).     * $Kbps$ (kilo), $Mbps$ (mega), $Gbps$ (giga).     * Video usually requires $40 Mbps$, while MP3 requires $64 Kbps$.

CPU Architecture and Logic Manipulation

• CPU Components:     * Arithmetic/Logic Unit (ALU): Performs math and logic.     * Control Unit: Coordinates machine activities.     * Registers: Temporary high-speed storage (General-purpose vs. Special-purpose).

• Bus: Wires connecting CPU and Main Memory for data transfer (Read/Write).

• Stored-Program Concept: Realization that programs (instructions) can be stored in memory just like data (von Neumann Architecture).

• CPU Philosophies:     * RISC (Reduced Instruction Set Computer): Minimal instructions, fast, energy-efficient (e.g., ARM Holdings and PowerPC).     * CISC (Complex Instruction Set Computer): Rich instruction set, complex circuitry (e.g., Intel and AMD).

• Instruction Groups:     * Data Transfer: LOAD (memory to register), STORE (register to memory), and I/O.     * Arithmetic/Logic: Requests ALU activity.     * Control: Directs program flow (e.g., JUMP instructions).

• Machine Cycle:     1. Fetch: Load instruction from memory into the Instruction Register (IR). Increment the Program Counter (PC).     2. Decode: Analyze the bit pattern to determine the task.     3. Execute: Perform the instruction tasks.