---

UIT2201: CS & the IT Revolution
Review Topics for Quiz 1 (Spring 2010)

---

The Quiz, the Questions:

---

Topics Covered:

1. Topics 1-3 (excluding "Concurrency");
2. Everything covered until Week 7 (T1-T6, last tut class - 05 Mar)
3. Textbook [SG] Chapters 1-3; Ch 13.3 (excluding 3.4.1, pp.99-105)
4. Lectures (including handouts given out in class),
5. Tutorials (all problems except A-problems),

---

Some Review Questions (RQ):

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.     _________
5. It is theoretically possible to build a decimal computer -- that is, a computer that uses decimal numbers internally.     _________
6. If different people construct a truth table from the same circult diagram, they will always get the identical truth table (as long as it is correctly done).     _________
7. A tuple consists of a row of attributes.     _________
8. There should not be more than one table (relation) in a database.     _________

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.

3. How do we define a database?

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. (Not applicable for Spring 2010) 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 2n² units of work.

RQ-9. Give an example of a linear time algorithm, namely, an algorithm that has time complexity O(n), where n is the input size.

RQ-DB1. Consider the database schema given in Lectures. Given the following sequence of SQL statements:

   T1 <-- SELECT from ENROLMENT where (COURSE-ID="NN")
   T2 <-- JOIN T1 and STUDENT-INFO 
             where (STUDENT-INFO.Student-ID = T1.Student-ID)
   T3 <-- SELECT from T2 where (Faculty="FASS")
   A  <-- PROJECT T3.Name from T3;