CS 101 outline and review questions

1. Key terms: computer, computer science, hardware, software, analog, digital
2. Historical milestones
3. Binary numbers, conversions, octal, hex
   a. Convert between decimal and binary
   b. Familiarity with powers of 2
   c. The number of possible representations for n bits
   d. Octal and hexadecimal shorthand for binary
4. All information is stored in binary; software and file type determine the precise representation and how translation is done; size and scheme
5. Integer representations: unsigned, signed, sign-magnitude, BCD
   a. Range of values for each representation
   b. How to represent negative numbers
   c. Waste in the case of BCD
6. Real number representation
   a. Extension of the place value system to negative powers
   b. What happens to a binary representation when you double or halve a value
   c. How to convert a real number to binary. The representation may contain a repeating pattern.
   d. Scientific notation: decimal versus binary, normalized
   e. Role of sign, exponent, mantissa
   f. Distribution of values, holes in the representation, ramifications of the choice of number of bits of exponent and mantissa
7. Linear versus non-linear (graph or tree) representation schemes
   a. Difference between a graph and a tree
   b. Why some information is inherently linear or nonlinear
   c. Examples of linear and nonlinear information
   d. Mathematical expression expressed as a tree: Be able to convert between 3 representations for an expression: ordinary infix notation, postfix notation, tree. Advantage of postfix notation
8. Text representation: properties of ASCII and Unicode
9. Data compression techniques: keyword encoding, run length encoding, Huffman code
   a. Given the distribution of symbols, derive a Huffman code; Know how to encode and decode according to a Huffman code
10. Image representation
    a. terminology (pixel, landscape, portrait, aspect ratio, resolution, dynamic range, binary image, pixelation, sampling, quantizing)
    b. schemes: RGB, CMY(K), HSB, Indexed color
11. Excel (see lab manual)
12. Logic gates:
    a. How AND, OR, XOR, NOT, NAND and NOR gates work, truth table
    b. digital circuits built from several gates such as an adder
13. Finite automaton and Turing machine as a model for computation
    a. Draw and analyze simple finite automata
14. Regular expressions: wild cards, purpose/applications
15. Units of time, speed and space
    a. Speed and time units are reciprocals of each other
    b. Speed of light as a limitation
    c. Space units not needed until we get to chapter on memory, but they use the same prefixes for speed
16. CPU instruction execution
17. Execution time formula; improving performance; pipelining, stalls
18. Memory: classification as main or secondary, memory hierarchy, media, type of access, examples, disk terminology (platter, pit, land, seek time, latency, fragmentation)
19. The nature of problem solving, software; problem-solving process
20. Software elements: program, types of statements, algorithm, structure of solution (e.g. loop), I/O, examples, 3 kinds of errors
21. Programming languages: machine, assembly, high-level
22. Searching and sorting (e.g. 4 ways to do each)
    a. 2 search techniques if the data is arranged linearly: linear search, binary search
    b. 2 search techniques if the data is arranged nonlinearly: BFS, DFS
    c. 4 sorting algorithms: insertion, selection, merge, bubble
23. OS role and responsibilities (namely: passwords, CPU mgmt., memory mgmt., file mgmt., I/O, user interface)
24. CPU Scheduling, system load
    a. Scheduling algorithms: First come first served, Round Robin, Shortest job next
25. File permissions, file organization, BFS, DFS
26. Access
27. Text software: editor, browser, text formatter, word processor
28. Text applications: Spell checking and binary search; readability
29. fonts: typeface + point size
30. Hypertext, HTML documents and tags
31. Image processing: brightness and contrast, histogram
32. Communication
    a. Shannon’s model has 6 parts: source, destination, transmitter, receiver, medium, noise
    b. Cryptography, for example Caesar cipher, cryptogram, 1-time pad
    c. error detection using parity bits
    d. LAN topologies: point-to-point, star, bus, token ring
    e. TCP/IP – packet switching over the Internet
33. Dijkstra’s algorithm, Traveling Salesman problem
34. Download speed: overhead, flight time, bandwidth
35. Terminology for Web and Internet applications
36. Web searching and issues

Test your comprehsion of the material with these questions. Most of these come directly from examples in class. A great way to prepare for a test is for you to come up with your own questions and check your answers. You can practice doing this with some of my review questions below.

Note that in the case of yes/no questions, you should be able to justify your answer. In general, being able to explain your reasoning is more important than simply stating an answer, which you could forget or accidentally get wrong.

1. Write down a bit string having 6 bits. What number does this bit string represent in the following representation schemes?
• unsigned
• signed
• sign-magnitude

Practice this question with a bit string that starts with a 1, and a bit string that starts with a 0.

 

2. Pick a two digit number (integer). Determine the 8-bit representations for this number using the following representation schemes
• unsigned
• signed
• sign-magnitude
• BCD

Practice this question also with a two digit negative number.

 

3. The single-precision floating-point representation is a method of representing real numbers. We allocate 8 bits for the exponent. Explain how we can determine the approximate bound for the largest possible (finite) number that we can represent, and the smallest positve number.
• How would your answers change if we had instead allocated 7 bits for the exponent? Would this be practical for scientific applications?

 

4. This question features some approximate values for large powers of 2. These approximations will appear in brackets. You may find the question easier to grasp initially in terms of these approximate values than just the powers of 2.
   Using the fact that the mantissa for a single-precision floating-point number has 23 bits:
