CSci 1302 Problem Solving and Algorithm Development II.

[Home] [Syllabus] [Assignments] [Resources]

Syllabus

The timeline below is somewhat approximate. Dates, topics, assigned reading, and problem set due dates are subject to change. All changes in assigned reading and due dates will be announced in class (and occasionally by e-mail). While I will do my best to update the web site accordingly, it is a student's responsibility to keep track of the problem set due dates and reading assignments. If you are not sure about due dates, please don't hesitate to ask.

Both the midterm and the final exams are open book, open notes.

Note that the date for the midterm exam is set and will not change. If you have a conflict with this date, please let me know right away.

All reading is from Discrete Mathematics with Applications by Susanna S. Epp (3rd edition), unless specified otherwise.

Late problem sets policy: Problem sets are due in the beginning of the class on the due date. If a problem set is submitted at (or before) the next class meeting after the due date, it is graded out of 3/4 credit. If it is submitted any time after the next meeting (until the last class meeting), then it is graded out of 1/2 credit.
Problem sets submitted more than 5 minutes after beginning of the class may be considered late.

Groups for problem sets

Working together with other students on problem sets helps you understand the material better. You may hand in group assignments (two students per group). Make sure you keep copies of all assignments yourselves and hand in one assignment from the entire group with names of all students on the first page. Groups are not set in stone for the entire semester, it's perfectly OK to change them or do some problem sets on your own, just make sure to coordinate it with the other person in your group.

Working in groups helps learning if all students in the group discuss all of the problems and participate equally. It doesn't help you learn if you divide problems among the group members (so that one person works on one problem and another works on another) or if one person does all the work, and the other just puts their name on it. If you feel that group participation is uneven, it's time to talk to your partner(s) and possibly to change your group or to start working individually.

Discussion with students other than those in your group (or anyone not in this class) should be limited to general approaches to the problem. All such discussions as well as use of sources other than the textbook and the handouts given in class must be acknowledged in the beginning of the problem solution.

Studying in groups

Studying in groups is strongly encouraged. Yopu may study for tests, go over texbook materials or lecture notes, and discuss problem sets in general terms (i.e. without actually writing the formulas or giving out the answers).

In-class quizzes

There will be approximately 10-12 quizzes during the semester. A quiz will be about 10-15 minutes and will be based on recent material (including the material of the previous class meeting and the assigned reading). Quizzes are open book: you may use your notes and the textbook and your notes on a quiz. Quiz dates will not be announced in advance.

Missed quizzes are counted as 0. The lowest quiz grade in the semester will be dropped (i.e. it will not contribute to overall grade).

Monday Wednesday Friday
Week 1: January 17 - 20
Martin Luther King Day, no classes
 Introduction, course overview.
Logical systems, scientific theories, mathematical models.
 Propositional logic: statements and connectives.
Reading: Ch. 1.1
Problem set 1: Statements, logical equivalence (due Wedn., Feb. 1)
Week 2: January 23 - 27
Statements and connectives (continue); truth tables
 Logical equivalence.
 Conditional and biconditional statements.
Reading: Ch. 1.2
Week 3: January 30 - February 3
Valid and invalid arguments. Logical deduction.
Reading: Ch. 1.3
 Logical deduction (continue)
Problem set 1 due
Problem set 2: Logical deduction (due Wedn., Feb. 8)		 Digital circuits.
Reading: Ch. 1.4
Week 4: February 6 - 10
Digital circuits and number manipulation.
Reading: Ch. 1.4 		Digital circuits and number manipulation (cont.).
Problem set 2 due
Problem set 3: Digital circuits and number manipulation. (due Wedn., Feb. 15) 		Introduction to quantifiers and predicates.
Reading: Ch. 2.1
Week 5: February 13 - 17
Formulas with quantifiers.
Equivalences of quantified formulas.
Reading: Ch. 2.2.
Problem set 3 due
Problem set 4: Quantifiers and predicates. (due Wedn., Feb. 22) 		Equivalences of quantified formulas (cont.)
Scope of quantifiers, bound and free variables.
Week 6: February 20 - 24
Statements containing multiple quantifiers, their equivalences.
Equivalences of formulas with multiple quantifiers.
Reading: Ch. 2.3 		Deduction in predicate logic
Reading: Ch. 2.4
Problem set 4 due
Problem set 5: Equivalence of quantified formulas (due Wedn., March 1) 		Deduction in predicate logic (cont.)
Reading: Ch. 3.1
Week 7: February 27 - March 3
Deduction in predicate logic (cont.)
Reading: Ch. 3.2, 3.3
Problem set 6: Deduction in predicate logic (due Mon., March 13) 		Deduction in predicate logic (cont.)
Reading: Ch. 3.4, 3.6
Problem set 5 due
 Proving correctness of algorithms.
Reading: Ch. 3.8
March 6 - 10: Spring break, no classes
Week 8: March 13 - 17
Introduction to mathematical induction.
Reading: Ch. 4.1, 4.2
Problem set 6 due
 Review for the exam.
Problem set 7: correctness of algorithms, mathematical induction (due Wedn., March 29) 		Midterm exam (includes material up to Friday, March 3.)
Week 9: March 20 - 24
Mathematical induction (cont.).
Reading: Ch. 4.3, 4.4.
 Mathematical induction (cont.).
 Introduction to loops in imperative programming languages.
Loop invariants.
Reading: Ch. 4.5
Week 10: March 27 - 31
More on loop invariants. Efficiency of algorithms, Big-Oh notation
Reading: 9.1, 9.2
Problem set 7 due.
Problem set 8: Loop invariants, efficiency of algorithms (due Wedn., April 5) 		Efficiency of algorithms
Reading: 9.3, 9.4
Week 11: April 3 - 7
Efficiency of algorithms (cont.)
Reading: 9.5
 Introduction to sets, basic concepts of set theory.
Reading: Ch. 5.1.
Problem set 8 due.
Problem set 9: Efficiency of algorithms, Introduction to sets (due Wedn., April 12). 		Exercises on efficiency of algorithms, sets (I will be away on this day)
Week 12: April 10 - 14
Set operations
 Proving properties of sets.
Reading: Ch. 5.2, 5.3
Problem set 9 due.
Problem set 10: sets, operations on sets (due Wedn., April 19) 		Relations (introduction).
Reading: Ch. 10.1
Week 13: April 17 - 21
Relations (cont.), composition of relations.
Properties of relations; functions
Reading: Ch. 10.2, 10.3
Problem set 10 due.
Problem set 11: Relations, relational closures, equivalence classes (due Wedn., April 26) 		Relational closures
Week 14: April 24 - 28
Partial order relations
Reading: 10.5
 Graphs.
Reading: Ch. 11.1, 11.2
Problem set 11 due.
Problem set 12: Partial order relations; Graphs (due Wedn. May 3) 		Graph representations, adjacency matrices
Reading: Ch. 11.3
Week 15: May 1 - 5
Graph isomorphism; Trees.
Reading: Ch. 11.4, 11.5.
 Graph traversals.
Reading: TBA
Problem set 12 due.
 Last day of classes
Review and wrap up.
Last day to submit any late work.
Final exam: Tuesday, May 9 11am-1pm