Computer System Memory

• human brain is super intelligent and amazing organ. it helps us do all the calculations, make decision. control all other organs of the body. store and retrieve information.

• human brain can stor information in the brain cells in different parts of our brain and we can also retrieve this information depending upon how that information is stored in our brain.

• human brains has both short term and long term memory and information is stored accordingly.

• A computer system too has memory where data can be stored and retrieved whenever required.

• A computer system can execute any program and process data only when the program and data is loaded in to the main system memory from a secondary memory.

• as per medical science, it seems that our memory is not located in one particular place in the brain, but our memory is instead a brain-wide process in which several different areas of the brain act in conjuction（共同行动） with one another(sometimes referred to as distributed procssing)

• human brain has different types of memory and each has their own particular mode of operation, but as a memory system they all cooperate in the process of memorization and can be ssen as three necessary steps in forming a lasting memory(permanent Memory).

• A computer memory is similar to a human brain. it is used to store both data and instructions(program). A computer memory is the storage space in computer where the data to be processed and intructions(program) required for processing the data are stored.

• Computer system makes the use of different types of memories with differ in capacity, access speed, physical size and the cost of the memory. each of this memory is optimally used in computer system depending upon its access speed, size and proximity((时间或空间) 接近) to the CPU.

• the memory is divided into large number of small parts called cells(1 Cell = 8 bits = 1byte). Each memory loacation or cell has a unique address which varies from zero to memory size minus one.
• for example if computer has 64kb words, then this memory unit has 64*1025 = 65536 bytes cells/ memory locations. the address of these location varies from 0 to 65535(즉 0에서 65535까지의 메모리를 할당하고 있다. 64kb로 된 단어는)

• hierarchy : 계급

why computer needs different types / levels of memories?

• the CPU is also alternately referred to as a processor. the CPU is the most important component in a computer system

• A computer’s CPU handles all insturctions it recieves from hardware and software running on the computer

Binary Code and ASCII

• the computers can understand only binary representation expressed using only 0 and 1. therefore all the characters that we use in text files such as characters, numeric and special symbols must have corresponding representation in the binary.

• however, initially there was no uniformity in the binary representation and the standardisation became necessity only when people started transferring data between the computers. this transfer of data can takce place only if two computers follow the same binary representation protocol.

• the computers can communicate with each otehr and share data only if they follow the same binary representation of the data
  • ASCII standard was introduced with objective to introduce a uniform standard
  • ASCII (American standard code for Infromation Interchange) is the most common format for text files in computers and on the internet.

• ASCII pronounced as “ask-key” stands for the American standard code for Infromation Interchange and was proposed by ASA(American standard Association) in 1963 and was finalised in 1968.

• in an ASCII file, each alphabetic, numeric, or special character is represented with a 7-binary number(a string of seven 0s or 1s). thereforem we can have only 128 possible characters that are defined in ASCII.

• the 7bits allow the computer to encode a total of 128 characters for the numbers 0-9, uppercase and lowercase letters A-Z and a few punctuation symbols. however, this 128 character code is suitable for only English language speaking users and there was no standard available for other languages. by now, the computers had spread across the world and extension of the existing ASCII standard was necessity.

• In order to extend the ASCII code, IBM and Apple expanded the amount of space reserved for the charter codes to 8-bits from existing 7-bit ASCII standard.

• this was done to enable the people to use the computer system in their own language. so they extended the 128 character limit of ASCII to 256 and used the members of the alst 127 number block(127-255) to reprensted the extra character that they needed.

Binary Code

• a modern-day computers are ‘digital machines’ and computer hardware has been designed to handle and process the data only in digital form. every computer system has a microprocessor(CPU - Central processing unit) which acts as brain of computer system. the processor is the main component in a computer system which does all arithmetic(算术) calculations and take logical decisions.

• the CPU is made-up of millions of tiny components called transistor which are fundamental building block of all digital circuits inside the processor chip.

• the transisotrs are made up of silicon which is a semiconductor material that can conduct electricity under some conditions but not others, making it a good medium for the control of electrical current.

• the transisotrs inside the processor ship function as micro switch which can be programmed to be switched on OR switched off. these two states can be easily represented by using binary numbering system which uses only two numbers 0 and 1

• each microprocessors chip is pre-programmed with instruction set which can intepret program instructions in binary machine code to perform various arithmetic calculations and logical decisions making operations.

• the term “binary” implies “two.”. thus, the binary number system is a system of numbers based on two possible digits 0 and 1. this is where the string of binary digits come in. each binary digit, or “bit”, is a single 0 or 1, which directly corresponds to a single “switch” in a circuit.

• therefore, binary number system makes a ideal choice for all computer applications and all the program instruction no matter in which language we write, first must me translated in machines code instructions in binary code(0 and 1)

• the computer can interpret and execute program instructions only in machine code represented using binary code. the cpu is the main component which performs all arithmetic calculations and takes logical decision.