• How many real numbers can be exactly represented between two consecutive powers of 2?
• Consider the real numbers that we can exactly represent between 8 and 16. How far apart are they?
• How far apart are the exact real numbers between 2^23 [8 million] and 2^24 [16 million]?
• How far apart are the exact real numbers between 2^24 [16 million] and 2^25 [32 million]?
• What does the answer to the previous question tell us about real number versus integer representation?
• Explain why a financial account balance should not be stored in this format. Illustrate the problem with a specific example.

 

5. The binary number 110.1001 equals what base-10 number? If we multiply this binary number by 4, what is the binary result?

 

6. In what ways did typical computers of the 1980s differ from those of the 1950s? How do today's PCs differ from those of 20 years ago?

 

7. If the ASCII code for 'A' is 65, what symbol has ASCII code 85?

 

8. The ASCII codes for 'a' and '0' (zero) are 97 and 48, respectively. What is the ASCII code for '3' ? What is the ASCII code for '6' ? The value '3' + '3' is the ASCII code for what letter? When you ask the computer for 3+3, how come it knows to give you 6 as the answer instead of a letter?

 

9. Basic image properties:
   • What does an image look like if we reduce its dynamic range too much? What if we reduce its resolution too much?
   • How much memory does an image need if it uses a grayscale system with 16 possible shades of gray, and it measures 400 by 300 pixels?
   • What are the dimensions of your computer's screen?

 

10. Give example RGB codes for light green, medium green and dark green.
    
    
11. When we use indexed color, we often express the R,G and B values in hexadecimal, and the values we can choose are 00, 33, 66, 99, cc and ff. What color is represented by the code #cc0000?

 

12. Using indexed color and dithering, explain how we can approximate a background color close to the value #993355.

 

13. Convert this arithmetic expression to postfix notation: (1+2) * (3+4).

 

14. Suppose an XOR gate has two inputs x and y and an output z. If x = 1 and z = 1, is it possible for us to determine the value of y? If so, what is it?
• Practice this question with other logic gates, and other values of x and z.

 

15. Consider a NAND gate with two inputs x and y and an output z. If x = y, then what can we conclude about z?

 

16. Suppose a machine does 8-bit signed integer arithmetic. Give an example of a computation that will result in overflow. Is underflow possible?

 

17. Draw finite automata that accept these sets of binary strings:
• strings containing 101
• strings ending in 101
• strings that start with 1 and end in 0
• strings of length 3

 

18. Write regular expressions that describe these sets of strings:
    • 5-letter words that start with T
    • words of any length that start with T
    • words containing the letter T
    • words that contain the letter E and end with T

 

19. Suppose that a processor's speed is 2 GHz. Each instruction that executes needs to undergo 5 stages, and each stage takes 1 cycle of CPU time. How many instructions can we execute in 1 microsecond if the machine is:
    • not pipelined?
    • pipelined? (Assume pipeline initially empty & no stalls)

 

20. Explain how the speed of light relates to how fast information can be processed in the CPU, and how fast data can be transmitted over a long distance network. In other words, which orders of magnitude are appropriate?

 

21. The contents of sixteen bytes of data can be described by how many hexadecimal digits?

 

22. Suppose a CPU requires instructions to undergo 4 pipelined stages, and each stage takes 1 cycle. We are about to run a program containing 30 instructions. Five of these instructions are in a loop that iterates 100 times, while the other 25 instructions are not in a loop.
    a. How many (dynamic) instructions does the CPU need to execute?
    b. How many cycles does the program take to run?
    c. How many cycles would the program take if the CPU were not pipelined?
    d. Based on your answer to part (b), how long will the program take to run if the processor speed is 200 MHz?

 

23. The problem-solving procedure typically involves 5 steps. Identify an obstacle that could occur at each step.

 

24. Suppose you are trying to guess a number between 1 and 100 inclusive. Using the binary search strategy, list the guesses you would make if the correct answer is 70. You may assume that after each wrong guess you would be told whether to go higher or lower.

 

25. Given this list of values: [ 9, 2, 5, 4, 8, 3 ], show the steps we perform to sort this list in ascending order if we use each of the following sorting techniques.
    a. bubble
    b. selection
    c. insertion
    d. merge

 

26. Suppose a computer's hard drive contains 10,000 files. Explain how these files can be organized into folders in such a way that no folder contains more than 20 folders or files.

 

27. Explain what the following octal permission codes mean. Which ones would be appropriate only for folders and executable files?
    a. 770
    b. 644
    c. 400
    d. 754

 

28. Approximately what point size should you request if you want your capital letters to be half an inch tall? Does it matter if you use a sarif, sans sarif or proportional font?

 

29. Suppose a book contains 700 pages. On each page there is typically 500 words of text and an image measuring 600 by 400 pixels and is in full CMY color. In theory, how much memory would be required to store the contents of this book?

 

30. Referring back to the 9-vertex Dijstra's algorithm example we did in class, show the steps of Dijsktra's algorithm assuming we want to travel from the top right vertex (C) to the lower left vertex (G). Do we ever reach a situation along the way when a vertex needs to be relabeled?

 

31. Suppose that you are creating a query in Access that refers to an Author table and a Paper table. How many records will the query return if there is no relationship defined between these two tables?