Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Comp.Sci Review 1-7
Computer science review (chapters 1-7)
| Term | Definition |
|---|---|
| computer network | A set of independent computer systems connected together by telecommunication links for the purpose of sharing information and resources |
| switched, dial-up telephone lines | A common way to transmit data in the early days of networking. When you dial a telephone number, a circuit (i.e., a path) is temporarily established between the caller and callee |
| bandwidth | Capacity for transmitting data |
| nodes | Individual computer on a network; also called host |
| broadband | Any communication link with a transmission rate exceeding 256,000 bps,today often up to 25 million bps. Typical broadband options for home users are cable modems and digital subscriber lines (DSL) |
| modem | Device that modulates, or alters, a standard analog signal called a carrier so that it encodes binary information |
| digital subscriber line (DSL) | Broadband technology that uses the same wires that carry regular telephone signals into your home, and therefore is provided by either your local telephone company or someone certified to act as their intermediary. |
| Although it uses the same wires, a DSL signal uses a different set of frequencies and transmits how? | and it transmits digital rather than along signals |
| cable modem 8 | Broadand technology that makes use of the links that deliver cable TV signals into your home, so it is offered by cable TV providers |
| 10. Fast Ethernet | Transmits at 100 Mbps over coaxial cable, fiberoptic cable, or regular twisted-pair copper wire |
| 9. Ethernet | The most widely used broadband technology |
| 11. gigabit networking | 11. Transmission lines that support speeds of 1 billion bits per second (Gbps |
| 12. gigabit Ethernet standard | 12. IEEE standard that supports communication on an Ethernet cable at 1,000 Mbps (1 Gpbs) |
| 13. IEEE (Institute of Electrical and Electronics Engineers) | 13. International professional society responsible for developing industrial standards in the area of telecom |
| 14. wireless data communication | 14. Transmitting data using radio, microwave, and infrared signals |
| 15. mobile computing | 15. The ability to deliver data to users regardless of their location |
| 16. wireless local area network (WLAN) | A wireless network in which the user transmits from his or her computer to a local wireless base station, often referred to as a wireless router, that is no more than a few hundred feet away. Connects to tradition wired network (DSL or CABLE MODEM) |
| 17. Wi-Fi | 17. Wireless transmissions that use IEEE 802.11 standards for local wireless access |
| 18. IEEE 802.11 wireless network standard | Another name for Wi-Fi |
| 19. Wi-Fi hot spot | Wireless base station (router) |
| 20. Bluetooth | A low-power wireless standard used to communicate between devices located quite close to each other, typically no more than 30– 50 feet (10–15 meters) apart |
| 22. metropolitan area network (MAN) | A network whose scope is larger than the few hundred feet of a LAN, typically a few blocks up to an entire city. Its purpose is to provide full Internet connectivity to all computers within a neighborhood or metropolitan area. |
| 21. personal area network (PAN) | A collection of privately owned interconnected digital devices all located in close proximity |
| 23. wireless wide area network (WWAN) | Nodes (often a tablet or smart phone) transmit messages to a remote base station provided by a telecommunications company, which may be located many miles away. base station is large cellular antenna on large structure - long distance |
| 24. wide area network | Connects devices that are not in close proximity but rather are across town, across the country, or across the ocean |
| 25. RFID | A tag that can be attached to or embedded within objects that includes a communications device that can send and receive wireless messages over a network |
| 26. local area network (LAN) | Network that connects hardware devices such as computers, printers, and storage devices that are all in relatively close proximity, such as in a building or on a single campus |
| 27. bus | (1) a path for electrical signals; (2) LAN topology in which all nodes are connected to a single shared communication line |
| 28. ring | LAN topology that connects the network nodes in a circular fashion, with messages circulating around the ring in either a clockwise or counterclockwise direction until they reach their destination |
| 29. star | LAN topology that has a single central node that is connected to all other sites. This central node can route information directly to any other node in the LAN. Messages are first sent to the central site, then forwards them to the correct location |
| 30. shared cable | A wire (such as twisted-pair copper wire, coaxial cable, or fiber-optic cable) is strung around and through a building. Users tap into the cable at its nearest point |
| 31. repeater | Device that simply amplifies and forwards a signal |
| 32. bridge | A “smarter” device than a repeater that has knowledge about the nodes located on each separate network. It examines every message to see if it should be forwarded from one network to another |
| 33. switch | A device that allows you to build a LAN by connecting devices to an Ethernet interface in each room |
| 34. broadcasting | Messages are sent by a node on a local area network to every other node on that same LAN |
| 35. dedicated point-to-point lines | Line or wireless link that directly connects two machines |
| 36. mesh network | An interconnection system in which a node is connected to other nodes via direct links |
| 37. store-and-forward, packet-switched | Technology used by WANs to deliver messages that “hop” from one node to another to make their way from source to destination |
| 38. packet | An information block with a fixed maximum size that is transmitted through the network as a single unit |
| 39. router | Device that connects networks |
| 40. Internet service provider (ISP) | business whose purpose is to provide access from a private network (such as a corporate or university network) to the Internet, or from an individual’s computer to the Internet |
| 41. Internet | A huge, interconnected “network of networks” that includes nodes, LANs, WANs, bridges, routers, and multiple levels of ISPs |
| 42. firewalls | A software or hardware component that controls access from a network to a computer system |
| 43. protocol | In networking, a mutually agreed upon set of rules, conventions, and agreements for the efficient and orderly exchange of information |
| 44. Internet Society | A nonprofit, nongovernmental, professional society composed of more than 100 worldwide organizations in 180 countries and thousands of individual members united by the common goal of maintaining the viability and health of the |
| 45. protocol hierarchy | The hierarchical set of network protocols that are used to transmit messages across a network |
| 46. TCP/IP | Transport Control Protocol/Internet Protocol; the name of the specific protocol stack used in the Internet |
| 47. Physical layer protocols | Govern the exchange of binary digits across a physical communication channel, such as a fiber-optic cable, copper wire, or wireless radio channel |
| 48. error detection and correction | The process of determining whether a message did or did not arrive correctly and, if not, getting a correct copy of that information |
| 49. framing | Identifying the start and end of a message sent over a network |
| 50. Medium Access Control protocols | Network protocols that determine how to arbitrate ownership of a shared line when multiple nodes want to send messages at the same time. |
| 51. collision | When two or more nodes on a shared link transmit at the same time and destroy each other’s |
| 52. Logical Link Control protocols | Ensure that the message traveling across this channel from source to destination arrives correctly |
| 53. ARQ algorithm | Automatic repeat request algorithm, the basis for all Data Link Control protocols in current use |
| 54. acknowledgment message | A network control message that says that your message correctly arrived at its destination |
| 55. Network layer protocols | Ensure that a message is delivered from the site where it was created to its ultimate destination |
| 56. IP | The network layer in the Internet |
| 57. host names | The symbolic, character-oriented name assigned to a host computer |
| 58. IP address | The 32-bit or 64-bit binary address that the Internet uses to actually identify a given host computer |
| 59. Domain Name System (DNS) | Internet application that converts from a symbolic host name such as macalester.edu to its 32-bit IP address |
| 60. routing | Selecting one specific path through the Internet among various nodes |
| 61. port number | A numeric identification of a program running on a host computer. It is used by the Transport layer protocols |
| 62. Transport layer protocols | Create a “program-to-program” delivery service, in which we don’t simply move messages from one host to another, but from a specific program at the source to a specific program at the destination |
| 63. TCP (Transport Control Protocol) | The primary transport protocol on the Internet |
| 64. Application layer protocols | The rules for implementing the end-user services provided by a network |
| 65. Uniform Resource Locator | A symbolic string that identifies a webpage |
| 66. Hypertext Transfer Protocol (HTTP) | The protocol used by the World Wide Web to transfer pages of information coded in hypertext markup language (HTML) |
| 67. Email (electronic mail) | The single most popular application of networks for the last 35 years |
| 68. spam | Electronic junk mail |
| 69. bulletin board system | Application that flourished in the 1980s and 1990s that used shared public file(s) where anyone could post messages and everyone was free to read the postings of others |
| 70. Internet forums | Support the real-time exchange of messages. In addition to simply posting a message that can be read at a later time, also suport interactive messaging–what the sender types appears immediately on the screen, allowing for the direct exchange of ideas |
| 71. chat rooms | Service that supports real-time exchange of messages over the Internet |
| 72. texting | Also known as SMS (Short Message Service), an application that allows for the rapid exchange of short messages, often using wireless cell phone technology |
| 73. social networks | Systems that create communities of users who share common interests and activities and that provide multiple methods of online interaction |
| 74. resource sharing | The ability to share physical resources, such as a printer or storage device, as well as logical resources, such as software, data, and information |
| 75. print servers | Shared printer available across a network |
| 76. file server | Shared data-storage disk(s) available across a network |
| 77. client/server computing | The style of computing wherein some nodes provide services while the remaining nodes are users (or clients) of those services |
| 78. distributed database | A database distributed among the geographically dispersed sites of an organization and shared as needed |
| 79. data warehouse | Network nodes that integrate massive amounts of information from a number of disparate sources and allow it to be electronically searched for specific facts or documents |
| 80. data marts | A single-subject data warehouse |
| 81. groupware | Software that facilitates the efforts of individuals connected by a network and working on a single shared project |
| 82. wiki | A set of webpages that everyone is free to access, add to, or modify |
| 83. Electronic commerce | A general term applied to any use of computers and networking to support the paperless exchange of goods, information, and services in the commercial sector |
| 84. ecommerce | A general term applied to any use of computers and networking to support the paperless exchange of goods, information, and services in the commercial sector |
| 85. cloud computing | A computing system in which the user can be completely unaware of where data is stored and where services are being provided |
| 86. server farm | An integrated collection of servers providing services over a network that would not be possible using only a single device |
| 87. virtualization | The separation of a service from the entity (or entities) providing that service |
| 88. internetworking | Concept first developed by Robert Kahn of ARPA, that any WAN is free to do whatever it wants internally but at the point where two networks meet, both must use a common addressing scheme and identical protocols |
| 89. gateway | Device that makes internetwork connections and provides routing between different WANs |
| 90. hypertext | A collection of documents interconnected by pointers, called links |
| 91. World Wide Web | The hypertext information system developed by Tim Berners-Lee at CERN in the late 1980s |
| 92. net neutrality | The concept that that a public information network such as an Internet service provider (ISP) should treat all users, all platforms, and all content equally |
| 1. naked machine | A computer without any helpful system software to facilitate its usage |
| 2. System software | A collection of computer programs that manage the resources of a computer and facilitate access to those resources |
| 3. virtual machine | The computer system as perceived by the user as opposed to the hardware that actually exists; the set of services and resources created by the software and seen by the user. |
| 4. virtual environment | Another term for a virtual machine |
| 5. operating system | The main piece of system software that helps to run and manage the computer system |
| 6. graphical user interface (GUI) | The visual overview of the computer that is provided by the operating system |
| 7. program libraries | A collection of software utilities provided for the user |
| 8. assembly language | A low-level programming language that maps 1:1 into machine language |
| 9. low-level programming languages | General term for a programming language that is close in design to machine languages |
| 10. high-level programming languages | A programming language that uses both natural language constructs and mathematical notation. |
| 11. source program | The original program as written by the programmer |
| 12. object program | The translated source program produced by the assembler or compiler |
| 13. assembler | The program that translates a source assembly language program into machine language |
| 14. compilers | The program that translates a high-level language into machine language |
| 15. pseudo-op | An assembly language command that does not actually produce a machine-language instruction but performs a service on behalf of the user |
| 16. algorithmic problem-solving cycle | The sequence of designing an algorithm, coding it into a programming language, translating it into machine language, and then running it on a Von Neumann computer to solve the problem |
| 17. pass | An examination of every statement in the source program by an assembler or compiler |
| 18. symbol table | A table that contains the name of every symbolic variable in a program and its equivalent binary memory address |
| 19. binding | The process of associating a symbolic name with a physical memory address |
| 20. object file | The file produced by the assembler or compiler that contains the translated machine language instructions and the address of where each instruction is to be loaded |
| 21. loader | System software that reads instructions from the object file and stores them into memory for execution |
| 22. system commands | Commands given by the user to the operating system to perform a service on the user’s behalf |
| 23. command language | The language used to enter system commands. Today it is more commonly a set of actions, such as mouse clicks or finger taps |
| 24. deadlock | When a computer is frozen because two components are each holding a resource needed by the other |
| 25. batch operating systems | A type of operating system in which a batch of programs are collected and then run as a group, all at once, one after the other |
| 26. multiprogrammed operating systems | A type of operating system in which multiple user programs are loaded into memory at the same time, and the computer takes turns running them |
| 27. time-sharing system | A multiprogrammed operating system in which the user can interact with the running program |
| 28. network operating system | An operating system that manages the resources of both the local computer as well as providing efficient access to a collection of remote resources via a computer network |
| 29. real-time operating system | An operating system that must provide access to particular resources or respond to system problems within a well defined time limit |
| 30. embedded systems | A computational device (chip, processor, computer) embedded within another system. |
| 31. distributed computing environment | A system that hides the exact location of specific pieces of information and allows the user to view the system as simply one large collection of resources |
| 32. gesture-based computing | The use of body and facial motions to communicate computational requests |
| 1. functional units | Subunits of a computer that perform tasks such as instruction processing, information storage, computation, and data transfer |
| 2. computer organization | The branch of computer science that studies computers in terms of their major functional units and how they work |
| 3. level of abstraction | A specific way to view a system |
| 4. hierarchy of abstractions | A series of abstractions, each one more detailed and each one showing lower level components of a system |
| 5. Von Neumann architecture | The computational model designed by John Von Neumann and first implemented in the EDSAC computer of 1947; the structure and organization of virtually all modern computers |
| 6. central processing unit | The part of a computer consisting of the control unit and the ALU |
| 7. sequential execution of instructions | When one instruction at a time is fetched from memory to the control unit, where it is decoded and executed |
| 8. Memory | The functional unit of a computer that stores and retrieves the Instructions and the data being executed |
| 9. random access memory (RAM) | A memory structure in which each cell has an address and it takes the same amount of time to fetch or store any cell |
| 10. Read-only memory (ROM) | A memory structure that can only be accessed, not written into or changed |
| 11. memory width | The number of bits in a single memory cell |
| 12. memory cell | The minimum unit of memory access |
| 13. address space | The maximum amount of memory that a computer can physically hold. It is determined by the size of the address field |
| 14. memory address | The unique numeric identifier for a memory cell |
| 15. nondestructive fetch | When you access the contents of a memory cell you only copy it, you do not destroy it |
| 16. destructive store | When you store a new value in a memory cell and destroy its previous contents |
| 17. memory access time | The time it takes to fetch or store the contents of a single memory cell |
| 18. nanosecond 18. nanosecond | One-billionth of a second |
| 19. memory address register (MAR) | The memory register that holds the address of the cell to be fetched from or stored into |
| 20. memory data register (MDR) | The memory register that holds the data value to be stored or the data value that was just fetched |
| 21. fetch/store controller | The component that determines whether a value will be placed into memory or copied from memory |
| 22. principle of locality | When you access a memory cell the likelihood is that you will access memory cells with addresses very close to this one in the near future |
| 23. cache memory | A special high-speed memory unit that keeps a copy of memory cells with a high likelihood of access in the near future |
| 24. cache hit rate | The percentage of the time that the information needed is in cache memory |
| 25. input/output (I/O) | The devices that allow a computer system to communicate and interact with the outside world as well as store information |
| 26. volatile memory | Memory that loses its contents when the power is turned off |
| 27. nonvolatile memory | Memory that does not lose its contents even when the power is turned off |
| 28. mass storage systems | Systems or devices where information is kept for long periods of time and not lost when the computer is not being used |
| 29. data centers | Cloud storage areas for large numbers of rmote data servers |
| 30. direct access storage devices (DASDs) | A mass storage device in which each unit of information is associated with a unique address, but the time to access each piece of information may not be the same |
| 31. sequential access storage devices (SASDs) | A mass storage device in which information is located by sequentially searching all the information that is stored |
| 32. sectors | A magnetic disk storage unit containing an address, a data block, and a fixed number of bytes. Sectors are arranged in concentric tracks on a disk |
| 33. track | A single concentric circle of information on a magnetic disk |
| 34. Seek time | The time required to move the read/write head to the correct track on a magnetic disk drive |
| 35. latency | The time required to rotate a magnetic disk to the beginning of the desired sector |
| 36. transfer time | The time required to read the desired sector on a magnetic disk into main memory |
| 37. I/O controller | A special-purpose device that controls the operations of an input/output device |
| 38. interrupt signal | A signal sent by the I/O controller to the CPU to let it know that it has completed an I/O operation |
| 39. arithmetic/logic unit (ALU) | A computer subsystem that performs such mathematical and logical operations as addition, subtraction, and comparison for equality |
| 40. processor | A system that is composed of the ALU together with the control unit; the CPU |
| 41. data path | The ALU circuits, registers, and interconnections between components |
| 42. register | A special, high-speed storage cell |
| 43. bus | (1) a path for electrical signals; (2) LAN topology in which all nodes are connected to a single shared communication line |
| 44. stored program | The instructions to be executed by the computer are represented as binary values and stored in memory |
| 45. control unit | The computer subsystem that fetches and executes instructions stored in the memory of the computer |
| 46. machine language | The programming language that a processor is directly able to understand and execute. It is written in binary. |
| 47. instruction set | The set of all operations that can be executed by a processor |
| 49. CISC machines | Complex Instruction Set Computer; machine that has a very large and complex instruction set |
| 48. RISC machines | Reduced Instruction Set Computer; machine that has a very small and simple instruction set, but where each instruction is highly optimized and executes very quickly |
| 50. program counter (PC) | The register that holds the address of the next instruction to be executed |
| 51. instruction register (IR) | The register that holds a copy of the instruction to be executed |
| 52. Von Neumann bottleneck | The inability of sequential, one-at-a-time processors to handle extremely large problems in a reasonable timeframe |
| 53. non-Von Neumann architectures | Computer designs based on models other than the standard Von Neumann architecture |
| 54. parallel processing | Building computers with two or more processors that work in parallel |
| 55. MIMD parallel processing | A parallel processing model in which multiple processors all work independently on their own program to solve a single problem; MIMD stands for multiple instruction stream/multiple data stream); also called cluster computing |
| 56. cluster computing | A parallel processing model in which multiple processors all work independently on their own program to solve a single problem; also called MIMD parallel processing |
| 57. grid computing | A MIMD model in which the individual processors can be computer systems belonging to a wide range of groups or individuals |
| 58. parallel algorithms | Algorithms that exploit the presence of multiple processors to solve a single problem |
| 59. quantum computing | A field of computer design using the principles of quantum mechanics in which a single bit of information can be not just a 0 or a 1 but in both states at the same time |
| 1. binary numbering system | A base-2 positional numbering system |
| 2. positional numbering system | A numbering system in which each position of a number represents a value times the radix to a given power |
| 3. bits | A binary digit, 0 or 1 |
| 4. arithmetic overflow | An attempt to represent an integer that exceeds the maximum allowable value |
| 5. sign/magnitude notation | A way to represent signed integer values in which one bit is used to represent the sign and the remaining bits are used to represent the magnitude |
| 6. two’s complement representation | A way to represent signed integers in which we count up from zero to represent positive values and we count down from zero to represent negative values |
| 7. scientific notation | A way to represent real numbers as a mantissa times a base to an exponential power |
| 8. ASCII | An acronym for the American Standard Code for Information Interchange; ASCII is an international standard for representing textual information that uses 8 bits per character |
| 9. Unicode | A code set for textual representation that uses a 16-bit representation for characters; a newer variant uses 32 bits |
| 10. digital representation | The allowable values for a given object are drawn from a finite set, such as the letters {A, B, C, . . . , Z} or a subset of integers {0, 1, 2, 3, . . . , MAX} |
| 11. analog representation | Objects can take on any continuous value |
| 12. amplitude | The height of a periodic wave which is a measure of its loudness |
| 13. period | The time it takes for a single wave in a periodic wave function |
| 14. frequency | The total number of cycles per unit time measured in cycles/second, also called hertz |
| 15. digitized | Converted from a continuous set of values to a series of individual numeric values |
| 16. sampling | At fixed time intervals, the amplitude of a signal is measured and stored as an integer value; the wave is then represented in the computer in digital form as a sequence of sampled numerical amplitudes |
| 17. sampling rate | The time interval between sampling points |
| 18. bit depth | The number of bits used to encode each sample during digitization |
| 19. raster graphics | A method for storing an image in which a sequence of picture elements is digitized and stored one row at a time, from left to right |
| 20. RGB encoding scheme | A method for encoding color that digitizes the contribution of the red, green, and blue components of each pixel |
| 21. byte | 8 bits |
| 22. data compression | The process of reducing the number of bits required to represent a sound or image |
| 23. compression ratio | Measures how much a compression scheme has reduced the storage requirements of the data |
| 24. lossless compression | No information is lost in the compression, and it is possible to reproduce exactly the original data |
| 25. Lossy compression | Compress data in a way that does not guarantee that all of the information in the original data can be fully and completely recreated |
| 26. gigabyte | One billion bytes |
| 27. transistor | An electronic device that can be in an OFF state, which does not allow electricity to flow, or in an ON state, in which electricity can pass unimpeded; a transistor is a solid-state device that has no mechanical or moving parts |
| 28. Boolean logic | A branch of mathematics that operates on the values true and false |
| 29. hardware design | The process of designing the low level components of a computer, including arithmetic and control circuits |
| 30. logic design | Another term for hardware design as it uses the capabilities of Boolean logic to carry out the design process |
| 31. Boolean expression | An expression that can evaluate only to true or false |
| 32. truth table | A table that contains columns labeled Inputs that list the possible combinations of true/false values |
| 33. gate | An electronic device that operates on a collection of binary inputs to produce a binary output |
| 34. circuit | A collection of logic gates (1) that transforms a set of binary inputs into a set of binary outputs and (2) where the values of the outputs depend only on the current values of the inputs; more properly called a combinational circuit |
| 35. sequential circuits | Circuit that contains feedback loops in which the output of a gate is fed back as input to an earlier gate |
| 36. circuit construction algorithms | An algorithm that allows us to go from a specification of what we wish to accomplish to a circuit which carries out those specifications |
| 37. circuit optimization | The process of reducing the number of gates needed to implement a circuit |
| 38. control circuits | A circuit used to make decisions and control the flow of execution |
| 39. multiplexer | A control circuit that has 2^N input lines and 1 output line |
| 40. decoder | A control circuit that has N input lines numbered 0, 1, 2, . . . , N - 1 and 2^N output lines numbered 0, 1, 2, 3, . . . , 2^N - 1 |
| 41. fault-tolerant computing | [in Exercise 24]The ability to continue functioning even in the presence of the failure of one or more components |
| 1. efficiency | An algorithm’s careful use of time and space resources |
| 2. benchmarking | Running a program on many data sets to be sure its performance falls within required limits; timing the same algorithm on two different machines |
| 3. analysis of algorithms | The study of the efficiency of algorithms |
| 4. sequential search algorithm | An algorithm that searches for a target value in a random list by checking each list item in turn |
| 5. order of magnitude n | The efficiency classification of an algorithm whose work varies as a constant times the input size n |
| 6. searching | The task of finding a specific value in a list of values, or deciding it is not there |
| 7. sorting | The task of putting a list of values into numeric or alphabetical order |
| 8. selection sort algorithm | A sorting algorithm that keeps moving larger items toward the back of the list. |
| 9. order of magnitude n 2 | The efficiency classification of an algorithm whose work varies as a constant times the square of the input size n |
| 10. flops | floating-point operations per second; |
| 11. binary search algorithm | An algorithm that searches for a target value in a sorted list by checking at the midpoint and then repeatedly cutting the search section in half |
| 12. order of magnitude lg n | The efficiency classification of an algorithm whose work varies as a constant times lg(n) |
| 13. polynomially bounded | An algorithm that does less work than some polynomial expression of the input size n |
| 14. exponential algorithm | An algorithm whose work varies as some constant to the power of the input size n |
| 15. intractable | A problem for which no polynomially bounded solution exists |
| 16. approximation algorithms | An algorithm that doesn’t give the exact answer to a problem, but provides a close approximation to a solution |
| 17. bubble sort | [Exercise 11]A sorting algorithm that makes multiple passes through the list from front to back, each time exchanging pairs of entries that are out of order |
| 18. Smart bubble sort | [Exercise 14] A variation of the bubble sort algorithm that stops when no exchanges occur on a given pass |
| 19. mergesort | [Exercise 15]A sorting algorithm that breaks the list to be sorted into smaller and smaller lists and then assembles the smaller sorted lists back into larger and larger sorted lists |
| 20. short sequential search | [Exercise 27] A variation of the sequential search algorithm that requires a sorted list and stops once it has passed the place where the target could occur |
| 1. pseudocode | A notation used to design algorithms. It uses English constructs, mathematical notation and an informal algorithmic structure designed to look like a high-level programming language. |
| 2. computation | An algorithmic operation that carrys out a single numeric computation and stores the result |
| 3. variable | A named storage location that can hold a data value |
| 4. Input | An operation that causes data values from the outside world to be brought into the algorithm |
| 5. Output | An operation that causes computed values to be sent to the outside world for viewing or saving |
| 6. sequential algorithm | An algorithm that executes its operations in a straight line, from top to bottom, without any branching |
| 7. iterative operations | Algorithmic operation that repeats a block of instructions |
| 8. control operations | Operations that alter the normal sequential flow of control within an algorithm |
| 9. Conditional statements | Algorithmic operation that asks a question and selects the next step to carry out based on the answer to that question |
| 10. iteration | The repetitive execution of a block of operations |
| 11. continuation condition | The true/false condition in an iterative statement that will determine when the iteration has been completed |
| 12. loop body | The block of statements that are to be repetitively executed |
| 13. primitive operations | An operation that can be directly understood by the computing agent executing the algorithm and which does not have to be further clarified or explained |
| 14. algorithm discovery | The process of finding an algorithmic solution to a given problem |
| 15. library | A collection of useful prewritten algorithms that can be used during problem solving |
| 16. abstraction | The separation of the high-level view of an entity from the low-level details of its implementation |
| 17. top-down design | A problem solving strategy in which you begin at the highest level view of the problem and, in steps, address the lower-level details of how to accomplish each operation |
| 1. algorithm | A well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time |
| 2. Computer science | The study of algorithms, including their mathematical properties, hardware and linguistic realizations, and their applications |
| 3. Sequential operations | Algorithmic structure that carries out a single task and then moves on to the next operation in sequence |
| 4. Conditional operations | Algorithmic operation that asks a question and selects the next step to carry out based on the answer to that question |
| 5. Iterative operations | Algorithmic operation that repeats a block of instructions |
| 6. computing agent | The entity that executes the steps of an algorithm |
| 7. unambiguous operation | An operation is unambiguous if it can be understood by the computing agent without having to be further defined or simplified |
| 8. primitive | An operation that can be directly understood by the computing agent executing the algorithm and which does not have to be further clarified or explained |
| 9. effectively computable | There exists a method for actually carrying out the intent of the operation |
| 10. infinite loop | The repetitive execution of a block of operations that will never end. This is a fatal error when it occurs in an algorithm |
Created by:
EmilyPipp