• in digital electronics, seven types of logic gates are used for decition making. the logic gates inside the processore are also constructed using transistors.

• the computer stores all information in binary digital form, which means all data be it text, photographs, audio, video or whatever else is comprised of only collections of ones and zeros.

• the fundamental builiding block of digital information is the binary digit or bit, which represents a single 0 (zero) or 1 (one) state.

• all the program code and the data must be represented in the binary form which can be operated upon by the processor and the result of this operation can be sent to either output device(monitor, printer etc) or it can be stored in a permanent storage device.

• A bit is also sometimes called a flag: this term is most often heard when a bit is used by itself to represent a particular information state. these “flags” are ofen used in networking message formats.

• the term character is also used to express a set of eight bits. this use comes from the fact that computers often store alphanumeric characters.

Binary Units

• a bit is considered as smallest unit in computers. 8 bits = 1 byte and 1 bye = 1 character.

• one bye represents one character such as A, 7, 9 and eight bits that are grouped togeter as a unit(byte)

• a byte provides enough different combination of 0s and 1s to represent individual characters. for example, the capital letter F is represented by the binary code 01000110 this can be undetstood by the computer system.

Binary code and Logic Gates

• the logic gates are elementary builidng blocks used in digital electronics to perform logical operations by operating on one or more boolean inputs and produce single binary output.

• the logic gates operate via tiny hardware component known as a digital switch. in the days of room-size computers, the switches were actually physical siwtches, but the most common type of switch in today’s computers is a transisot known as a MOSFET(Metal-oxide Semiconductor field-effect transisotr)

• logic gates are pieces of hardware that perforam logical operations on the boolean inputs, allowing us to create complext devices using abstract boolean algebra.

• logic gates are the fundamental building blocks of hardware and computer processors are made up of billion of tiny logic gates.

• A logic gate generally has one or two inputs and only one output as a result of the logical operation.

• all processors work on the same principle. fundamentally they all take signals in the form of 0s and 1s(thus binary signals), manipulate(控制) them according to a set of program instruction and produce output in the form of 0s and 1s.

• the processor works by reacting to an input of 0s and 1s in specific manner and then returning to an input of 0s and 1s in specific manner and then returning an output based on the decision. the decision itself happens in a circuit called a logic gate, each of which requires at least one transisotr, with the input and outputs arranged differently for different operation.

Boolean algebra

• in mathematics and mathematical logic, boolean algebra is the branch of algebra in which the values of the variable are the truth values (true and false) and this is usally denoted in binary 1 and 0 respectively

• Boolean algebra was introduced by George boole in 1854 who was a British mathmatican. Boolean algebra has been fundamental in the developement of digital electornics.

• in algebra we make use of decimal numbers, whereas the boolean algebra uses truth values, true (1) and false(0).

• A logic gate is a tiny circuit used in processors for making a logical decision which is based on boolean algebra. boolean algebra is used to analyze and simplify the digital(logic) circuits. it uses only the binary numbers i.e. 0 and 1. it is also called as binary algebra or logical algebra.

• A logic gate is a physical device that perform as logical operation on one or more logical inputs and produces a only one logical output.

• the input is the signal or data that fed into a logic gate whereas the output is the result from processing the inputs by using the operation of the logic gate.

• the input and output can be either high(denoted by 1) Or low(denoted by 0)

• logic gates are identified by their functions. there are five basic logic gates that are extensively used inside the computer processor.

Introduction

• Heaps are a subdivision of Trees with a few rules. These rules, just like with Stacks and Queues, give these data structures many essential roles.

Why is it Important?

• Heaps are used for a variety of applications. They can act as priority queues, help with graph traversals, and provide a data structure that makes finding the extreme value O(1) time

Lesson Notes

• Heaps in essence are just stricter trees. They have all the same properties of trees, with the additional “Heap Property” rule added.

• The heap property is a rule which gives a relationship between the parent and child nodes within a tree. It states that the parent node must always be either greater, or less than its children. If it has to be greater, then it is a max heap, if less, a min heap.

• This property propagates throughout the tree. Since every parent has to be greater or less than, the root, or the top of the tree, must be the greatest/least

• The simplest heap is the binary heap. This is a heap in which each node of the heap has only two children and must maintain a complete tree pattern

• A complete tree is a tree which every level, expect the last, is filled, and all nodes are as far left as possible.

• This is an example of a complete tree. Notice how it’s completely filled, and the last level fills from left to right.

• This is an example of a tree which isn’t complete. The F should be shifted as a left child of C to make this complete

• Due to the structure of a heap, most of the run times are logn, as it only takes the height of the tree to get to any given node. We have previously learned that trees are built in a structure that lends this height to be equal to logn time.

Run time

• Insert: O(logn)
• Delete: O(logn)
• GetMin: O(1)

Heap Example

Applications

• Heaps are great for priority queues, as the most “important” task will always be at the top, and really fast to retrieve. They are also used in more complex algorithms like Dijkstra’s Shortest Path Algorithm.