Welcome!
Here you will see info about what we did in class, upcoming exams, solutions for past exams, etc.,
CHECK AT LEAST ONCE A WEEK!!
COURSE PAGE WITH SYLLABUS, GRADING SCHEME ETC
Started 8/16/2017
Problem numbers from 8th and 7th editions are given. If you need 6th edition numbers let me know.
Friday, Dec 8
Hope you guys have a nice break.
I should be done grading by wednesday.
You are welcome to stop by office any day, in the afternoon.
Sorry about party mix-up.
FINAL EXAM SOLUTIONS
FINAL EXAM DEC 8 FRI, 11AM TO 1PM,
SAME CLASSROOM (DGH 238).
PLEASE STUDY CLASS-NOTES, EXAMPLES IN TEXT, HW PROBLEMS, TESTS AND CHAPTER SELF-TEST PROBLEMS.
I have reloaded the review problems (see below) with solutions.
REVIEW THU DEC 7, 11AM TO 1PM,
ASB-213 (NEAR MY OFFICE)
I WILL BRING UPDATED GRADE SHEET.
WE WILL DO SOME OF THESE
REVIEW PROBLEMS
Wednesday, Nov 29.
TEST 3 SOLUTIONS.
Monday, 11/27/2017
REVIEW PROBLEMS with solutions for selected problems.
You may need to refresh your browser.
Sunday, 11/26/2017
Notes on HW8: I have added comments for chapter 6 problems also.
Notes on HW8.
Friday, 11/24/2017
Notes on HW8: Right now I have written about the RSA problem from 5.4.
Notes on HW8.
Friday, 11/17/17.
Today we discussed to 6.3 , generalized permutations and combinations,
and and 6.5, probability.
ALL HW8 problems:
6.5: 27, 29, 31 (both 8th ed. & 7th ed.).
6.3: 8, 11, 26, 40, 46(8th ed.), 5,8,23,37,43 (7th ed.).
6.2:11,23,40,47,62(both 8th ed. & 7th ed.).
6.1: 20,33,93(8th ed.);17,27,87(7th ed.).
5.4: 3,13 (8th ed.); 3,11 (7th ed.).
6.1: 9(8th ed.); 8 (7th ed.)
6.1 problem 12 (not in 7th ed.):
How many 5 letter strings can be formed from ABCDEFG it should contain
the substring CEG somewhere in that string?
Wednesday, 11/15/17.
Today we discussed to 6.2, permutations and combinations.
More HW8 problems:(more to be added friday)
6.2:11,23,40,47,62(8th ed. & 7th ed.).
Monday, 11/13/17.
Today we continued to discuss Chapter 6, section 1.
If you understand this section well you will find it easier understand the rest of this chapter.
Here are solutions and explanations for some problems from HW7.
Please read them. They will be helpful for the test 3 and final.
More HW8 problems:(more to be added wednesday and friday)
6.1: 20,33,93(8th ed.);17,27,87(7th ed.) .
Wednesday, 11/8/17.
Today we discussed Chapter 6, sections 1.
I also discussed the hw problem from 5.2 involving highest power of 2
dividing n!.
HW8 problems:(more to be added next week)
5.4: 3,13 (8th ed.); 3,11 (7th ed.).
6.1: 9(8th ed.); 8 (7th ed.)
6.1 problem 12 (not in 7th ed.):
How many 5 letter strings can be formed from ABCDEFG it should contain
the substring CEG somewhere in that string?
Monday, 11/6/17.
Today we discussed Chapter 5, sections 3 and 4.
The topics were: Using Euclidean algorithm to write GCD as a linear combination, to find inverses modulo an integer, and the RSA cryptosystem.
Please read completely both the sections, especially the algorithms.
Also try some of the computation problems in the exercises.
Will post hw problems on wednesday.
Friday, 11/3/17.
Today we discussed Chapter 5, section 2 -number systems
HW7 problems are due by wednesday Nov 8 by 4pm.
PLEASE VISIT ME ASAP ---DON'T WAIT UNTIL LAST MINUTE!
Problems (total 10):
5.2: 33,46,60,66(8th ed); 30,43,57,63 (7th ed).
5.3: 34,43 (8th ed.); 32,41 (7th ed.).
5.1: 23, 25 (only for the number in 24) (both 7th and 8th ed.); 38,44 (8th ed.) Not in 7th ed.
38: Let the n-th Fermat number F_n be (2^(2^n))+1. The product of all F_i from i = 0 to n-1
equals (F_n)-2. Using this or otherwise you can show that F_i are relatively prime if i are different. Use this fact to show that there are infinitely many primes.
44: If E denotes even integers, define an E-prime by an even number that cannot be written as a product of two evens. For example, 2 nd 10 are E-primes. Show that 36 can be written as a product of E-primes in two different ways, thus showing that it is not possible to factor even numbers in a unique way using E-primes.
Monday, 10/30/17.
Today we started Chapter 5 -- basic number theory.
HW7 problems (more will be posted later): 5.1: 23, 25 (only for the number in 24) (both 7th and 8th ed.); 38,44 (8th ed.) Not in 7th ed.
38: Let the n-th Fermat number F_n be (2^(2^n))+1. The product of all F_i from i = 0 to n-1
equals (F_n)-2. Using this or otherwise you can show that F_i are relatively prime if i are different. Use this fact to show that there are infinitely many primes.
44: If E denotes even integers, define an E-prime by an even number that cannot be written as a product of two evens. For example, 2 nd 10 are E-primes. Show that 36 can be written as a product of E-primes in two different ways, thus showing that it is not possible to factor even numbers in a unique way using E-primes.
Friday, 10/27/2017
Test II Solutions
TEST 2 on OCT 27, FRI.
Chapters 3 and 4 (only selected topics in chapter 4).
Review problems for test (Please ALSO review homework problems AND class notes):
Chapter III self test:
(8th edition)All except problems 7,13 and 15.
(7th edition) All except problems 2 and 12.
Chapter IV self test:
(8th edition): All except problems 1,2,3,5 and 13.
(7th edition): All except problems 1,4,5,7 and 13.
You can also try these old exams:
NOTE: Our exam will be similar in format but some problems will be on topics different
from those in these exams.
Fall 04 Test II & III selected problems
Fall 06 Test IV
Tuesday, 10/23/17.
Yesterday we talked about estimating the time taken by an algorithm to produce its output as a function of the size of the input.
4.3 practice problems: 7,10, 17, 20, 23 (8th ed.); 7,10,16,19,22 (7th ed.).
Monday, 10/23/17. 9:39am
We will have class today.
Also please check above for details on test on Friday.
Wednesday, 10/18/2017.
NO CLASS ON FRIDAY DUE TO YARDFEST.
Today we wrote pseudocode for couple of algorithms.(4.1)
Please read 4.2 and 4.4 -- they are easy if you understood 4.1.
HW6 is now due by Friday 10/20 by 4pm (instead of tomorrow).
Practice problems for Test 2 (no need to turn in):
4.1: 5,7,12(8th ed.); 4,6,11 (7th ed.).
4.2: 17,22 (8th ed.); 15,20 (7th ed.).
4.4: 9,10,12(8th ed. and 7th ed.).
Write a recursive algorithm to find the n-th Fibonacci number.
Monday, 10/16/2017.
Today we did more problems on relational databases.
HW6 is due by Thursday 10/19 by 4pm.
Please come and discuss it with me asap. I can help you if you have questions.
Friday, 10/13/2017.
Today we discussed the equivalence relation given by congruence (remainders mod an integer), matrices of relations (3.5) and relational databases (3.6),with examples.
HW6 is due by 4pm Thursday 10/19:
3.6: (7th ed. and 8th ed.) 12,15.
3.5: (7th ed. and 8th ed.) 17,19.
3.4 problems: (7th ed.) 10,23,25,27,36,40;
(8th ed.) 12,25,27,29,39,43.
Wednesday, 10/11/2017.
Today we discussed the equivalence relations and partitioning of sets into disjoint subsets of equivalence classes, with examples..
HW5 is due by 4pm tomorrow.
HW6: (more will be posted friday)
3.4 problems: (7th ed.) 10,23,25,27,36,40;
(8th ed.) 12,25,27,29,39,43.
Monday, 10/9/2017.
Today we discussed the inverse of a relation, composition of relations, partial and total orders and equivalence relations.
HW5 is due by thursday 10/12 by 4pm.
Please come and discuss it with me asap. I can help you if you have questions.
Friday, 10/6/2017.
Notes on Summation by Parts.
Probems: 3.2:(8th ed.) 15,17,82,84,112,128,147;(7th ed.) 9,11,76,78,86,102,121.
3.3: (8th ed.) 31,35,37; (7th ed.) 28,32,34.
Wednesday, 10/4/2017.
HW4 due by 4pm tomorrow.
Today we talked more about sequences, their notation, change of index
and summation by parts.
HW5: (8th ed.) 15,17,82,84,112,128,147
(7th ed.) 9,11,76,78,86,102,121.
More problems will be posted friday.
Monday, 10/2/2017.
Today we discussed the floor and ceiling functions, sequences, their notation
and some special sequences such as arithmetic, geometric and telescoping sequences.
Friday, 9/29/2017
Today we discussed Euclidean algorithm, check digits and discrete logarithms.
HW4: due thursday Oct 5 by 4pm; Please don't wait for last minute.
3.1: (from wednesday) 9, 34,51,64, 74 (8th ed.) ;2,27 ,40,52,56 (7th ed.)
Added today: 5.3: 9,17 (8th ed.) ; 9,15 (7th ed.).
3.1: 62, 67,70(8th ed.); 50 (7th edition).
3.1 problems 67 and 70 are not in 7th edition.
They are below. For both check if the ISBN's have the correct check digit.
First read problem 54 for the definition of check digits.
3.1.67: 978-0-8108-8139-2.
3.1.70: 978-1-4354-6028-7.
Wednesday, 9/25/2017
Today we discussed iterative processes and iterations of functions.
We watched part of a video about fractals.
Here is another iterative process, this time resulting in the
Sierpienski Triangle, similar to the process I described in class for the square.
We also talked about Collatz conjecture (google it!), random number generation and hash functions.
No new hw problems today.
Monday, 9/25/2017
Today we discussed 3.1 ; basic properties of functions.
We also gave examples of different types of functions.
We also started modular arithmetic.
HW4 problems: 3.1: 9, 34,51,64, 74 (8th ed.) ;2,27 ,40,52,56 (7th ed.)
Friday, 9/22/2017
Test I Solutions
TEST I FRIDAY SEP 22 ; ALL OF CHAPTERS 1 & 2 (BOTH 7TH & 8TH ED) EXCEPT RESOLUTION PROOFS AND ARGUMENTS AND RULES OF INFERENCE
Review problems for test (Please ALSO review homework problems AND class notes):
Chapter I self test:
(8th edition)1,2,3,4,5,6,8,12,13,14,15,16,17,18,19,22,23,24.
(7th edition) All except problems 9 to 18.
Chapter II self test:
(8th edition): All upto 16.
(7th edition): All except problems from 2.3.
You can also try these old exams:
Our exam will be similar in format but some problems will be on topics different
from those in these exams.
Fall 04 Test I (all except 4b and 5)
Fall 06 Test I (all except 7)
Tuesday, 9/19/2017
I have uploaded some old exams of mine. See above
Our exam will be similar in format but some problems will be on topics different
from those in these exams.
Monday, 9/18/2017
Today we did problems using proof by strong induction.
Please look at review problems for test posted above
HW3 can be submitted wednesday by 4pm.
Please try the following problems from 2.4 and 2.5 for practice.
They don't need to be submitted.
2.4: (8th ed.) 1,5,13,19,22,28,45; (7th ed.) 1,5,12,18,21,27,42
2.5: (8th ed.) 1,7,10 ; (7th ed.) 1,6,11.
Please study this paper by Kei Nakamura to learn about Fibonacci numbers and using induction to prove their properties.
Friday, 9/15/2017
Today we did more problems using proof by induction.
Please look at review problems for test posted above
HW3 can be submitted wednesday by 4pm.
Wednesday, 9/13/2017
Today we talked about proofs by cases and started proof by induction.
No new HW problems but I encourage you to try as many problems from book on induction as possible.
Problem 2.4.17 (2.4.16 in 7th ed.) is quite interesting and slightly more challenging.
Monday, 9/11/2017
Today we talked about methods of proofs, including proof by contradiction and by example.
HW3 (total 10 problems; due on or before monday 5pm in office):
Problems 7 to 10:
8th edition: 2.2: 33,38,48,52.
7th edition: 2.2: 28,33,43,47.
If anyone needs 6th edition problems, email me.
Friday, 9/8/2017
Today we talked about Proofs and methods of proofs, including direct proof,
proof by contradiction and by contrapositive.
Notes from today's class.
HW3 (more to be given monday):
8th edition: 2.1: 12,19,34 ; 2.2: 3,21,28.
7th edition: 2.1: 12,17, 32; 2.2: 3,18,23.
If anyone needs 6th edition problems, email me.
Wednesday, 9/6/2017
Today we talked about hw2.
There are 10 problems below. Please work on them asap.
Stop by my office if you need help.
They should be presented by 5pm next wed, 8/13.
Friday, 9/1/2017
Today we talked about Nested Quantifiers.
Updated and edited notes from today's class.
It also includes solution to problem 66 in section 1.1 (sets).
HW2 problems (we will discuss hw2 on wednesday).
Please try them over the break.
Section 1 (Sets : 1.1 in 7th, 2.1 in 6th ed.)
1.1.56: Draw a Venn diagram and shade the region representing
B∩(C∪A)' where the second set is the complement of C∪A.
1.1.67: (see notes from today for example problem) In a group of students each is taking a math or computer course or both. 1/5th of those taking a math course are also taking computer, and 1/8th of those taking a computer course also taking math. Are more than 1/3rd taking a math course?
Section 1.6 (Nested Quantifiers ; 1.4 in 6th ed, 1.6 in 7th).
1.6.35: Let L(x,y) be the function "x loves y." If P is set of all living people then domain of discourse is P x P. Write the statement "Everybody loves somebody" symbolically.
1.6.50: Determine the truth value of ∃x∀y(x^2 < y+1) if domain of discourse is R x R.
1.6.73: Given domain of discourse is R x R x R determine whether the following statement is true or false: ∀x∃y∃z ((x < y) →((z > x)∧(z < y)).
Wednesday, 8/30/2017
Today we talked about Quantifiers.
Notes from today's class.
HW2 problems (more will be added friday):
Section 1 (Sets / specifically section on Cartesian products)
1.1.73: If X = {1,2}, Y = {a}, Z = {α, β} list the elements of X x Y x Y.
1.1.79: Give a geometric description of ZxZ.
Section 5 (Quantifiers)
1.5.29: Write ∃x(Not(P(x)) using only negation, AND and OR symbols given that D = {1,2,3,4}
1.5.41: Given that D = {people}, P(x) is " x is a professional athlete" and Q(x)
is "x plays soccer" determine the truth value of ∀x(Q(x) → P(x)) and write it in words.
1.5.49: Given that D = {people}, P(x) is " x is an accountant" and Q(x)
is "x owns a Porsche" write"Some accountant owns a Porsche" symbolically.
Monday, 8/28/2017
Today we mainly went over the homework I that is due by friday.
Please come to my office any day this week between 2 and 3pm with
completed hw.
Friday, 8/25/2017
Today we talked about Basic logical statements and De Morgan's law.
Please read the following Notes from today's class. I have included more details including answers for the questions.
Please note that the section numbers below are for 6th edition of textbook.
The order of the sections are a bit scrambled in the newer editions.
I hope to have the latest edition soon.
Also I did not cover Truth tables in class because they are quite easy.
Please read and use truth tables when necessary (indicated in problem below).
Also read definitions of converse, sufficient condition and necessary condition.
Homework problems from 1.2 for today (will discuss some of the HW on monday):
Write the following statements as conditional propositions. Also write their converses, contrapositives:
1.2.3: A necessary condition for Fernando to get a computer is that he gets 2000 dollars.
1.2.6: The audience will go to sleep if the chairperson lectures.
1.2.44: Using truth tables, check whether the following are logically equivalent: The statements "p -> q" and "(Not p) OR q"
Wednesday, 8/23/2017
Homework 1 problems: (more will be added friday)
1.1, 3. Write the negation of "For some positive integer n, 19340 = 17n"
1.1, 17
(Given p is F, q is T, r is F, is the statement (NOT(p OR q))AND(NOT(p) OR r) true?)
1.1, 51: Write symbolically: You did not hear "Flying pigs" rock concert (p is F) and you did not hear Y2K concert (q is F) but you have sore eardrums (r is T).
Monday, 8/21/2017
Notes from today's class
Please read the following to get started on the course:
Note on Russell's paradox
This note contains its definition, history, an example using web search principles, and the Barber of Seville example. I compiled it from various web-sites