Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!
With a final exam comparable in difficulty to the midterm, the scores needed for an A will be circa 88; for B circa 77, for C circa 66, and 55 will be needed for passing grade (D).
The topics for the final correspond to the homework topics, with just one exception: pseudocode/recursive algorithms/algorithm correctness will not appear on the exam. The emphasis will be on topics not on the midterms, that is, starting with Induction/Recursion. That being said, logic, proofs, sets, functions, Big-Oh are quite likely to appear as building blocks of other problems.
The following were distributed in class, January and February. expected outcomes -- counting, probability, graphs, languages.
HW11 (the last one) was posted April 19 is due April 25. The late-turn-in policy for this homework is as follows: 5% Friday April 27, 10% before the final exam starts (8AM, May 1st), and no homework will be accepted after the exam has started.
Read Chapter 10 (sixth edition: Chapter 9) before the April 23 lecture.
The quiz on April 23 will be based on Graphs.
HW10 was assigned April 11 is due April 18:
Read Sections 7.1 and 7.2 (sixth edition: 6.1 and 6.2) before the April 16 lecture.
HW9 is due April 11:
Read Sections 6.3 and 6.4 (sixth edition: 5.3 and 5.4) before the April 9 lecture.
The quiz on April 9 will be based on counting.
HW1 is due Jan. 18:
Write clearly and turn in hard coppies. Blackboard is useful as a timestamp and backup, but we do want hard coppies.
Read Sections 1.1, 1.2, and 1.3 for Homework 1, and Section 1.4 before the Jan. 18 lecture.
Read Sections 1.4 and 1.5 for the Jan. 20 lecture and Homework 2, which consist of the following siz exercises: Subsection 1.3: 12, Subsection 1.4: 48, 62, and Subsection 1.5: 6, 16, 36.
In the sixth edition, these exercises appear as follows: Subsections 1.2: exercise 12, Subsection 1.3: 48, 62, and Subsection 1.4: 6, 16, 36. Homework 2 is due Wednesday Jan. 25. There is a quiz Monday, Jan. 23.
HW3 is due Feb. 1:
HW4 is due Feb. 8:
The first midterm, 50 minutes on Feb 17 (instead of recitation) will be based on Chapter 1 of the textbook, or roughly on Homeworks 1-4 and Quizzes 2-5. The quiz on Feb. 27 will be based on functions. Read Sections 3.2 for the Feb. 27 lecture.
The following were distributed in class, January and February. expected outcomes -- logic , expected outcomes -- proofs, expected outcomes -- sets, functions, induction, and a onto computable function from Z+ to Z+ X Z+.
HW5 is due Feb. 22:
HW6 is due Feb. 29:
Quiz 8 on March 5 will be based on Big-Oh. Read Section 5.2 (sixth edition: 4.2) for the March 2 lecture (not recitation).
HW7 is due March. 7:
Quiz 9 on March 12 will be based on induction/recursion. Read Section 5.3 (sixth edition: 4.3) for the March 12 lecture.
The second midterm, 50 or 75 minutes on March 16 (instead of recitation) will be based on: Sets, Functions, Summations, Big-Oh, and Induction/Recursion (but not recursion with structures, algorithms, or recurrence relations). It corresponds to Quizes 5-9 and Homeworks 5-7. Logic/proofs are likely to appear as part of the questions about sets, functions, etc. The exam is open books closed notes as the first midterm.
Read Section 6.1 (sixth edition: 5.1) before the April 2nd lecture.
Homework 8 was assigned March 15 and is due March. 30. The deadline was extended to April 2nd.
The following were distributed in class, March: pseudocode for merge and partition, with invariants and some lecture notes on recurrence relations.
Quiz 10 on March 26 will be an interview question. The week March 26--30 will have three recitation sessions, one covering the Master theorem.
Quiz 11 on April 2 will be based on solving recurrence relations. Read sevent edition Section 6.1 (sixth edition: Section 5.1) before the April 2nd lecture.
HW9 is due April 11:
Read Sections 6.3 and 6.4 (sixth edition: 5.3 and 5.4) before the April 9 lecture.
The quiz on April 9 will be based on counting.