CSE 20

Top

Top

The textbook for this course is

The full pdf of the book is available for free download from a UCSD internet connection at:

• http://link.springer.com/book/10.1007%2F978-1-4471-4069-6

You may want to print out the relevant chapters for easy reference. A paperback version on this material is available from SpringerLink for about $25 (on-campus) or $40 (off-campus). Amazon sells the book for about $50.

Top

Class Meetings

Top

Typically, homework is due via Ted by 5pm Monday evening. The weekly reading quizzes are due by 5pm Friday evening.

NOTE: Subject to change throughout the quarter.

Top

Homework

• Homework 7, due 12/8. Reading: JS Chapter 6.1-6.4
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  0. Warmup exercises (do not hand in): JS 6.2b, 6.5, 6.6, 6.7, 6.8a
  
  
  1. Over the set of real numbers, define the relation R to be xRy if and only if x-y is an integer. Prove that this relation is an equivalence relation and describe its equivalence classes.
  
  
  2. 1. For every positive integer n, prove that if n is not divisible by 3, then n^2 MOD 3 = 1.
     2. For every positive integer n, prove that if n is odd, then n^2 MOD 8 = 1.
     3. [Bonus:] Use the first two parts to prove that if p is a prime integer greater than 3, then (p^2 -1) is divisible by 24.
  
  
  3. On page 240 in the book, the authors note that the subset relation is a partial order. Prove that, indeed, for any set A, if X, Y,Z are subsets of A, and X is a subset of Y and Y is a subset of Z, then X is a subset of Z. (Hence, the subset relation is transitive.)
  
  
  4. [JS 6.8b] Suppose that R is an order relation on a set S. Prove the following: If q is a minimum element of S, then q is minimal. Hint: use the definition of minimal and minimum on page 242.
  
  
  5. Consider the set of binary strings of length less than or equal to 3: { λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111 }.
     1. Draw the Hasse diagram of the prefix relation on this set. Recall (page 247) that a string x1...xm is a prefix of a string y1...yn if and only if m <= n and xi=yi for i=1,2,...m. You may draw the diagram by hand and incorporate a scan/ photo of it in your submitted document.
     2. Write out the elements of this set in lexicographic order.
  
  
  6. [ Bonus ] Look up the definition of a topological sort (also known as a linear extension) of a partial order. State the definition in your own words. Then, explain how you would generate all possible topological sorts of a finite partial order.
• Homework 6, due 12/2. (Note unusual day) Reading: JS Chapter 3.6, 6.1, 2.1, 2.2, beginning of 2.3
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  0. Warmup exercises (do not hand in): JS 6.1 b, 6.1c , 6.2a.
  
  
  1. Consider the function on binary strings defined recursively as .
     Prove that for any binary strings s,t ones(st) = ones(s)+ones(t). Hint: prove by induction on the length of t.
     Notes: the domain of the function ones(s) is the set of binary strings. The codomain of the function ones(s) is the set of nonnegative integers. The "+" in the recursive definition is addition of integers. So, for example,
     ones(11010) = ones(1101) = ones(110)+1 = ones(11) + 1 = ones(1) + 2 = ones(lambda)+3 = 0 + 3 = 3.
  
  
  2. Consider the domain S = { 00, 01, 10, 11 }.
     1. Give an example of a relation that is reflexive and transitive but not symmetric. Justify your example.
     2. Give an example of a relation that is anti-symmetric and not transitive. Justify your example.
  
  
  3. We consider several functions each of whose codomain is the set of nonnegative integers. For each of the following functions, (i) find its domain, then (ii) decide whether the function is one-to-one (and prove your answer), and (iii) decide whether the function is onto (and prove your answer).
     1. The function that assigns to each pair of positive integers the maximum of these two integers.
     2. The function that assigns to each positive integer the number of the digits 0,1,2,3,4,5,6,7,8,9 that do not appear as digits in the decimal representation of the integer.
     3. The function that assigns to a binary string the numerical position of the first 1 in the string and that assigns the value 0 to a bit string consisting of all 0s.
  
  
  4. For n and k positive integers with k<=n, how many binary strings of length n contain k 1's? Hint: list out all the strings for small values of n and k; can you relate this question to one about subsets and counting sets of certain sizes?
     An example for n=5, k=2. The binary strings of length 5 which contain (exactly) 2 ones are: 11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011. So, for these values of n, and k, the number of binary strings of length 5 which contain 2 ones is 10.
  
  
  5. Consider the set A = {1,2,3}. Describe (i.e. find, define) a bijection between the set X of subsets of A with an odd number of elements and the set Y of subsets of A with an even number of elements. Note: it is possible to generalize this observation to prove that every nonempty set has the same number of subsets with an odd number of elements as it does subsets with an even number of elements.
  
  
  6. [ Bonus ] Find an error in the "proof" of the following "Theorem".
     
     "Theorem": Let R be a relation on a set A that is symmetric and transitive. Then R is reflexive.
     "Proof": Let a be an element of A. Take an element b in A such that aRb. Because R is symmetric, we also have that bRa. Now using the transitive property, we can conclude that aRa, because aRb and bRa. Thus, we have proved that each element of A is related to itself via R and hence R is reflexive.
     Can the error be fixed (in other words, is the statement of the "Theorem" true)? If so, fix it. Otherwise, prove that the statement of the "Theorem" is false.
