Midterm Study Guide

Chapter 1What is Computing

The big idea

A computing system has three parts:

• Hardware is the physical stuff you can touch.
• Software is the programs that tell the computer what to do.
• Data is the information the computer works with.

Abstraction means hiding the complicated details. You drive a car without knowing how the engine works.

Layers of a computer, inside to outside

1. Information
2. Hardware
3. Programming
4. Operating system
5. Applications
6. Communications

Famous people

Generations

Two kinds of programmers

• Systems programmers build the tools.
• Application programmers use the tools.

Four skills of computing

Algorithmic thinking, representation, programming, and design.

Chapter 2Data Representation

Which digits each base uses

A number can't use a digit as big as its base. So 178 is not base 8, because it has an 8.

Binary to decimal

Write these place values over the bits, right to left. Add up the places that have a 1.

Example: 10010 has 1s in the 16 place and the 2 place. 16 + 2 = 18.

Decimal to binary

1. Divide the number by 2.
2. Write down the remainder (0 or 1).
3. Divide the answer by 2 again. Keep going until you reach 0.
4. Read the remainders from bottom to top.

Bottom to top: 41 = 101001.

Binary to hex, and hex to decimal

• Binary to hex: split the bits into groups of 4 from the right. 1101 1100 is D C, so DC.
• Hex to decimal: left digit × 16, plus the right digit. 2F = 2 × 16 + 15 = 47.

How many things bits can show

• n bits can show 2ⁿ different things. 3 bits = 8, 4 bits = 16, 8 bits = 256.
• Adding one bit doubles it. 8 bits = 1 byte.

Analog and digital

• Analog is smooth and continuous, like a mercury thermometer.
• Digital is split into separate pieces.

Text

Compression

• Lossless keeps everything. Lossy throws some detail away.
• Keyword encoding swaps common words for a symbol.
• Run-length encoding writes a repeat as flag, letter, count. qqqqqq becomes *q6. Don't bother for 2 or 3 repeats.
• Huffman encoding gives common letters short codes. No code is the start of another code.

Sound, pictures and video

• Sound is saved by sampling (measuring often) and quantization (storing each measurement as a number).
• A color is three numbers for red, green and blue, each 0 to 255. (255, 255, 0) is yellow.
• Raster images are made of pixels (JPEG, PNG). Vector images are made of shapes (SVG).
• Video uses temporal compression (only save what changed between frames) and spatial compression (squeeze each frame).

Chapter 3Computer Components

Gates are built from transistors

• A transistor is a tiny switch with no moving parts.
• Depending on the input voltage, it either lets electricity through (like a wire) or blocks it (like a resistor).
• It is made of a semiconductor, which is neither a good conductor nor a good insulator.

How it stacks up:

1. A few transistors make one logic gate.
2. Millions of gates make one integrated circuit (chip), with billions of transistors.
3. Tens or hundreds of chips sit on the motherboard.

From the textbook: a NOT gate uses 1 transistor, NAND and NOR use 2, AND and OR use 3.

A gate does one basic job on electrical signals. A circuit is several gates joined together. The most important chip is the CPU.

The gates

• NOT flips the input. 1 becomes 0, 0 becomes 1.
• AND gives 1 only if both inputs are 1.
• OR gives 1 if at least one input is 1.
• XOR gives 1 if the inputs are different.
• NAND is the opposite of AND. NOR is the opposite of OR.

OR and XOR only differ on the last row, when both inputs are 1. You can describe a gate three ways: a Boolean expression, a logic diagram, or a truth table.

Parts of the computer (von Neumann)

• ALU + control unit = CPU.
• PC (program counter) holds the address of the next instruction.
• IR (instruction register) holds the instruction running now.
• Registers are tiny, super fast storage inside the CPU.
• A 3.2 GHz CPU ticks 3.2 billion times a second.

Fetch-execute cycle

1. Fetch the next instruction.
2. Decode it.
3. Get data if needed.
4. Execute it.

Then it starts again, which is why it's called a cycle.

Memory

• RAM can be read and changed. It is volatile, so it is wiped when the power goes off.
• ROM can only be read. It keeps its data.
• Secondary storage keeps data for good: hard disk, SSD, USB drive, CD.

Embedded systems

A small computer built into something bigger to do one job. Examples: computers in cars, phones and medical equipment.

Chapter 4Operating Systems

What an OS does

• Application software does a job for you, like a word processor.
• System software runs the computer itself. The OS is system software.

The OS has three jobs:

1. Manage resources like memory and devices.
2. Give you a way to use the computer.
3. Let programs use the computer's resources.

Key words

Addresses

• A logical address is where something is inside the program.
• A physical address is where it really is in memory.

Partitions

• Fixed partitions split memory into set pieces. Dynamic partitions are made as needed.
• The base register holds where the partition starts. The bounds register holds how long it is.

Picking a block

• First fit: the first block that is big enough.
• Best fit: the smallest block that is big enough.
• Worst fit: the biggest block.

Slide example. Blocks: A 1000, B 700, C 750, D 1500, E 300, F 350.

Process states

1. New: being created.
2. Ready: waiting for its turn on the CPU.
3. Running: using the CPU right now.
4. Waiting: waiting for something else, like a file or the printer.
5. Terminated: finished.

Lots of processes can be ready or waiting. Only one can be running.

Scheduling

• Nonpreemptive: the process gives up the CPU by itself.
• Preemptive: the OS takes the CPU away.
• Turnaround time: from when a process first shows up to when it finishes.

Average turnaround

Add up when each process finishes, then divide by how many there are. Example: P1 = 50, P2 = 20, P3 = 30.

• FCFS runs P1, P2, P3. They finish at 50, 70, 100. Average = 220 ÷ 3 = 73.33.
• SJN runs P2, P3, P1. They finish at 20, 50, 100. Average = 170 ÷ 3 = 56.67.

Chapter 5Networks and Internet

Key words

Two ways to set up a network

• Client-server: one main server, everyone asks it. Easy to manage, but if the server goes down, everyone is stuck.
• Peer-to-peer: every computer is equal and shares directly. No single point of failure, but harder to keep secure.

Sizes of networks

• LAN: a small area, like one building.
• MAN: a whole city.
• WAN: connects LANs far apart.
• Internet: a WAN that covers the whole planet.

Packet switching

A message is cut into small numbered packets. Each packet travels on its own. They are put back together at the end.

Protocols to know

The OSI model has 7 layers. A firewall filters traffic to protect a network.

Addresses

• A hostname is a name with dots, like www.imamu.edu.sa.
• An IPv4 address is 4 bytes (32 bits). They ran out in 2011.
• An IPv6 address is 128 bits.
• DNS turns a hostname into an IP address.
• The TLD is the last part of the name, like .com or .sa.

The Web

• The Internet is the network. The Web is the pages and software that run on it. They are not the same.
• A browser gets and shows pages. A web server sends them. A URL is the address of a page.
• A cookie is a small text file a website saves on your computer. It is not dangerous.

HTML, CSS and XML

• HTML builds the page using tags like <body> and </body>.
• <head> holds info about the page. <body> holds what you see.
• CSS decides how it looks.
• XML describes what the data means, and lets you make your own tags.

Cloud and blockchain

• Cloud computing: rent computing power and storage over the Internet and pay for what you use (AWS, Google Cloud, Azure).
• Blockchain: a shared record of transactions that no single person controls.