UIT2201: CS & the IT Revolution
Review Topics for Quiz 1 (Fall 2003)

Here are some general information on Quiz 1 (for your reference).

The Quiz, the Questions:

The questions will be similar to those in the tutorials and the notes. But, not so long.
(There will be a fun bonus-mark question.)

Topics Covered:

  1. Everything covered until Week 8 (last class - 3 Oct)
  2. Lectures (including handouts given out in class),
  3. Tutorials (all problems except A-problems),
  4. Textbook [SG] Chapters 1-3; Ch. 4 (up to Ch 4.4.2)

Some Review Questions (RQ):

Some sample question for your reference. Of course, there is no guarantee that all the Quiz questions are like that. This is for reference only!

RQ-0 Review all the tutorial problems given to you.

RQ-1. [True/False] For each of the following, answer TRUE or FALSE.

  1. A repeat-until loop can execute 0 times.     _________
  2. One fundamental virtue of an algorithm is that if we can specify an algorithm for solving a problem, then we can implement the algorithm and have a very fast (and so practical) solution of the problem since computers are very fast computing machines.     _________
  3. Whether or not an operation is a primitive depends, in part, on the computing agent that is expected to execute it.     _________
  4. Computer science work was done before the electronic computer was invented.     _________

RQ-2. (Short Answers)

  1. Give the definition of computer science as given in the textbook [SG].
  2. Determine if the following are unambiguous, effectively computable operations. Explain your reasoning for those that are not effectively computable.
    1. Read in the value of n;
    2. Check if X equals Y.
    3. List the positive, odd integers greater than 2201.

RQ-3. At the beginning of the course, we have seen several very diverse computing devices that come from different domains. These includes email, ATM machine, course enrolment, online library search, MP3 music access, 3-D walkthrough.

  1. What are some of the common capabilities of all these diverse and different computing devices.
  2. Compare and contrast them with respect to these common capabilities.

RQ-4. Modify the algorithm of Figure 2.10 (the "Find Largest Algorithm) so that it computes the number of occurrences of the value x in a list of n numbers.

RQ-5. Explain how the popular outdoor game of scavenger hunt can be defined recursively. Remember to also include the base case.

RQ-6. Describe the best case input of the sequential search algorithm. How many comparisons are required in a search of n items in this case?

RQ-7. Describe the Worst case input for an unsuccessful search using the sequential search algorithm. How many comparisons are required in a search of n items in this case?

RQ-8. For what input sizes n is an algorithm (A) that does 50n units of work slower than an algorithm that does 2n2 units of work.

UIT2201: CS & IT Revolution; (Fall 2003); A/P Leong HW