Computer Science Final EXAM PDF

Preview

Summary

final exam study guide for intro to CS...

Description

COMPUTER SCIENCE FINAL EXAM LECTURES 1-6 What is HTML, and how does it work? How is this related to the World Wide Web? ● Hypertext markup language that is used to portray your information on a browser ● Markup language is made up of tags that annotate what you would like the browser to look like ● Tags can be used to choose font size, font style, provide a link, show the source of an image, etc. ● WWW is “information” – it is a system of interlinked hypertext documents and other resources accessed via the internet Compare and contrast the history of Microsoft and Apple Computer in terms of their focus on hardware and software. ● Explain why the phrase “visiting a website” is a misnomer. What’s really happening? ● Website is delivered to you ● When page is requested, browser must 1st identify Web server on which the page resides o Web address, or URL, includes name of server as well as document name ● Once server name extracted from URL, browser sends message to that server over internet and requests page ● Server locates specified page in its directories and send page back to browser for display ● When message received, browser interprets HTML formatting information embedded in page & displays page accordingly in browser window ● Protocol determines how messages exchanged between browsers & servers are formatted o Known as HyperText Transfer Protocol (HTTP) What is a URL? What are its components parts? Why do some URLs begin with http://? ● Uniform Resource Locator ● Provides web pages with specific names so users can identify them and browsers can locate them ● http:// is a protocol prefix that specifies that the HyperText Transfer Protocol should be used in communications between the browser and server ● Immediately following is the server name, identifying Web server where page is stored ● Particular directory where page is located is next, followed by file name Explain how the concepts of users and permissions can create a secure file system. ● Users have unique usernames and passwords and are organized into groups ● File permissions are given to each file for: o Reading, writing or executing o Owner, group or others o This leads to 3x3 matrix of permissions What is CSS and how does it work? What are the key advantages? ● CSS stands for cascading style sheet ● Coordinates formatting, look and feel ● External file that is put into HTML file ● Uses different syntax than HTML uses ● ADVANTAGES: o Solves problem of inconsistent browsers o Simplify HTML source by externalizing format o Write-once, use-many formatting Explain the concept of an algorithm and how this relates to computing.

Explain the concept of programmability and describe how Jacquard’s loom helped demonstrate this idea before the rise of digital computing ● Programmability – ability to use same hardware for different purposes o One x box can play multiple games using the same system; you don’t need to buy a new system for each ● Jacquard’s loom allowed users to insert a punched game card with different holes to make different weavings using the same machinery Is the World Wide Web hardware or software? Explain. ● Collection of software that spans the Internet and enables interlinking of documents and resources What is a Web Server and how does it work? ● Software application that waits for/responds to HTTP requests ● Tim Berners-Lee wrote 2 applications to make the web: o Web browser called World Wide Web o Server called HTTPd ● Server received HTTP request, searches for resource (file) on disk, sends HTTP response (status code + data) o Status 404 if not found o Status 403 if forbidden o Status 200 if else How do you publish a web page? 1. Create HTML document, locate ancillary files (e.g. images) 2. Transfer files to web server 3. Set permissions to read access 4. Test URL in your browser LAMP Model ● Configuration used most commonly as structure for web applications ● Linux operating system for a server ● Apache web server software ● MySQL database software ● PHP/Perl/Python scripting language to create dynamic HTML