• Homework 5, due 11/17. Reading: JS Chapter 3
  
  A note on the reading: Chapter 3 contains a lot of information. Here is a quick guide of what we're covering now, what we'll be eventually covering in this course but not yet, and what we're saving until CSE21.
  • Section 3.1 The Greedy Algorithm and Three Cookie Problems: this section is mostly for motivation. You are not expected to have a thorough understanding of the greedy method or the terminology of transversals, etc.
  
  
  • Section 3.2 Boolean Expressions and Truth Tables: this section is absolutely critical and we spent quite a bit of time covering the material here. In particular, you should be extremely comfortable with the definitions of the Boolean operators, with truth tables, and with proving equivalence / nonequivalence of compound Boolean expressions.
  
  
  • Section 3.3 Predicates and Quantifiers: again, this is foundational material that you must be familiar with. Make sure you understand the meaning of and differences between universal and existential quantifiers and are able to translate from English to symbolism and vice versa.
  
  
  • Section 3.4 Valid Arguments: While we don't often work at the level of formality of this section, you should be familiar enough with the standard argument forms to apply them in proofs.
  
  
  • Section 3.5 Examples of Proofs: This section has good examples of worked proofs and additional proof strategies (proof by cases, direct proof, contrapositive proof, indirect proof. Particularly useful examples include Theorem 3.5.2, Theorem 3.5.3, Theorem 3.5.4, Theorem 3.5.5, and Theorem 3.5.7. NOTE: Subsection 3.5.3 covers material about sizes of (infinite) sets that we will only look at near the end of the quarter.
  
  
  • Section 3.6 Mathematical induction: We will be spending all of this week on this section (and related proofs in section 3.7).
  
  
  • General comment: while we might briefly define them, the binomial coefficients and the Binomial Theorem will be discussed in much greater depth in CSE21.
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  0. Warmup exercises (do not hand in): JS 3.13, 3.14, 3.21
  
  
  1. Prove the following formula (for n a positive integer) by mathematical induction: .
  
  
  2. [JS 3.20] Find a formula for the sum .
     Use Mathematical Induction to prove that your formula is correct for all positive integers n.
  
  
  3. At time 0, a particle resides at the point 0 on the real line. Within 1 second, it divides into 2 particles that fly in opposite directions and stop at distance 1 from the original particle. Within the next second, each of these particles again divides into 2 particles flying in opposite directions and stopping at distance 1 from the point of division, and so on. Whenever particles meet they annihilate (leaving nothing behind). How many particles will there be at time 2^11 -1? Justify your answer. Hint: Derive a formula for the number/ locations of particles at time 2^n-1 for arbitrary positive integer n, prove the formula using induction, and apply it when n=11.
  
  
  4. Prove that for any integers x,y there are integers a,b such that gcd(x,y) = ax + by. You may use Theorems and proofs from the textbooks, so long as you refer explicitly to what you're using and on which page it may be found.
  
  
  5. [JS 3.24] A non-recursive Square and Multiple Algorithm to calculate b^n.
     Precondition: n is a positive integer and b is of any type that can be multiplied.
     Postcondition: the value returned is equal b^n.
     The algorithm (as on p. 129) is:
     
     .
     
     1. [Warm-up: do not hand in] Walk through the algorithm with n=53 (using the column headings suggested in the textbook).
     2. [Warm-up: do not hand in] Walk through the algorithm with n=710 (using the same column headings.)
     
     
     3. In this part, you will prove rigorously that the algorithm always terminates by proving that the body of the while-loop is executed exactly many times.
        Let n (a positive integer) and b be the inputs and denote by a_k the value of a after the k-th iteration of the while-loop. Prove by mathematical induction on k that For any nonnegative integer k, after k iterations of the while-loop, 2^(s-k) <= a_k < 2^(s-k+1), where s=. Explain why this statement guarantees that the number of times that the body of the while-loop is executed is exactly s.
     
     
     4. In this part, you will prove rigorously that the algorithm correctly outputs b^n (namely, that the postcondition is met). Let n (a positive integer) and b be the inputs. Use mathematical induction on k to prove for any nonnegative integer k, after k iterations of the while-loop, (square)^a * (product) = b^n. Explain why this statement guarantees that the output value of the algorithm is b^n.
  
  
  6. [ Bonus ] In your own words, explain the connection between the well-ordering principle and mathematical induction.
• Homework 4, due 11/10. Reading: JS Chapter 3
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  0. Warmup exercises (do not hand in): JS 3.1, 3.2, 3.3,
  
  
  1. True or false? For any sets X,Y if the power set of X equals the power set of Y, then X=Y. (Justify your answer. In particular, include an analysis of the logical structure of this sentence and discuss which proof strategy you're using.)
  
  
  2. (JS 3.4) Prove that the smallest proper divisor of an integer n>1 must be prime. (Hint: formalize the statement to clarify what "smallest proper divisor" means.)
  
  To start you off on Questions 1 and 2, here are some hints and strategies: pdf
  
  
  3. Let a and z be positive integers and suppose that no prime number b (2<=b<=a) divides z. Prove that no composite number in this range divides z either.
  
  
  4. (JS 3.6) Disprove each of the following assertions:
     1. n^2 + n + 41 is prime for every positive integer n.
     2. the product of any two irrational numbers is irrational.
     3. the product of any rational number and any irrational number is irrational.
  5. A hash table is a data structure for storing items in memory. It can be thought of as a sequence of n data locations (indexed 0, 1, ..., n-1) in which items are to be inserted as they arrive. [Feel free to read more background about hash tables online.]
     
     In one implementation of hash tables using open addressing, the location in which an item is stored is computed by first finding a candidate address for the item, checking if it's available, and, if it is not (this is called a collision), trying again at the address k locations later (where k is a fixed positive integer). If this brings you past the last location in the table, you "wrap around" to the beginning" and keep checking locations k spots apart until find a vacant one.
     
     Designing a hash table means choosing its size (n) and the number of spots that are skipped each time (k).
     1. If a hash table has size n=14 and k=5, and address spots 1,2,6,8,10 are already filled, where will a new item be stored if the first candidate address we check for it has address 1? (Justify your answer.)
     2. Two positive integers are relatively prime if their greatest common divisor is 1. Prove that if x is prime and y is not a multiple of x, then x and y are relatively prime.
     3. Ideally, we want n and k to have the property that if any address in the hash table is vacant, we will eventually find it. Show that if n and k are not relatively prime, then repeatedly skipping k locations will not reach all possible locations.
     
     
  6. [Bonus] Look up and describe two specific uses of hash functions / hash tables in applications. As usual, you must cite any and all references you use.
• Homework 3, due 11/3. Reading: JS Sections 3.2, 3.3, 2.1, 2.2
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  1. A set of Boolean operators is called complete if it is possible to express an equivalent of any compound Boolean expression with only the operators in the set.
     1. Show that the set { ^, V, ~ } is complete. Illustrate your translation procedure on the compound Boolean expression .
     2. Determine whether each of the following sets of operators is complete, and justify your answers.
        1. { ^, ~}
        2. { ^, v}
        3. { nand } , where nand is a binary Boolean operation defined by "p nand q" = ~(p ^ q).
  
  
  2. The unique existential quantifier (written as an existential quantifier followed by !) has the following interpretation: is true means "there is a unique x in the domain such that P(x) is true", or equivalently, "there is exactly one x in the domain such that P(x) is true." Show how to write an expression with ordinary quantifiers (and the equal sign) that is equivalent to .
  
  
  3. Define the following predicates whose domain is the set of strings: P(w) means "w is a string of length 2", Q(w) means "w starts and ends with the same letter", and R(v,w) means "v and w start with the same letter." Translate the following symbolic statements into English, and determine whether they are true or false (explain your reasoning!):
     1. 
     2. 
     3. 
     Note: writing one string after another denotes concatenation. For example, if u=ab and v=ba then uv=abba. Also, note that the symbol plus with a circle around it denotes XOR. Finally, the Greek letter "lambda" denotes the empty string.
  
  
  4. Let C be the set {0,1,..., 15}. Let D be a subset of C and define the number f(D) to be: f(D) is the sum, for every element i of D, of 2^i. For example, if D is {1,6} then f(D) = 2^1 + 2^6 = 66.
     1. What are f(emptyset), f({0,2,5}), and f(C)?
     2. Is there a D such that f(D) = 666? If so, find it. If not, explain why not.
     3. Explain why, if D and E are any two subsets of C such that f(D) = f(E), then D=E.
  5. (The Russell Paradox) Suppose that the data type thing were defined so that every set of thing elements was itself another thing. Define the set R to be {x : x is a set and x is not a member of x}.
     1. Explain why , {1}, and {1,{1}} are elements of R.
     2. Explain why the set of all thing elements, given our assumption, is not an element of R.
     3. Is R a member of R? Explain why both a "yes" and a "no" answer to this question are impossible
  
  
  6. [Bonus] Russell's paradox led to the development of axiomatic set theory. Look up Zermelo-Fraenkel set theory and explain in your own words at least three of the basic axioms. Cite all references you use.
• Homework 2, due 10/20. Reading: JS Sections 1.3, 3.2.
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  0. Warmup exercises (do not hand in): JS 3.9, 3.10
  
  
  1. Balanced ternary
     There are 10 types of people in the world: those who know ternary, those who don't, and those who think this is a binary joke. It turns out that the use of positive digits in positional representation of numbers is common, but not at all necessary. A variation on ternary numbers (base 3), called balanced ternary uses three symbols (aka "trits"):
     • + (the plus sign) represents +1
     • 0 represents the zero digit, as usual
     • - (the minus sign) represents -1
     This leads to an unambiguous representation using the same power-of-three columns as ordinary ternary numbers. For example, +0-+ can be evaluated, from right to left, as +1 in the ones column, -1 in the threes column, 0 in the nines column, and +1 in the twenty-sevens column, for a total value of 1*1 - 1*3 + 0*9 + 1*27, which is 25 {10}.
     
     It turns out that this representation has a number of useful properties that turn out to be missing in 2's complement binary representation: a) The negative of a number in balanced ternary is obtained by interchanging 1 and -1; b) The sign of a number is given by its most significant nonzero “trit,” and in general we can compare any two numbers by reading them from left to right and using lexicographic (decimal) order, as in the decimal system; c) The operation of rounding to the nearest integer is identical to truncation (i.e., deleting everything to the right of the radix point). (You do NOT need to prove these properties ... but you're welcome to think about why they're true.)
     
     Describe an algorithm for converting numbers from decimal representation to balanced ternary representation. Your algorithm may be described either in English or in pseudocode. In addition to the algorithm, include one or two sentences about why and how it works; in particular, informally explain (1) why your algorithm terminates, and (2) why it always gives the correct output. (Hint: think recursively.)
     
     
  2. The Intel x86 chip lists the speed of processor instructions based on speed per instruction:

     Instruction	Latency	Throughput
     ADD/SUB -- add or subtract	1	2.5
     AND/OR/XOR -- bitwise logical operations	1	2
     SHL/SHR -- shift left or shift right	1	1.7
     MUL -- multiply	11	0.5
     DIV -- integer division	80	1/34

     The take-away message from the table is that, in processors, shifts, ands, ors, additions, and subtractions are much faster than multiplying, dividing, and mod. Given this, what is a way to compute the following functions using only combinations of the fast operations (shift, and, or, xor, addition, subtraction)? (Recall the instructions about what we expect from complete answers.)
     1. N * 7
     2. N * 17
     3. N % 16
     4. - N (where negative uses one's complement)
     5. - N (where negative uses two's complement)
     (You may assume that all numbers N are represented with 8 bits.)
     
     
  3. Describe an algorithm that takes as input a number K and prints out 2^K lines, labelled as for a truth table with the first line starting "T T ... T" and the last line starting "F F ... F". Your algorithm may be described either in English or in pseudocode. In addition to the algorithm, include one or two sentences about why and how it works; in particular, informally explain (1) why your algorithm terminates, and (2) why it always gives the correct output.
  
  
  4. In Java, the negation operator is denoted by !, conjunction (and) is denoted by && , disjunction (or) is denoted by ||, and assignment is denoted by =. Let P and Q be Java boolean variables. What are the values of P and Q after the following code is executed? (Hint: Does it matter what the initial values of P and Q are? Recall the instructions about what we expect from complete answers.)
     
  
  
  5. Consider Boolean expressions which may use three Boolean variables P, Q, R. We can group these expressions based on their truth tables.
     1. Which truth table(s) give(s) the shortest possible DNF? (Shortest is in terms of number of disjunctions or conjunctions.)
     2. Which give(s) the longest possible DNF?
     3. Which give(s) the shortest possible CNF?
     4. Which give(s) the longest possible CNF?
     
     
• Homework 1, due 10/13. Reading: JS Chapter 1.
  
  Instructions: complete answers must include reasoning and explanation, using full sentences. Assignments must be typed and submitted as .doc or .txt or .pdf files. Any images or diagrams that you use as part of the explanation may be scanned and incorporated as part of the (single) assignment document; text cannot be scanned. You may choose to work in groups of 1-3 students for this HW. Submit only one document per group. The names and PIDs of all group members need to be listed at the top of the document.
  
  0. Warmup exercises (do not hand in): JS 1.8, JS 1.9, JS 1.13, JS 1.14
  
  
  1. The following algorithm is supposed to compute the sum of the first n positive integers. Does it work properly? If so, why? If not, explain the problem and fix it.
     • sum1ToN( int n ):
     •   return n + sum1ToN(n-1)
  2. [JS 1.5] Is n^2 + n + 17 always prime (when n is a nonnegative integer)? (Recall the instructions about what we expect from complete answers.)
  
  
  3. Use Euclid's Algorithm to find GCD(N+1, N) for any positive integer N. Does this show that N and N+1 never have a prime factor in common? (Recall the instructions about what we expect from complete answers.)
  
  
  4. A "machine" consists of a row of boxes. To start, one places n pennies in the leftmost box. The machine then redistributes the pennies as follows. On each iteration, it replaces a pair of pennies in one box with a single penny in the next box to the right. The iterations stop when there is no box with more than one coin. For example, if we start with 6 pennies in the leftmost box and, in each iteration, choose to distribute a pair of pennies from the leftmost box with at least two coins, we get the sequence

     Initial state:	6	Empty	Empty
     After 1 iteration:	4	1	Empty
     After 2 iterations:	2	2	Empty
     After 3 iterations:	0	3	Empty
     After 4 iterations:	0	1	1

     1. Does the final distribution of pennies depend on the order in which the machine processes the coin pairs?
     2. What is the minimum number of boxes needed to distribute n pennies?
  5. [JS 1.18] Let X* denote the approximation obtained by rounding X to 2 places after the base point. If X*=45.67, then 45.665 <= X < 45.675. In general, X* - 0.005 <= X < X* + 0.005. If A* = B* =z, then |B-A|< 0.010. Is it true that if |B-A| <= 0.01, then A* = B*? Or could we have |B-A| <=0.000 000 1 but A* not equal to B*?
  
  
  6. [Bonus] Two early mathematicians** mentioned in this chapter are Al-Khowarizimi and Euclid. Look up some data about each of them and write a short paragraph including:
     • Time and place each lived.
     • Two major contributions each made to mathematics and / or science. Illustrate each of these contributions with a different example from those you find in whichever references you're using.
     You must include reference information for all sources you consult. Answers without citations will receive zero bonus credit.
     (**In the early days, there were no computer scientists. All of the scientists who laid the foundation for modern Computer Science were mathematicians.)
• Homework 0, due 10/6, has three components which must be completed to earn full credit.
  1. CSE 20 Pre-test: complete through   Ted.  
     In Ted, navigate to our course, CSE20 - Minnes Kemp [FA14]. Click on the link in the left sidebar for "Homework, Quizzes, Handouts". In the Homework folder, you will find a link to HW0 Part 1. You will receive full credit for this part of the HW for honest attempts at answering the questions; correctness of the answers will not be used to calculate your score for this HW.
     
     
  2. Pre-survey: answer some questions about your experience in CSE thus far https://www.surveymonkey.com/s/LQ66JLZ
     * If you've filled out the pre-survey for another class, you do NOT need to fill it out again.*
     
  3. Consent form: the pre-test and pre-survey results will be studied to improve CSE education at UCSD and beyond. Fill out a consent form indicating your (un)willingness to be considered in the study https://www.surveymonkey.com/s/CRRMQWN
     * The consent form must be filled out for CSE20, even if you've filled it out for other classes.*
  HW0 must be completed individually. (Future assignments can be group based.)

Top