Notes of Crash Course Computer Science

Posted on Edited on In

Notes of crash course computer science.

History of Computer

Non-electrical Computer

  • People “Computer”
  • Step Reckoner (步进计算机): first mechanical computer using gear
  • Pre-computed Table: used for looking up pre-computed results
  • Difference Engine, Analytical Engine: could do calculation and some operations, more general
  • Tabulating Machine: electro-mechanical computer, using traditional mechanical system for keeping count and couped them with electrically-powered components

Electrical Computer

  • Harvard Mark I: electro-mechanical computer, using relays (electrically-controlled mechanical switch) to control, motor to trigger gears to count
  • Colossus: replace relay with vacuum tubes, faster calculation
  • IBM 608: replace vacuum tubes with transistors

Computer Basic Components

  • ALU: Arithmetic and Logic Unit
    • Takes in binary numbers
    • Control input determines which calculations to perform
      • Add / Sub, Plus 1
      • NOT, ADD, OR
    • Output result and calculation and flags
      • Is overflow
      • Is equaled to 0
      • Is negative
  • Register: small, linear chunks of memory, could store a single value
  • RAM: a large bank of memory storing a lot of numbers located at different address

CPU

  • CPU: Central Compute Unit
    • Consists of ALU, Register, CLOCK
    • Handle Instruction
      • Read / Write data from / to RAM
      • Perform calculation
    • Instruction handle cycle
      • Fetch: fetch instruction code from RAM to instruction register
      • Decode: analysis the instruction code based on logic gates, then
        • Enable address wire and respective data register for read/write instruction
        • Pass data and operation code to ALU
      • Execute:
        • Enable read / write of RAM, disable them later
        • Store ALU result to temporary register, disable ALU
        • Add 1 to the value of Instruction Address Register, ready to retch next instruction code
  • CPU communicates with RAM through address wire, data wire, and enable wires
  • To make the data transmission faster
    • Create a CACHE in CPU, read a block of data from RAM at 1 time, write data into CACHE temporarily, use the Dirty Bit to really write data to RAM
    • Build the pipeline to optimize the instruction handle cycle. e.g. the second instruction’s fetch phrase is performed at the same time of first instruction’s decode phrase

Programming

  • Von Neumann Architecture
    • a processing unit containing an arithmetic logic unit
    • data registers
    • instruction register
    • instruction address register
    • a memory to store both data and instructions
  • Stored-program computer: Von Neumann architecture programable computer, could store program into memory, insert program and data using punched cards, plug board or switches

History of Programming Languages

  • Machine code: consists of binary 0 and 1, the native language that machine can understand
  • Assembly Language: opcodes are given simple names, called mnemonics, following by operands, form instruction. The instruction will be translated into machine code by assembler later, which is written in machine code
  • A-0, FORTRAN: compiler translates the programs into native machine code
  • COBOL: a general programming language could run in different computers, each computer should implement their own compiler
  • C, C++, Java, Python, etc

Operation System

  • A special software, help programmers to run program easily
  • Play as intermediaries between software programs and hardware peripherals, provide software abstraction through APIs, called device drivers
  • Support multitask, allow CPU to execute different programs “at the same time”
  • Map physical memory address to virtual memory address (always starting from 0)
  • Protected memory, allows the program to only run in a specific memory

History of Operation System

  • Atlas system: multitask OS, allow CPU to run different tasks, has virtual and protected memory
  • Multics: support multi-user to login
  • Unix
    • kernel (core functionality, memory management, multitasking, dealing with OS)
    • non-kernel (useful tools, programs, libraries)

Storage

  • Punch cards
  • Delay line memory: can only sequence read
  • Magnetic core memory: support random read, but still expensive
  • Tape: cheap, sequence read
  • Hard disk: surface is magnetic
  • Solid State Drives: SSD, no moving part, integrated circuit

Computer Interaction Interface

  • Input: gears, panels of mechanical controls and patch wires, punch cards; Output: paper with holes
  • Input: keyboards, command line interaction; Output: print to paper (for computation results), screen (for temporary values)
  • Mouse, Graphical User Interface (GUI, with concept of desktop): Macintosh, Windows 95

Graphics

  • Wireframe Rendering
    • Represents 3d Object in 2d screen
      • orthological projection
      • perspective projection
    • Polygons (Triangles): a collections of polygons is called mesh, representing a 3d object
  • Scanline Rendering: scan the pixel row from top to down, fill the pixel between the 2 interactions pixel point between pixel row and triangle edges
  • Antialiasing: make the pixels passed by triangle edges change color gradually
  • Occlusion: according to the depth of triangle, determine which part is in front
  • Lighting: determine each triangle’s lighting level based on the position of light and its direction
  • Texturing: map texture image to triangle

Network

Kinds of Network

  • LAN (Local Area Network): 2 connected computers in a room, several computers computers in campus
    • Ethernet
      • Computer connects with cables; computer talk with each other through cables
      • Each computer has a MAC (Media Access Control) address to represent itself; the receiver’s MAC address will be placed at the beginning of data sent by another computer
      • Exponential backoff: to solve the data collision issue in LAN
      • Switch: divide collision domain to several sub-domains, only connect sub-domains when there is a transmission required to go into other another domain, reducing the probability of data collision
    • Wifi
      • Similar to Ethernet, but carrier is air instead of cables
      • Devices connecting with the same home Wifi are in the same LAN
  • WAN (Wide Area Network), larger scale connected network to connect small LAN together
    • Use router to connect LAN, router is run by ISP (Internet Service Provider)
    • Regional router in a WAN could cover an area of users (LANs), then regional router will go into larger WAN, finally connect into the backbone of Internet, which made up with gigantic routers

Data Transmission

  • Routing
    • Data transmit in the network through node by node, each node records the destination and which node to go next to reach the destination
    • Hop count: how many routers data have passed. could use traceroute command
  • IP (Internet Protocol): transmitting data will be divided into small packets, each packet has the destination IP
  • Port: every program in a computer needs to listen to a port to receive message from network
  • Construction of a data in network
    • IP header
    • Protocol header
      • UDP (User Datagram Protocol) header: port number, checksum
      • TCP (Transmission Control Protocol) header: port number, checksum, sequence number
    • Data
  • DNS (Domain Name System)
    • Computer will check with DNS Server to loop up IP address of a domain (characters)
    • DNS server is provided by ISP

World Wide Net

  • Fundamentals is a single page containing text
  • Hypertext is a kind of text supporting hyperlink
  • URL (Uniform Resource Locator): the unique address of a web. e.g. domain.com/about
  • HTTP (Hypertext Transfer Protocol): commands to retrieve specific page from server. e.g. GET /page, will get response data with status code. e.g. 200 means response successfully
  • HTML (Hypertext Markup Language): parsed by web browser, rendering content