LECTURES 7-10 Explain what it means to “run the numbers”, and how spreadsheets accomplish this. What is an Excel formula? What syntax elements are needed to write one? Write a trivial example to show you know the syntax for it. ● Built-in function that allows excel to do a number of different calculations for you ● Syntax rules: o Formula can consist of operators, function names, cell references and cell names o Always begin with = sign o Must use Excel operator precedence ● EXAMPLE: = ((1*2)(3*4)) What is the point of an Excel built-in function? How do you use/reference one in your worksheet? Identify an example of an Excel built-in function. ● They do mathematical, statistical, financial, engineering, data/time, etc. types of computations Explain the general form and behavior of Excel IF function. Give an example to illustrate. ● General form: IF (, , ) ● Used to input data into excel and result in a numerical answer ● EXAMPLE: = IF ((A1 0.5 is considered good ● P-Value statistic describes likelihood of randomness explaining the value for the equation’s coefficient o P-Value > 0.05 or 0.10 indicates randomness o P-Value → 0 indicates non-randomness

LECTURES 11-15 Explain the concept of packet switching. Why is it needed? How is data transmitted under this scheme? ● Dividing of data into fixed-sized, numbered packets ● Individually routed to their destination then reassembled into messages ● ADVANTAGES: o Sending information in smaller units increases efficient use of connections o Allows network to react to failures or congestion o Improves reliability ● DISADVANTAGES: o Time required to assemble messages, resend missing packets o Speed of delivery: latency isn’t guaranteed

o

Inefficient for small packets

Who invented the Internet? Who paid for it? What are the key technologies that made the Internet possible? ● Visionary for internet was Lick – he saw need for something like the internet ● Bob Taylor and ARPA got monetary funding from Pentagon to carry out research ● 2 key technologies: o Packet switching o IMP Protocol Explain the difference between a MAC address and an IP address. How is each used for sending packets to the target host? ● IP address – logical address that uniquely identifies a computer on the internet and is expressed as 4 one-byte integers ● MAC (Media Access Control) address – unique identifier assigned to network interfaces for communications on the physical network segment Norm Abramson’s work on Aloha Net led to the development of the carrier sense multiple access/collision detection protocol. Why is CSMA/CS needed? How does CSMA/CD work? Which network technologies use it? On numbers systems: a) What is the binary numbering system and why do computers use it? ● Uses only the numbers 0 & 1 to correspond to data; “0” with on and “1” with off ● Computers can easily understand this and use this system to decode numbers, letters & symbols b) What is the hexadecimal number system and when/why is it used, and which symbols used in this system? ● Uses numbers and letters to correspond to data ● Used when 4 numbers (binary) are in a data packet The binary code 01010111 represents the character ‘W’. Identify and explain this encoding scheme, and show the equivalent decimal number. Show all your work. ● Binary encoding system is used to help computer decode data ● Helps to keep things efficient and orderly ● Uses decimal and hexadecimal numbers to correspond to letters, numbers & symbols used on keyboard ● (0x27)(1x26)(0x25)(1x24)(0x23)(1x22)(1x21)(1x20) = 87 o On ASCII chart, used to show what each number, letter & symbol means, the letter W corresponds with the number 87 POTS (Plain Old Telephone System) – to connect phone call, caller’s phone must be physically connected to connect to receiver’s phone; connecting these circuits (called switching) takes place at dedicated facilities called central offices Circuit Switched Network – creating circuits between source & destination; wasteful (circuits must be connected even if no data is being sent!) Network Interface Controller (NIC) - Each node had an NIC connected to its circuit board - CPU treats NIC as an input/output device - Communicates by reading or writing bytes of data to NIC - Each NIC has unique Media Access Control address, which distinguishes it from all other NICs Other Networks ● Local-area network (LAN) – connects relatively small number of machines in relatively close geographical area ● Wide-area network (WAN) – connects local-area networks over potentially large geographic distance

● Gateway/Router – particular computer on a LAN which directs all communication going between that LAN and other networks

Internet Protocol ● Each node has logical IP address ● Application data separate from physical transport mechanism ● IP packets can travel across multiple networks ● Packet delivery isn’t guaranteed (“best effort”) ● IP Layer Model o 4 layer model of network interaction to facilitate communication standards o Each layer deals with particular aspect of network communication o Network protocols usually specific to one layer in this model o IP is a layer 2 protocol Domain Name System ● Domain name – part of hostname that specifies specific organization or group ● Domain Name System (DNS) – distributed system for managing hostname resolution – process of converting domain name to IP address Routing ● Directs forwarding of IP packets from their source to their destination IP Packet Header ● Each protocol encapsulates some user data along with a packet header ● Header contains information used for routing and sequencing ● Specifies 13 fields including: packet length, source & destination IP addresses, fragment sequence, time to live (number of hops remaining) Application Layer Protocols ● Creates data & communicates to other applications on the same or another host Transport Layer Protocols ● Break messages into packets, hands them off to IP software for delivery and orders and reassembles the packets at their destination ● Transmission Control Protocol (TCP) – reliable transport protocol; guarantees delivery of packets as well as data integrity ● User Datagram Protocol (UDP) – unreliable transport protocol; doesn’t guarantee delivery of packets Radio ● Radio waves are electromagnetic radiation, which travel through the air o Wave length – length of a radio wave o Frequency – number of occurrences of a repeating event per unit time ● Radio transmissions are sent from transmitter to receiver

LECTURES 16-20 Explain the concept of ‘raster graphics’ which includes formats such as bitmap and jpeg. (a) How does it work? (b) Explain the concept of color depth. (c) What is the effect of this on storage requirements? ● Lifelike images composed of pixels which are dots of colors used to make the picture ● Bitmap format uses 24 bits or 3 bytes and takes up less room than other formats o Can be imperfections in the image, often not detected by human eye ● JPEG uses Hoffman encoding scheme and uses smoothing to create a clearer image o Takes up more room than bitmap

● Color depth refers to assigning a bit to each color in the image o The greater color depth an image contains, the more room it will take up o Can enhance image if looked at in the right format o High color images are 16 bits of color o True color images are 24 bits Explain the concept of ‘vector graphics’. (a) How does it work? (b) For which kind of images is vector graphics most appropriate? ● Composed by series of instructions given to computer by user ● Instructions are then interpreted to create the graphic ● Made up of more simple images and are rigid in terms of the shapes & colors ● Most appropriate for cartoon images with less detail as opposed to pictures & videos ● Easily resized mathematically and smaller in file size (a) Briefly contrast the concepts of lossless compressions and lossy compression. (b) How does the JPG image format use such compression strategies? ● Lossless compression o Avoids almost any loss of any part of image o Uses techniques like run length encoding, keyword encoding and Huffman encoding ▪ Used to condense file and still produce an image with great quality ● Lossy compression o Usually loses some of the image but not enough to be detected by human eye ● JPEG uses Huffman encoding technique to have lossless compression on its images o Also uses smoothing technique in order to produce better quality image (a) Describe the process of audio sampling. (b) How are sounds recorded as binary numbers? Discuss bit depth. (c) Explain what is meant by sampling rate and why this matters. ● (a) Explain why CD-audio quality music takes up a lot of bytes on disk. Explain the effects on file size and sound quality of (b) downsampling and (c) compression. (a) Briefly describe vector graphics and MIDI music. (b) Draw an analogy between vector graphics versus raster graphics and MIDI music versus sampled music. Discuss life-likeness and data requirements. ● Vector graphics o Series of instruction made into an image and composed of mostly lines and shapes ● MIDI o A way to specify instructions for music o Gives directions for note, voltage and amplitude ● Analogy between vector graphics and raster graphics is a map o Vector graphics is like a map that gives specific directions because they are simple o Raster graphics are like a map with a more visual quality, meaning you can see more of what the exact route looks like realistically o Vector graphic maps are easier to follow because the directions are straight forward & spelled out ● Analogy between MIDI music and sampled music is a cake o Sampled music is a cake that comes out the way you want consistently because you are the one consistently putting the ingredients together o MIDI is a cake which everyone makes on their own so it will not be as consistent and solid o For MIDI, each person uses their own equipment, giving each person a different sound, or a different cake Analog and Digital Information ● Analog – continuous representation, analogous to actual information it represents ● Digital – discrete representation, breaking information up into finite elements

Digitizing an Image ● Creating discrete rep. of analog data, suitable for storage and manipulation by a digital computer o Involves: ▪ Sampling – taking measurements (of color) at discrete locations within the image ● Measure the color for each pixel (discrete point of light (color) in picture) & record ▪ Quantizing RGB Encoding ● Additive color model ● Red, green and blue colors are combined in various ways to reproduce other colors Quantization ● Process of assigning discrete values to measurements taken in samples ● Color depth refers to number of bits used to represent a color ● 16 bits: HiColor o 5 bits for each number of RGB o 1 bit for transparency ● 24 bits: TrueColor o 8 bits used for each number in RGB o 8 bits used for transparency (called alpha) Keyword Encoding ● Replace frequently used words with a single character Run-Length Encoding ● Consider single character that is repeated over and over again in a long sequence; replace with a flag character, repeated character & number of repetitions (example: *n8) Huffman Encoding ● Uses variable-length bit strings to represent each character ● More frequently used letter have shorter strings to represent them ● To decode: look for match left to right, bit by bit record letter when a match is found begin next character where you left off

