COT 3100 Sect. #7094X (Fall 1999)
Homework Assignment #3:
Functions, Summations, Orders of Growth
Assigned Mon. 9/13, Due at the start of class Fri. 9/24

All problems are taken from the textbook (Rosen), §1.6-1.8. You should also practice the odd-numbered problems in those sections, whose solutions you can check in the back of the book, or review in more detail in the student solutions guide. Practicing other even-numbered problems may also help you. Each assigned book exercise is worth 1 point out of a total of 15. (Or ~6.67% out of 100%.)

We are still using the same optional collaborative homework policy that we used in the previous assignments. (Group work is permitted, if you turn in a joint assignment.)

The indicated extra credit exercises are each worth 1 extra point out of the 15, up to a maximum score of 100%. (This time you cannot do just any problem for extra credit.)

Exercises from §1.6, pp. 67-69. (Functions)

Ex. 4 - Find the domain and range of some functions.
Ex. 14 - Identify numeric bijections.
Ex. 28 - Compute inverse images of some finite & infinite sets.
Ex. 42 - Use floor/ceiling to express a quantity.
Ex. 52 - Draw the graph of a function.
Extra credit:
Ex. *20 - Prove a fact about composition and injectivity.
Ex. 56 - Prove a fact about composition & inversion.
Ex. 58 - Prove a fact about cardinality, injectivity, and surjectivity.
Ex. 60 - Represent partial functions with total functions.
Exercises from §1.7, pp. 78-80. (Sequences & Summations)
Ex. 14 - Compute summations over sets.
Ex. 18 - Compute nested summations over ranges.
Ex. 20 - Compute a telescoping sum.
Ex. 28 - Use product notation to express factorial.
Ex. *38 - Show that the rationals are countable.
Extra credit:
Ex. *12 - Show that a sequence rule corresponds to a given closed formula.
Ex. *22 - Compute a difficult telescoping sum.
Ex. *26 - Find a closed-form equivalent of a summation.
Ex. *40 - Show that the real solutions to quadratic equations with integer coefficients are countable.
Exercises from §1.8, pp. 90-92. (The Growth of Functions)
Ex. 2 - Identify some O(x²) functions.
Ex. 6 - Prove an O() relationship.
Ex. 28 - Concretize and illustrate a Theta() relationship.
Ex. 30 - Explain Omega(1).
Ex. 34 - Show that all log orders are the same.
Extra credit:
Exercises 8, 20, 22, 26, 32, 36, 60, 62. (1 point ea.)

COT 3100 Sect. #7094X (Fall 1999) Homework Assignment #3: Functions, Summations, Orders of Growth Assigned Mon. 9/13, Due at the start of class Fri. 9/24

COT 3100 Sect. #7094X (Fall 1999)
Homework Assignment #3:
Functions, Summations, Orders of Growth
Assigned Mon. 9/13, Due at the start of class Fri. 9/24