Comprehensive Study Notes: CS101 Introduction to Computing

Introduction to Computer Science and its Foundations

• Definition of Computer Science: It is a discipline seeking a scientific foundation for various computing topics. Key pillars include:

  • Hardware: Physical parts of the computer (case, monitor, motherboard, hard disk, mouse, keyboard). These are components you can physically touch.

  • Software: A set of instructions and documentation telling a computer how to perform tasks. This includes applications and the operating system.

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

  • Networks: Computers connected to share resources (Internet, printers, file servers).

  • Graphics: The generation of images using computers (used in digital photography, games, and cell phone displays).

  • Robots: Machines programmable by a computer to carry out complex actions automatically, via external or embedded control.

  • Databases: Specially organized collections of data for rapid search and retrieval. Managed via a Database Management System (DBMS).

  • Security: Controls put in place to provide confidentiality, integrity, and availability for system components (data, hardware, firmware).

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

  • Information Processing: Digitized information manipulation by computers, known as Information Technology (IT).

• Applications of Computer Science: CS applies to virtually all domains including Telecom, Banks, Hospitals, Software Development, the Service Industry, Military (Pak Army), and Freelancing.

• Job Market Insights:

  • Local (Pakistan): Job opportunities in CS are currently higher than in any other field when classified by either industry or function.

  • International: Forbes magazine ranked Software Developer as the #1 job in the US. High-ranking CS areas include: Artificial Intelligence (AI), Machine Learning, Data Science, Virtual Reality, IoT, Back-End/Front-End Development, UI Design, Full-Stack Engineering, IT Management, and Quality Assurance (QA).

• Breadth-First Learning: This course employs a "Breadth-First" strategy, providing a basic introduction to almost all CS courses (abstract view) to clarify the "bigger picture" before specializing (Depth-First Learning).

Search Engines and Search Operators

• Google Dominance: Google holds the vast majority of the market share compared to Yahoo or MSN.

• Query Literacy:

  • Query: The set of words provided to the search engine.

  • Mechanism: Google finds pages containing all terms in the query.

  • Case Sensitivity: Google is case-insensitive; "COMPUTER SCIENCE" is the same as "computer science."

  • Query Formulation: Use medical/technical terms for better results (e.g., "Headache" instead of "Head hurts"; "Rector of Virtual University" instead of "Head").

• Tools and Tricks:

  • Microphone: Allows for voice-activated searching.

  • Flip a Coin: Typing "Flip a Coin" launches a coin-toss simulation.

  • Weather: "Weather [Location]" provides instant weather stats.

  • Calculations: Direct input (e.g., $12 \times 391$, $\sin(90)$, $\tan(80)$, $80/100 \times 200$) launches a calculator.

  • Conversions: Unit and currency conversions (e.g., "100 Euros in PKR", "Kph in Mph", "m in cm").

• Standard Search Operators:

  • Social Media: Use @ (e.g., Fifa World Cup @twitter).

  • Prices: Use pkr or currency symbols (e.g., Laptop pkr 50000).

  • Hashtags: Use # (e.g., #education).

  • Exclusion: Use - to remove terms (e.g., Jaguar -cars to find the animal only).

  • Exact Match: Enclose phrase in double quotes " " (e.g., "Tallest Building in Pakistan").

  • Wildcard: Use * to fill in unknown words (e.g., "* is thicker than water").

  • Range: Use two dots .. (e.g., laptop pkr25000..pkr35000).

  • Boolean: AND (both words must appear), OR (either word can appear).

  • Site Specific: site:webname.com (searches only within that URL).

  • Related/Info: related:youtube.com (finds similar sites); info:youtube.com (site information).

  • Cache: cache:youtube.com (shows a saved version if the site is down).

  • Filetype: filetype:pdf or ext:pdf filters results by extension.

• Specialized and Advanced Operators:

  • Stocks: stocks:aapl shows market trends.

  • Maps: map:Lahore.

  • Define: define:Computer provides verbatim definitions.

  • Tilt: Typing tilt rotates the screen functionality.

  • Intitle: intitle:"iPhone vs. android" (term must be in page title).

  • Allintitle: allintitle:iphone vs. android (any of the terms in title).

  • Inurl/Allinurl: Searches for terms within the URL string.

  • Intext/Allintext: Searches for terms specifically in the body text.

  • Proximity Search: AROUND(n) (e.g., education AROUND(3) "virtual university") finds pages where the two terms are within n words of each other.

• Privacy and Security Warnings: What not to search:

  • To avoid ads: Avoid searching personal info, medical drug names, or your location.

  • To avoid legal flags: Avoid keywords like "Pressure cooker bomb", "Attacks", "Poison", "Murder", "Hacking", or "How to make computer virus."

  • To avoid Malware: Avoid "Free Music" or dubious pirate sites which are often infested with viruses.

