IST 230 MIDTERM | Complete Solution

Chapter 1

1. Tell whether the following two statements are equivalent by constructing their truth tables in canonical form; you must explain your answer; you need not exactly follow the template below:Is logically equivalent to ?

Chapter 2

1. Define the sets X = {a, b, c} and Y = {1, 2}. Show the set X × Y by listing the elements with set notation.

Chapter 3

1. Express 2²+2³+2⁴+2⁵+2⁶+2⁷+2⁸ using summation notation.

Chapter 4

1. Simplify the Boolean expression: .

Chapter 5

1. Create a relation on the set {1, 2, 3, 4} that is reflexive and transitive. You may display your answer as an arrow diagram, matrix, or set of ordered pairs.

1. The table below shows the database of course offerings for the Computer Science Department for the current academic year. It's actually just a portion of the course offerings, but for the purposes of this question, assume it lists all the courses.

Course number

Course title

Instructor

Quarter

CS 111

Digital Image Processing

Majumder

Spring

CS 112

Computer Graphics

Majumder

Spring

CS 117

Project in Computer Vision

Fowlkes

Fall

CS 116

Computational Photography & Vision

Fowlkes

Winter

CS 122A

Introduction to Data Management

Carey

Spring

CS 122A

Introduction to Data Management

Li

Winter

CS 122C

Principles of Data Management

Carey

Winter

1. Give a key for this database.
2. Show the results of the operation SELECT[Course number = "CS122A" ∨ Course number = "CS122C"]
3. Show the results of the operation PROJECT[ Instructor ]
4. Show the results of the operation SELECT[Quarter="Spring"] followed by Project[Course number]. Express in English what question this combination of queries is asking.
5. What operation or operations should be performed if you wanted to know which quarters CS 122A is being offered?
6. What operation or operations should be performed if you wanted to know which courses are being taught by Prof. Majumder?

Chapter 6

1. Write an algorithm in pseudo-code with the following input and output:

Input: a₁, a₂,..., a_n, a sequence of numbers.

Output: The largest number in the sequence.

1. Write the output for the following psuedocode:

                count :=0

                For i= 1 to 2

                                For j=1 to 3

                                                count :=count+i*j

                                End-for

                End-for

Chapter 7

1. Find the first four terms of the recursively defined sequence , for all integers , where .
2. Prove the following conjecture using Mathematical Induction:

Proof: