Class Notes (835,600)
Canada (509,275)

COMP SCI 1BA3 - Lecture Notes.doc

29 Pages
Unlock Document

Computer Science
Anthony Hurst

COMPUTER SCIENCE FINAL EXAM Homunculus – a very small man; midget or dwarf, maggot mistaken for a small person by monks. Anthropomorphism – referring to something inhuman as human. Ex. She’s a beauty referring to a car Autokinetic – means self-moving Automaton – Independent; acting of one’s self; run’s itself. Vaucanson’s mechanical duck; the duck was able to eat, splash, quack and eliminate food; could do what a duck could do. Computer History 500 B.C. – The Abacus • Babylonians 1576 – 1626 – de Caus • mechanism to control both the playing of an organ and the movements of model figures 1621 – Slide Rule ; a precursor to the electronic calculator • William Oughtred invented the slide rule by using John Napier’s invention Napier’s Bones 1642 – Blaise Pascal; the Pasacline Arithmetic Machine • Has capacity for 8 digits and can add and subtract, multiply and divide o 1623 Schickard’s Calculator; carry the one by interlocking gears o 1673 Leibniz Calculator; German Gottfried Wilhelm von Leibniz improved Pascal’s calculator; differential calculus o 1820 de Colmar’s Arithmometer; became the first mass produced calculator • All the calculators operated under manual power by turning a crank or pulling a lever 1804 – Joseph-Marie Jacquard; Jacquard`s Loom • Introduced punch cards for weaving; made replicas 1822 – Charles Babbage; the Difference Engine • Wasn’t able to create a working version • Mill = processor or CPU and Store = memory 1834 Charles Babbage; the Analytical Engine • Wasn’t completed its design embodies many of the concepts that define the modern computer, including memory, a programmable processor, an output device, and user- definable input of programs and data 1842 Ada Lovelace • Known as the first computer programmer ; comp should do more than one task • assisted Babbage with his development of the Difference Engine and the Analytical Engine 1854 George Boole - Boolean algebra; Truth tables • Introduced truth system (ones and zeros • NOT, AND, OR • Wrote about the Laws of human Thought 1877 Herman Hollerith; Hollerith Tabulating Machine • Card reader with tally; electrical sensors to read cards 1911 C-T-R Company • Merger of Computing Scale of America, Tabulating Machine Co., International Time Recording Co. 1936 Claude Shannon • Realized Boole`s machine could be used with electric circuits; Logic gates 1937 Alan Turing; Turing Machine • Defined what it means to be computable; “On Computable Number” is his paper • Turing machine was an idea • Head – little unit that interfaced with equipment (R/W Head) • Turing test  3 separate room test 1937 Howard Aiken • Proposed connecting 78 adding machines 1939 John Atanasoff & Clifford Berry; Atanasoff-Berry Computer (ABC) • ABC used vacuum tube computer for solving equations st • 1 known electronic digital calculating device 1941 Konrad Zuse; Z3 • a mechanical relay calculator which was switch based; Used binary numbers 1943 Alan Turing - • Code breaking at Bletchley Park, using the COLOSSUS(WWII), thought to be 1 st electronic computer 1943 COLOSSUS • Created by a team of British developers • An electronic device designed to decode messages encrypted by the German ENIGMA machine 1944 Howard Aiken; Harvard Mark I • IBM’s first American general-purpose computer; beginning of the digital computer age 1943 ENIAC (Electronic Numerical Integrator and Computer) • First general purpose computer • Different programs run with ease 1945 John von Neumann • Outlined critical elements of a computer system (general computers) 1946 Presper Eckert and John Mauchly • Vacuum tube computer 1947 John Bardeen, Walter Brattain, William Shockley invented transistor • Transistor has same capabilities of vacuum tube but was faster, broke less often, used less power, and created less heat 1948 Norbert Weiner • Cybernetics 1949 Maurice Vincent Wilkes • EDSAC, first practical stored program 1951 Sperry-Rand UNIVAC - • UNIVAC I; 1 commercially successful digital computer 1951 First Business Computer 1952 John von Neumann • detailed prototype for most future serial computers and stored program concept • Made the JONIAC or JOHNIAC? 1954 Claude Shannon • Adapts transistors to perform logic operations 1957 FORTRAN • FORTRAN programming language was introduced 1960 PDP-1 • First minicomputer 1960 Grace Hopper; COBOL • COBOL programming language; BUG 1964 Doug Engelbart • The first mouse 1965 IBM 360 • Advent of third generation computers 1965 DEC PDP-8 • First commercially successful minicomputer 1967 Floppy Disk 1968 Intel Corp • Robert Noyce and Gordon Moore founded the Intel Corporation 1969 – IBM • Unbundled some of its hardware and software and began selling them separately allowing other software companies to emerge 1969 – UNIX • Developed at Bell Labs; Advanced Micro Devices AMD was formed 1969 – ARPANET (predecessor of today’s internet) was established 71 – first microprocessor 72 – C-programming language 75 – first electronic business program 1976 Ethernet Technology • Concept at first • Hook computers up to talk to each other • Originally through phone lines • Rand at 300 bod (rate of transfer speed) • The military picked up on it 1989 – Tim Berners-Lee – invented WWW 1995 – Java 2000 – USB ------------------------------------------------------------------------------------------------------------------------------- Terms: Prototype – an experimental device that must be further developed and perfected before going into production and becoming widely available First generation computers can be characterized by their use of vacuum tubes, by custom application programs. Second generation computers used transistors instead of vacuum tubes. Transistors are smaller, cheaper, use less heat than vacuum tubes. Third generation computers became possible in 1958 when Jack Kilby developed integrated circuits. First computers with the circuits are RCA Spectra 70 and IBM 360. Fourth generation computers appeared in 1971 when Ted Hoff developed the first general purpose microprocessor. Called the Intel 4004, the microprocessor dramatically changed the computer industry. Multi-tasking or Concurrency - running more than one program at a time Archive – contain files which have accumulated over a period of time Mirror Site – alternative site that does the same thing as another site Co-Axial – two wires are inside of another wire (they share a common axis) FTP – File transfer program HUB – run from Rutgers to u of T to Stelco to U of Guelph Inverter – inverse of the input Convergence – two or more technologies merge into one Digital computer – specific set of states(precise) many changes of states when starting up a computer; only 2 states (0 – no current, 1- a little current) Analog Signal – temp. – infinite # of states General Purpose Computer – may be applied to do many different things; we can program it, store a program, & use it, then store another program. it can do different things (the comps we use) Computation – the processing of symbols. Calculation is a subset of computation Intractable (very very hard) problem – unsolved Algorithm – solution to a problem (steps that accomplish a task = processing) the carry – having to move to the next column – the sum gets bigger than the next column that you’re adding overflow(depends on how much memory) – finite #s Binary - can only have quantities of 1 or none. 1 of 2 to base 0 1 0 = 2 1 1 1010 = 10 in the denary system 3 2 1 0 1 1 = 3 + 1 1 2 2 2 2 1 0 + 1 1 1 1101 0100 - 8 bits is a byte.. kilobyte is 1024 because - 10 2 nybble - half of a byte Denary (meaning 10 symbols) - number system we use powers of base 10. 10 symbols - representing quantities 9 + 1 = 10 Hexadecimal - based on 16 symbols in the alphabet of symbols Octal - 8 symbols Transistor - debounces the switch; close the switch more reliably IMPORTANT ADVANCEDMENTS integrated circuits - helped advance minicomputers PdP 8 was the first comp to be interconnected with other comp thru ethernet port is where you connect the cable development of ethernet - concept at first - idea was to hook comps up so they could talk to eachother. originally done thru phone line. allowed programs to be transferred from one comp to another thru wires instead of on a disk ether pt of ethernet came about bc the inventers idea said it came out of the comp and into the ether (air) like magic ethernet concept grew and grew until the military used it to stay connected. WhiteSands mistle base, set up huge site called and ARCHIVE then they created mirror site-meant alternative site. Archive net - major beginning or the World Wide Web or the internet. Arpanet allowed ppl to exchange files. Educational use followed. Technical bulletins were hard to get a hold of. HUBs - the info had to go thru these hubs. the Bang path- the ! symbol was the bang symbol and was used to distinguish which comp it was going to/ coming from. when the institutions joined thats when it began to be called the internet. Primarily the North American unis and the military in the states. It was character driven not graphically Driven. Cern- site of linear accelerator for accelerating atomic particles. Bernius lee.. invented HTML behind the webpages we see now. Various codes or mark-up lang that told the comp how to display graphic display. relied on guy interfaces. Xerox had developped one. DATABASE INFO Open Office - Calc • Use spreadsheets for what-if scenarios. You plug in different numbers, what if, quickly compare outcomes depending on what numbers you input • 3 differences with Calc and Excel: o CHOOSE function o # in calc must be 1 or more o Paste-special  get a window that comes up  do you want to paste the formulae or do you want to paste the values?  in this case you would paste the value because you don’t need the formula anymore • delimiter - a file with a .csv tail stands for comma separated values. (comma - does not need to be a comma, could be a space, tab etc.) • transpose - rows into columns and vice-versa Database • Normalization o Design process • Design: an ongoing process • work your way from a starting point and eventually get to a point in the design process where you get a prototype that you can use to see flaws, then you go back and edit those • Use it to review your design to make adjustments to your prototype • Database - product of using a database management system(software that allows you to create a database but does not help you design it); collection of data stored and organized in a specific way. Specifics are base on the designs of your database • Several design methodologies o Generally go through the cycle • Classic problem is CONSISTENCY. o Integrity - means whether the data is consistent (may be retrieved easily and accurately) • KEY - in a database allows you to uniquely identify a particular reference. If you don’t tell them not to, they will create a key for you • database management systems are transparent o transparent normally means that you don’t have to worry about the storage (physical) details/ locations o Sequential access method (SAM)  Looking for a word in the dictionary and have to go through every single page to find a word o Direct access method (DAM)  Little pieces of information that act like a lookup table or an index  What we use today  disk drives and usb drives make use of this technology  You skip to that section and then you start looking sequentially • Relational database design o Founded upon the concept of relationships among the data (i.e. name & phone number) o structured to mimic the rel’p. books -titles and authors. book was writen by authors. authors wrote the book. VERB is the rel’p • Why not use a spreadsheet? o Not good with text and not good with this relationship aspect Database types • Flat file system aka multi file system o distinguishing characteristic: it was not one file o Redundant data = having same name over several files o Make several changes for one person i.e. update two files manually o Everything is one dimension; older style & error prone o 3 problems  redundant – wasted space  Access method is slow (SAM)  Lost updates • Hierarchical structure has a narrowing shape (pyramid) o Top element is the root, branches coming out of the roots (subroots) o Fans out the lower you go in the hierarchy o redundant • PARENT-CHILD REL’PS - important. the key to understanding how you traverse thru the hierarchy • Grandfathering here means two levels removed from the child. (grandfather- father- son- 3 levels) Parent can have many children; Children may only have one parent • Hierarchical systems are really a special case of network systems o Less flexible than network • Network system is similar to hierarchical but child’s can have more than one parent o Connections can go across the tree instead of only up and down o Network has more complexity but it also has more flexibility o More or less simple and straight forward and not as much programming involved • Each of the boxes in a system is referred to as a node • Most of the databases are static that we’ll come across o The information doesn’t change that much • Real time systems o Difficult to deal with o Airline reservation system or a hotel reservation systems o Constantly updating the information and refreshing it all the time o Can’t let people read the info about the occupancy • Relational system o Called that because the underlying fundamental element is a relation o Relation is a structure - looks like a table; going to have rows and columns o Tupple – the row; fundamental(basic) unit for the info o Attributes are the columns o Two dimensional structure o The Relation represents an entity  person, place, time, product, thing o A row or tupple represents an instance of the relation or instance of the table SQL • structured queried language • developed in the days of flat file system dbs • “Select” famous key word… “select from” • used to type in queries • Queries – a way of questioning the database “give me all the data that match this criteria” • Criteria – a filter or a rule of thumb • Key to understanding databases  Truly relational database management system  All operations take a relation as an argument  All results must be a relation  Be represented in the form of relations  Getting it into the database in the form of a relation • Dr. Edgar F. Codd o No 2 database systems were the same, were never alike o Problems and errors crept into databases  Better get some standardized approach o Headed a committee that eventually created a criteria for db o Proposed a new system; -notion of relations consisting of tupples and attributes o Key to understanding relational databases - to be a truly relational database system, all operations that a relation has an argument and the result must be a relation, and all of the design structural elements must be represented in the form of relations. o Logical organization  Logical in a sense of structure means the conceptual nature of the organization; not the actual physical details  Toy means small or compact in computer language o More modern database package that we’ll see that’s designed for the web is MYSQL  Open source product; kind of like open office  People can contribute things like software routines or utilities o ORACLE  hierarchical system  Storing your data somewhere else; not on your system at all • 3 schema architecture – general model now o Conceptual schema  Overall design of the database  Gather up manual pieces of paper and analyze them  Data dictionary is a list of all the data items that you’re going to use in your database; list things like entities and the attributes of those entities • Preliminary document – gathered on paper first then represented in the form of a relation; a table  Describes entities and relationships among entities, describes attributes o UPS - uninterrupted power supply - when the power sags or drops (at the wall socket), the internal power in the computer sags then a 1 becomes a 0 and your data becomes corrupted for times when the power is off. Therefore you need backup supply or uninterrupted power supply o Logical schema  The way in which people would use the database  Call it the user views  Every user is authorized to see a certain subset of the entire data o Physical schema  Actual storage details  Most people don’t need to know anything about it o Two different types of end users  Most common user just needs to INTERACT with the database - view it and maybe make minimal changes/additions  Application programmer • Someone that uses SQL or some programming language  DBA • Database administrator has godlike powers of who gets to see the data, who gets access to protected information, etc • ONLY ONE • Maintains the database, looks for problems, authorizes changes • That conceptual schema must be represented in a table – accounts for several data classes o Operational data – needs to be tracked on a daily basis o Transient data  Helps understand what the data will be used for  Help designer to construct the queries o Summary data  Usually the first major extraction from a database  Tells you the BOTTOM LINE – tells you whether you’re making money  Profit and loss o Managerial data – helps us to understand what our next move will be o Strategic data – make use when company grows  Presentation of strategic data – knowing what to present, what they need to know  Not so much daily operations • Entity is the big object o Each entity is represented in a table, or a tupple • Base tables  ones that are created and stored o At run time we can generate data from existing data • One of most imp. aspects of database is LOGICAL - PHYSICAL INDEPENDENCE o recognize structural aspects w/o physical details; transparent • Database administrator very often closely tied to the nature of the business • Advantages of databases o Consistency  Tighter control over data if using an organized software package  Also known as accuracy and redundancy o Programming interface for specialized need  Developed faster o Query is a question  Create in the form of a program  Flexibility  Extracting info from database o Administration and security  Usually simpler, fewer loose ends • Disadvantages o Security is more complicated o A little more expensive to set up in a large commercial environment o Once you get a lot of data online and get it stored electronically  Tendency to lose paperwork  Little things get lost in the shuffle o Backup and recovery can be very complicated o Companies become dependent on these databases Database Design Process • The list is circular not linear; designer will go thru methodical process o Inventory  Listing the known things and things you would like to know but are unknown at the moment  Means that you are looking at all the paper material and getting from it all its attributes  Taking stock on info and trying to organize in a sensible manner its preliminary details.  Organize preliminary details in a sensible manner • Major entities, relationships among them  Try not to get caught up in making everything an entity • No more than 3 to 5 entities  Try to make the data dictionary  Form = input, report = output  End of inventory stage - you got a data dictionary and some sample forms and reports  when designing you’re creating; you’re solving a problem. When you think you found your solution you will have to present it to whoever you are working for • 1 : Perfect solution – most expensive nd • 2 : Budget solution • 3 : Practical(workable) solution – the one usually picked • 4 alternative: Null solution o What’s the meaning of not doing anything? o Is it a good idea to do nothing o let’s analyze a situation if we do not find a solution Data duplication • See data being repeated over and over again, avoid storing information twice • Extract common information Permanent data vs. likely to change data • Women’s name can change • Job titles, phone numbers, addresses o Analysis and Design  Look for large scale relationships  Formulating some tables, speculating, guessing which route to go  Look for a breakdown that give you distinct components  Quickly change focus from low level to high level  You identify major components of problem, and you work on the separately  some tables have various levels of fields  how many tables? Depends how many entities  DATABASE – take same approach • Start at top and break down into components – these will end up being table or enties.  NORMALIZATION – process will help you decide when to split tables into smaller tables. You need a table for each entity  candidate key – an attribute that could possibly serve as a primary key. • Looking for candidate keys in the process phase. • Doesn’t mean it will be key, but narrowing down and will pick one or two  key is used as a unique identifier(to identify the particular record) of a particular tupple • that’s how tables are connected to each other, by overlapping keys  operation known as a join • intersect, union, relational algebra • interjoin and outerjoin - operations that helps you connect tables at runtimes to extract common info from the tuple that can be found in other tables DESIGN STAGE o Synthesis  Put it all back together in a solution  Make sure each relation has a unique name  Avoid blanks in a name, use underscores • New ______ entries  Columns or fields in tables  select a data type  Data type is much more important in database systems than it is in spreadsheets • Underlying management of the database, the software uses data types to help control bad entries of data  integrity of data • Fix this by using keys, using data types  Data Type: Text, number, memo • Format is really strict about how it appears • guaranties how it stores • Numbers that’s not number needs to be stored as text (phone number with hyphen, etc.) • Big number little number, small integer, large integer, double o Many to Many - design M:N one entity is the supplier. Many suppliers : many sellers ; solve it by introducing a third entity - artificial Reader’s writer’s problem • It’s not a specific solution • When sharing files if you change an assignment file because there is a typo in it • Highly shared real time systems, very important when someone is changing data, the readers are locked out so they can’t read it. • What do you do about readers that have already started reading when you start to write it • When the writing process is initiated the file is locked • Solve problem  ignore problem with old reader getting screwed o How do you deal with readers reading an old copy o Lock out new readers but allow current readers to continue reading o In companies that have offices in different time zones around the world Entity- • Is it a person, place or thing? EX- mountains can be a entity • What is the key identity- without entity= wouldn’t have characteristics about them • Table will have to work for all attributes of entity • Need to look at most obvious thing you will be tracking • You will always find an anomaly= something that does not fit mold • Sketch out then make adjustments • Database= have a test data set- don’t keep tweaking that data set, even if you learn things force you to think in terms of changing structure, don’t change it right away • Make sure data set contains something that won’t violate this= data is not allowed. IF you have a limited set of data values, have numbers in a data dictionary • Entity attribute diagram, when it comes to terminology- might include in documents • Rectangular Diagram= used to describe entities • For different fields= used as headings • Want names of fields to be meaningful and at the same time to not be large and wide because it takes up room on the stream= you lose part of the heading • Data type is NOT THE SAME AS FORMAT= when it is number not the same as formatting display • Used in underlying matter so that data integrity is maximize= cannot enter number in date field without become a number • Spreadsheet you can = on database it will override • More important than the entity diagram, is the multivalued Attribute o Occurs when you can have more than one specific tuple= for one of the attributes • Primary key= to indentify a specific tuple= unlikely you will get assigned number that is not a number • Key needs to be unique= has to involve a lot of characteristics= • Composite Key= has to be unique, has to work like primary key but has mopre then one field two or more fields working together to form a unique identifier EX- Social insurance number 7= child _____ • Reason for having two tables= want to maintain relationship = 1:1- for every instance of this entity there is only one connected or related currents of an entity in that category • For entry in one table= corresponding entry in another table= would not be a one to one relationship COMPOSITE ENTITY • Solution to a problem  design problem, many to many • Many to many relationship o Supplier can supply many products, products come from many suppliers o Is not easily represented in relation databases • This table will contain more information about the item • Create your own primary key • Still talking about design o Asking yourself how many tables and fields o One table for every entity, introduce tables to resolve many to many o May want to break an entity into two entities if it gets too bulky • Try to use the smallest amount of information to get away with o atomic values - broken down as reasonably small as you can get them w/o being ridiculous
More Less

Related notes for COMPSCI 1BA3

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.