2nd Test Prep

Hello, I hope everyone did well on the test. I am sure some people found it difficult and others probably found it the easiest thing they have ever written. I found there were a lot more word questions than the last one and noticed it was weighted half of the test. Anyway, I know this is a bit late in case some people needed study notes, but I decided to post my study notes so others can compare with theirs and hopefully there are some things to add to their list before going into the final exam (which is actually a month away!)

**Notice when I wrote the Lecture numbers, I meant the lectures starting from the last test date. (Starting with Algorithm)

Lecture 1

Algorithms

·         Al-Khwarizmi – A Persian mathematician, astronomer, and geographer. He is considered one of the inventor of algebra, as his solution of linear and quadratic equations done in Arabic was discovered in twelfth century.

·         Greatest Common Divisor (GCD) = the largest whole number that divides two non-negative whole numbers

·         So GCD(12, 20) = 4

·         Euclid’s algorithm = GCD(48,18) => Divide 48 by 18 to get 2 with remainder of 12 => 18 divide by 12 to get 1 with remainder of 6 => 12 divided by 6 to get 2 with remainder of 0

·         So, GCD (a, b) = GCD (b, remainder of a/b)

Lecture 2

·         If there are two or more algorithms solving the same problem, then you have to choose the one that is more efficient

·         There obviously isn’t an algorithm that solves every problem

·         Halting problem = problem of deciding whether when given a program and an input, that the program will run forever or eventually halt

·         Alan Turing proved in 1936 that there cannot exist a general algorithm to solve the halting problem for all possible program-input pairs

How to solve a new problem

·         Understand the problem – what’s required, what’s given, solver-name: input -> output, draw pictures

·         Devise Plan(s) – different types of searches

·         Try the plan

·         Look back and analyze what went wrong if the plan doesn’t work

Lecture 3

Von Neumann Architecture

·         Memory-mapped I/O = allows input and output devices to be treated the same as memory

·         System bus = a single computer bus (a subsystem that transfer data between components inside a computer/between computers) that connects the major components of a computer system. This will reduce costs and improve modularity.

·         => It becomes the following components

·         1: Data bus = to carry information

·         2: Address bus = determine where it should be sent

·         3: Control bus = determine its operation

Von Neumann Bottleneck

·         Shared bus between the program memory and data memory leads to bottleneck

·         The limited throughput (data transfer rate) between the CPU and memory compared to the amount of memory

·         Because the program memory and data memory cannot be accessed at the same time, the throughput is much smaller than the rate at which the CPU can work, which would affect the processing speed when the CPU is required to perform minimal processing on large amounts of data

·         Thus the CPU is continuously forced to wait for needed data to be transferred to or from memory

Moore’s Law

·         Observation that over the history of computing hardware, the number of transistors on integrated circuits doubles approximately every two years.

Input, Output

Storage (Data storage device)

·         A device for recording (storing) information (data).

Hard drive

·         Capacity is specified in unit prefixes corresponding to power of 1000 (So 1-terabye (TB) = 1000 gigabyte (GB)) and not all of it is available to the user due to use by the file system

·         Performance is specified by the time to move the heads to a file plus the time it takes for the file to move under its head and the speed at which the file is transmitted

Compact Disc (CD)

·         Used to store digital data

·         CD data is represented as tiny indentations known as ‘pits’, encoded in a spiral track moulded into the top of the polycarbonate layer

·         CD is read by focusing a laser through the bottom of the polycarbonate layer. The change in height between pits and lands results in a difference n the way light is reflected. By measuring the intensity change with a photodiode, the data can be read from the disc.

Flash Drive

·         A flash drive does not contain any moving parts (except for electrons) , they are very robust mechanically

·         Information stored in electron chamber

·         Compare to hard drives, flash drives use little power, have no fragile moving parts, and very light and small

·         Resistant to mechanical shock, magnetic fields, scratches, and dust.

·         However, it can only sustain limited number of rewrites before the drive fails.

·         Flash memory places RAM

Lecture 4

·         Sharing big computers with smaller computers

·         There were a lot of computers that were dedicated to one job, however as time passed, the new revolution has come where you can stop one task and start another.

An operating system should have:

1)      Kernel = main component of operating systems, and acts as a bridge between application and the actual data processing done at the hardware level. It’s responsibilities include managing the system’s resources

2)       Utilities = repair and maintain machine

ROT13

·         The 26 alphabet is split into first 13 and last 13. Then in order, the first alphabet corresponds to the first in the second batch.

·         ABCDEFGHIJKLM

·         NOPQRSTUVWXYZ

Lecture 5

Network Topology

Topological structure of a network, and may be depicted physically or logically. The shape of the cabling layout used to link devices is called physical topology and logical topology shows how data flows within a network.

Bus

·         In local area networks, bus topology is used, where each node is connected to a single cable

·         Each computer/server is connected to the single bus cable

·         A signal from the source travels in both directions until it finds the intended recipient, and then the data is accepted.

·         All machines can transmit signal at any given time

·         If another machine is transmitting at the same time, then it waits for a random interval of time before re-transmitting them.

·         Since it consists of only one wire, it is inexpensive to implement but expansive to manage the network

Star

·         Each network host is connected to a central hub, in order to be classified as a star network, all the nodes on the network must be connected to one central device.

·         It is considered easiest topology to design and implement.

·         However, it also means that the hub represents a single point of failure

Ring

·         A network topology that is set up in a circular fashion

·         Signal travels around the ring in one direction and each device grabs the incoming signal and transmits them to next device.

·         The signal travels until the recipient gets the message which will then keep propagating in the ring until the original sender receives it and conclude that the message has been sent

·         The network is dependent on the ability of the signal to travel around the ring