LECTURES 21-25 Explain these elements of Flash environment: timeline, stage, key frames. ● A timeline is the element that allows you to scroll through the frames; you can click a specific frame ● Stage is where animation of image is placed & displayed ● Key frame is inserted to select a specific point where you want the end point of a particular action to be Explain what a tween is (in Flash) and how it works. What are shapes & symbols and how do these relate to tweens? ● Element of flash that allows specific movements to occur ● Steps to use a tween: o Create layer o Choose frame you would like your animation, picture, etc. to end on by inserting keyframe o Somewhere between beginning and keyframe, right-click on any frame and insert tween o In motion tweens, the picture must be converted to symbol prior to adding tween ● 2 kinds of tweens: o Shape – seen on timeline with arrows from right to left ▪ Don’t use symbols ▪ Can shape tween color

o

Motion – allows movement of pictures and various effects to happen to them ▪ Must use symbols ▪ Layer has no arrow between keyframes

Explain the Flash fade-out/fade-in effect. How do you create one, what property of a pixel’s light representation is involved, and how is this related to TrueColor color bit depth. ● Involves alpha property which is transparency ● Steps to create: o Go to beginning of a motion tween and select stage o Go to properties, then alpha and set alpha to 0% so you cannot see the image o At end of tween, modify alpha to 100% o A tween between these 2 keyframes will cause the fade to be in effect ● 8 bytes are assigned for transparency; 225 = fully visible and 0 = fully transparent ● Alpha property of light is involved in this effect (a) Explain the concepts of spatial compression and temporal compression, and (b) how each of these techniques is used to compress digital video. ● Spatial compression o Very similar to JPEG in that it successfully condenses a very large portion of the frame without damaging its quality o Specific to one frame o Deals with 2 dimensions of video compression (width & height) o Based on removing redundant information within a fame ● Temporal compression o Deals with compressing many frames o Deals with 1 dimension o Based on differences between consecutive frames ● Spatial compression deals with compressing each individual frame, enabling video to run more quickly ● Temporal compression takes the redundancy between frames and eliminates them as well; enables smoother movement between frames What is a codec and what does it do? Identify and briefly describe the most common types of video compression (discussed in class). ● Compressor/DECompressor ● Algorithms used to shrink size of a movie to allow it to be played on a computer or over a network ● Most used lossy compression (a) Explain the key ways that YouTube reduces the data requirements for videos as compared to standarddefinition DVD format video. (b) How well did they do? ● Video player built on Macromedia’s Flash v.7 ● Standard video playback in 320 by 240 pixels at 25 frames per second o Average bitrate is about 200kbps for video ● Audio: an embedded MP3 audio stream, one channel o Average bitrate is 64kbps ActionScript ● Programming language used to control Flash animations ● “source code” statements are written in rigidly specified syntax and semantics Frame Rate ● How many distinct images per second

What is Flash?

● Animation and multimedia delivery platform ● Developed/sold by Adobe ● Content can be delivered via the web, played in Flash player or in web browser

LECTURES 26-30 Compare and contrast the running-time characteristics of a linear search versus a binary search. ● Grounds for comparison b/w linear search and binary search are number of comparison operations required in a worst-case scenario ● Linear search requires comparison for each item in list with a worst-case performance requiring n comparisons for a list of size n ● For a list of size n, binary search requires at most long(n) comparisons, which is extremely efficient ● Example: for a list with 45 billion elements, a binary search would take at most 36 comparisons ● Binary search only works on ordered lists Explain the approach shared the selection sort or bubble sort algorithms, and the key characteristics of these algorithms. Explain the approach used by and run-time characteristics of a sorting algorithm like the quick sort. ● Divide-and-conquer strategy ● Takes advantage of the fact that it is quicker to sort a smaller number of items ● Algorithm splits list into sub lists around a split point ● Algorithm is applied recursively (e.g. sub lists are also sorted by dividing into sub lists, and so forth) ● Even...