This chapter includes contents: Mathematical review; asymptotic and algorithm analysis; relationships and data structures; requential storage: Lists, queues, stacks, deques; hash tables; trees; priority queues and heaps; sort algorithms; graphs and graph algorithms; algorithm design techniques; complexity classes and NP completeness. | (CSC 102) Lecture 11 Discrete Structures Previous Lectures Summary Rational Number Irrational numbers Absolute values Triangular inequality Modular Arithmetic Floor and Ceiling Today’s Lectures Summary Floor and Ceiling Properties of Floor and Ceiling Functions Methods of Proof Direct Proofs Examples Compute and for each of the following values of x: 25/4 − Solution: 25/4 = and 6 < < 7; hence b. 0 < < 1; hence . c. −3 < − < −2; hence The 1,370 students at a college are given the opportunity to take buses to an out-of-town game. Each bus holds a maximum of 40 passengers. For reasons of economy, the athletic director will send only full buses. What is the maximum number of buses the athletic director will send? b. If the athletic director is willing to send one partially filled bus, how many buses will be needed to allow all the students to take the trip? Example General Values of Floor Solution: Cont Is the following statement true or false? For all real Numbers x and y, Solution: The statement is false, take x = y = 1/2, then Hence Theorem: For all numbers x and all integers m, Proof: Suppose a real number x and an integer m are given. Let n = that unique integer n such that, n ≤ x < n + 1. Add m to all sides to obtain n + m ≤ x + m < n + m + 1. Now n + m is an integer and so, by definition of floor, But n = . Hence by substitution Properties of Floor Theorem: Proof: Suppose n is a integer. Then either n is odd or n is even. Case 1: in this case n = 2k+1 for some integers k. Cont . also. Since both the left-hand and right-hand sides equal k, they are equal to each other. That is, Case 2: In this case, n = 2k for some integer k. Since k=n/2 by the definition of even number. So Cont Methods of Proof Proof A proof is a logically structured argument which demonstrates that a certain proposition is true. When the proof is complete, the resulting proposition becomes a theorem, or if it is rather simple, a lemma. Direct Proofs Theorem . | (CSC 102) Lecture 11 Discrete Structures Previous Lectures Summary Rational Number Irrational numbers Absolute values Triangular inequality Modular Arithmetic Floor and Ceiling Today’s Lectures Summary Floor and Ceiling Properties of Floor and Ceiling Functions Methods of Proof Direct Proofs Examples Compute and for each of the following values of x: 25/4 − Solution: 25/4 = and 6 < < 7; hence b. 0 < < 1; hence . c. −3 < − < −2; hence The 1,370 students at a college are given the opportunity to take buses to an out-of-town game. Each bus holds a maximum of 40 passengers. For reasons of economy, the athletic director will send only full buses. What is the maximum number of buses the athletic director will send? b. If the athletic director is willing to send one partially filled bus, how many buses will be needed to allow all the students to take the trip? Example General Values of Floor Solution: Cont Is the following statement true or false? For all real