Roots of Computing and Hardware Foundations

• The Abacus: Ancient computing device from China, Greece, and Rome using beads on rods.

• Gear Technology:

  • Blaise Pascal, Gottfried Leibniz: Experimented with gears where output was read by final positions.

  • Charles Babbage: Envisioned gear machines that printed results to eliminate transcription errors.

• Punched Cards: Developed by Herman Hollerith (founder of what became IBM) for the 1890 U.S. Census; used into the 1970s.

• Transition to Electronics:

  • George Stibitz: Electromechanical machine at Bell Labs (1940).

  • Mark I: Completed at Harvard (1944) using mechanical relays.

  • ENIAC (Electronic Numerical Integrator and Calculator): Created by Mauchly and Eckert.

    • Stats: 1800 sq ft, 20,000 vacuum tubes, 30 tons, cost $487,000$, consumed $200\,kW$.

• Milestones of Advancement: Transistor, Integrated Circuits, Desktop computer (Jobs/Wozniak 1976), IBM PC (1981), World Wide Web, Smartphones.

• Data Representation (Bits):

  • Bit: Short for Binary Digit; basic unit of storage (0 or 1).

  • Capacity: $n$ bits can represent $2^n$ patterns.

  • Byte: 8 bits ($2^8 = 256$ patterns).

  • Measurement Units:

    • $1\,KB = 1024\,Bytes$

    • $1\,MB = 1024\,KB$

    • $1\,GB = 1024\,MB$

    • $1\,TB = 1024\,GB$

• Boolean Operations:

  • AND: Result is 1 only if both inputs are 1.

  • OR: Result is 1 if any input is 1.

  • XOR: Result is 1 if inputs are different; 0 if they are same.

  • NOT: Inverts the input.

• Hexadecimal Notation: Shorthand for bit streams. Groups bits into fours.

  • Scale: $0–9$ then $A(10), B(11), C(12), D(13), E(14), F(15)$.

  • Example: bit pattern 1110 1000 is E8 in hex.

Memory and Mass Storage Systems

• Main Memory: Reservoir of bits stored in circuits called flip-flops.

  • Address: A unique "name" identifying a specific cell.

  • RAM (Random Access Memory): Ability to access cells in any order.

  • DRAM (Dynamic RAM): Stores bits as tiny electric charges; must be refreshed frequently.

  • SDRAM (Synchronous DRAM): Faster retrieval techniques.

• Magnetic Storage: Thin spinning disks with magnetic coating.

  • Track: Circle traversed by the read/write head.

  • Sector: Equal segments of a track (typically $512\,bytes$ to a few $KBs$).

  • Zoned-bit Recording: Adjacent tracks form zones. Tracks in a zone have the same number of sectors.

  • Performance Metrics:

    • Seek Time: Time to move head to track.

    • Rotation Delay: Time for data to rotate under head.

    • Access Time: Seek Time + Rotation Delay.

    • Transfer Rate: Rate bits move to/from disk.

• Optical Systems:

  • CD (Compact Disk): $12\,cm$ diameter; uses lasers to detect pits on reflective surfaces. Spirals from inside to outside.

  • DVD (Digital Versatile Disk): Multiple semi-transparent layers; higher capacity than CD.

  • BD (Blu-ray): Uses blue-violet spectrum for finer precision; $5\times$ DVD capacity.

• Flash Memory: Bits stored by trapping electrons in silicon dioxide chambers.

  • SSD (Solid State Disks): Flash-based replacements for magnetic disks; no moving parts.

  • SD cards: High-capacity (SDHC up to $32\,GB$; SDXC up to $TB$ sizes).

Storing and Representing Data

• Text Representation:

  • ASCII: 7-bit code (128 characters) for Western symbols. 8th bit usually zero.

  • Unicode: 21-bit patterns; supports thousands of characters (Chinese, Hebrew, etc.).

  • UTF-8: 24 to 32 bit variations; compatible with ASCII.

• Image Representation:

  • Pixel: Single picture element.

  • Bitmap: Collection of encoded pixels.

  • Black/White: 1 bit per pixel.

  • Grayscale: 8 bits (256 shades).

  • RGB: 3 bytes per pixel (Red, Green, Blue).

  • Brightness/Chrominance: Luminance (sum of RGB) vs Color components.

  • Scaling: Geometric structures (Vector/Analytical Geometry) allow scaling without pixelation (e.g., TrueType, PostScript).

• Sound Representation:

  • Sampling: Recording amplitude at intervals.

  • Rates: $8000\,samples/sec$ (phone); $44,100\,samples/sec$ (CD).

  • MIDI: Encodes instructions for synthesizers rather than raw audio waves.

• Binary Math Fundamentals:

  • Addition: $0+0=0, 1+0=1, 1+1=10$ (0 carry 1), $1+1+1=11$ (1 carry 1).

  • 2’s Complement (Integers): Leftmost bit is the sign bit (0 for positive, 1 for negative).

    • Conversion Trick: To find negative of a number, start from right, copy until first 1, then invert all remaining bits to the left.

    • Overflow: Occurs when result is too large for the bit length; detectable via the sign bit.

  • Excess Notation (Integers): A system where a specific pattern (e.g., 100 for Excess 4) represents zero. Numbers are an "excess" offset of the binary value.

  • Floating-Point (Fractions): Sign bit + Exponent + Mantissa.

    • Normalization: Mantissa always starts with the leftmost 1.

    • Truncation Error: Round-off error caused by limited mantissa length (e.g., $1/10$ is non-terminating in binary).

Data Compression and Manipulation

• Generic Techniques:

  • Lossless: No info lost (Run-length encoding, Huffman codes, LZW).

  • Lossy: Info lost (JPEG, MP3). Higher compression ratios.

  • LZW (Lempel-Ziv-Welsh): Adaptive dictionary encoding where recurring patterns are added to the dictionary.

• Media Specific Compression:

  • GIF: lossy/dictionary-based; limited to 256 colors.

  • JPEG: uses Discrete Cosine Transform; ignores details humans can't see. Compresses $10\times$ to $30\times$.

  • MPEG/MP3: Video uses I-frames (full pictures) + relative encoding (differences between frames). MP3 uses temporal/frequency masking to remove perception-redundant sounds.

• The CPU (Central Processing Unit):

  • ALU (Arithmetic/Logic Unit): Performs calculations.

  • Control Unit: Co-ordinates activities.

  • Registers: General-purpose (temporary storage) and Special-purpose (Instruction Register/Program Counter).

  • The Bus: Collection of wires connecting CPU to Main Memory.

• Architecture Philosophies:

  • CISC: Large, complex instruction set (Intel/AMD standard).

  • RISC: Minimal, efficient instruction set; low power (ARM standard used in mobile).

• Machine Cycle: Fetch, Decode, Execute.

• Management Utilities:

  • Controllers: Intermediaries between CPU and peripherals (USB, FireWire).

  • DMA (Direct Memory Access): Controller accesses memory without CPU intervention, avoiding the "von Neumann bottleneck."

  • Pipelining: Overlapping machine cycle steps to increase throughput.

Operating Systems (OS)

• Evolution:

  • Batch Processing: Jobs collected and executed in a queue (FIFO).

  • Interactive Processing: Dialogue via terminals.

  • Time-Sharing: Servicing multiple users simultaneously.

• Software Classification:

  • Application Software: Specific tasks (spreadsheets, games).

  • System Software: Infrastructure (OS and Utility software like formatting tools).

• Kernel Components:

  • User Interface: Shell (textual) or GUI (graphical/icons).

  • File Manager: Hierarchical folders and directory paths.

  • Device Drivers: Translate generic requests to specific hardware signals.

  • Memory Manager: Allocates space; uses Paging to create Virtual Memory.

  • Scheduler/Dispatcher: Manages processes and Time Slices via interrupts.

• Booting: The "bootstrap" process. ROM contains a Boot Loader that transfers the OS from mass storage to volatile RAM.

• Security Concerns:

  • Deadlock: Needs three conditions (competition for non-sharable resources, partial requests, non-forcible retrieval). Handled via detection or avoidance (e.g., spooling).

  • Privilege Levels: CPU operates in Privileged and Non-privileged modes to prevent processes from altering the OS.

  • Semaphores: Flags used to ensure Mutual Exclusion in Critical Regions of code.

Networking and the Internet

• Classification:

  • Size: PAN (Personal), LAN (Local), MAN (Metropolitan), WAN (Wide Area).

  • Pattern: Bus (Ethernet) and Star (Wireless/Access Points).

  • Control/Access: Open (TCP/IP) vs Closed (Proprietary).

• Protocols:

  • CSMA/CD: Ethernet collision detection (talk, clash, wait).

  • CSMA/CA: Wireless collision avoidance. Handles the "Hidden Terminal Problem."

• Hardware Connectivity: Repeaters (amplification), Bridges (selective forwarding), Switches (multi-port bridge), Routers (connect incompatible networks via forwarding tables).

• Models:

  • Client/Server: Defined roles.

  • Peer-to-Peer (P2P): Processes provide and receive services (Swarms).

• Distributed Systems:

  • Clusters/Grids: Independent computers working as one.

  • Cloud Computing: Large pools of shared computers (Google Drive, Amazon EC2).

• Architecture & Addressing:

  • ISPs: Tier-1 (Backbone), Tier-2 (Regional), Tier-3 (Access/Hotspots).

  • IP Addresses: 32-bit (IPv4) or 128-bit (IPv6). Often in dotted decimal form (e.g., 192.207.177.133).

  • DNS (Domain Name System): Translates mnemonic names (mu.edu) to IP addresses. TLDs include .com, .edu, .gov, .org.

• Applications:

  • Email: SMTP (sending), POP3/IMAP (receiving), MIME (non-ASCII support).

  • Web: HTTP, HTML (markup via tags like <head>, <body>, <a>, <img>), XML (standardized text-based data representation).

  • Communication: VoIP (Skype), Streaming (Netflix/YouTube).

• Layers of software: Application (messages) -> Transport (packets/TCP/UDP) -> Network (routing/IP) -> Link (transmission).

• Security Attacks:

  • Phishing: Gathering info via fake sites.

  • DoS (Denial of Service): Overwhelming targets using Botnets.

  • Cures/Protection: Firewalls, Proxy Servers, Malware/Antivirus software, Public Key Encryption (Digital Signatures).

Algorithms and Software Engineering

• Algorithm Definition: Ordered set of unambiguous, executable, and terminating steps.

• Discovery Strategies: Polya’s phases (Understand, Plan, Carry out, Evaluate). Techniques include Stepwise Refinement and working backwards.

• Search Efficiency:

  • Sequential Search: Average $n/2$ comparisons.

  • Binary Search: Maximum $\log_2 n$ comparisons.

• Programming Generations:

  • 1st: Machine Language (numerics).

  • 2nd: Assembly (mnemonics, assemblers).

  • 3rd: High-level (compilers/interpreters). Machine independent.

• Paradigms:

  • Imperative: Sequence of commands (C, Python).

  • Declarative: Describes the problem (Logic programming/Prolog).

  • Functional: Nested functions (LISP).

  • Object-Oriented (OOP): Units called objects; uses Classes (templates) and Methods.

• Life Cycle (Waterfall/Iterative): Requirements Analysis -> Design -> Implementation -> Testing -> Maintenance.

• Testing Types:

  • Glass-box: Tester knows internal structure.

  • Black-box: User POV. Includes Boundary Value Analysis.

  • Pareto Principle: Testing the small number of modules where most errors clump.

• Design Considerations:

  • Coupling: Minimize linkage (Data vs Control coupling).

  • Cohesion: Maximize internal binding (Functional cohesion).

  • Information Hiding: Encapsulation of data.

Databases and Data Mining

• Database vs Flat File: Databases are multidimensional with integrated linkages.

• Relational Model:

  • Relation: Table.

  • Tuple: Row.

  • Attribute: Column.

• Relational Operators:

  • SELECT: Extracts specific rows.

  • PROJECT: Extracts specific columns.

  • JOIN: Combines tables based on common attributes.

• Data Integrity:

  • Commit/Rollback: Using logs to ensure transactions are either 100% finished or undone.

  • Locking: Shared vs Exclusive locks to prevent "Lost Updates."

• File Organizations:

  • Sequential: Accessed start to end; uses EOF sentinels.

  • Indexed: Uses a separate key file for quick access.

  • Hashing: Uses a hash function to map keys to Buckets. Prime numbers (like 41) prevent Clustering.

• Data Mining:

  • Data Warehouses: Snapshots of data for pattern discovery.

  • Techniques: Cluster analysis (finding groups), Outlier analysis (detecting errors/fraud), Association analysis (buying habits).

Office Software Productivity Tasks

• MS Word:

  • Home Ribbon: Clipboard (Cut/Paste), Font (Size/Face), Paragraph (Bullets/Numbers/Alignment).

  • Insert Tab: Cover pages, Tables, Illustrations (Shapes/SmartArt), Hyperlinks, Header/Footer, Symbols/Equations.

  • Design/Layout: Watermarks, Column formatting, Margins.

  • Review/View: Spelling/Grammar, Track Changes, Read Mode vs Print Layout.

• MS Excel:

  • Cells: Identified by address (e.g., A1).

  • Formulas: Built-in functions like =SUM(range), =AVERAGE(), =MIN(), =MAX().

  • Data Management: Basic and Custom sorting, Filtering, Charts (Column/Pie).

• MS Access:

  • Architecture: Designing Tables (fields/data types), creating Forms for entry, generating Reports.

  • SQL: SELECT * FROM table_name WHERE criteria.

• Web Development:

  • HTML Structure: <head>, <body>, <h1> (headers), <p> (paragraphs).

  • Tag Types: Block (new line) vs Inline (same flow).

  • Dreamweaver: WYSIWYG editor. Views: Design, Code, Split, Live, Live Code.