COMP 1805 DISCRETE
STRUCTURES
This is the COMP1805 home page
"http://www.scs.carleton.ca/~maheshwa/courses/COMP1805/1805.html".
Check it regularly for new information, assignments, etc.
Instructor: Professor Anil Maheshwari
Office: School of Computer Science, Carleton University,
Ottawa,
Canada K1S 5B6, room 5364, Herzberg Physics Building,
Phone: (613) 520-4333, Fax: (613) 520-4334,
OFFICE HOURS:
E-mail: maheshwa@scs.carleton.ca,WWW:http://www.scs.carleton.ca/~maheshwa.
Term:
Class Hours:
Tutorial : .
Course-TAs:
Course Objectives: This is a fundamental course in
understanding
what computers do and can do. Computers handle discrete structures
(everything
needs to be represented in finite number of bits). The course presents
an overview of some of the major theoretical concepts needed to
understand
the structures which computers can represent and manipulate. The
emphasis
is on developing the concepts, methods of proof, and quantitative
analysis.
Topics include: propositional and predicate calculus, Boolean algebra,
introduction to complexity of algorithms, mathematical reasoning,
counting,
recurrences, relations, introduction to graphs. (Also listed as MATH
1805.)
Courses Prerequisites: Two OACs in
Mathematics
or two Grade 12 university preparation Mathematics courses (after
Summer
2002), and one of COMP
1405, COMP
1005, COMP
1007 or Engineering SYSC
1100 (which may be taken concurrently).
Text Book: Discrete Mathematics and Its
Applications
(5th edition) by Kenneth H. Rosen, Mc-Graw Hill, 2003.
We will be mainly concentrating on Chapters 1, 2, 3, 4, 6, 7,
8, 9 and 10 from the book in this course.
Important Dates:
All Assignments need to be submitted in the Assignment Box for this
course in
Room 4135 HP (Herzberg 4th Floor) by 1 PM of the due date.
TA will remove all assignments shortly after 1PM and late submissions
will
receive 0 MARKS. Please do not try to submit the assignments anywhere
else
other than these boxes.
Here are the Sections which you should study with respect to
the
Final Exam.
| 5th Edition |
4th Edition |
| 1.1, 1.2, 1.3 (Skip Logic Programming),
1.4,
1.5, 1.6, 1.7 (Skip Computer Representation), 1.8, 2.2, 3.1, 3.2, 3.3,
3.4 (Skip Lame's), 4.1, 4.2, 4.3, 4.4, 6.1, 6.2 (Thm 1 and Thm 3 for
distinct
roots), 6.5, 7.1, 7.3, 7.4 (Skip Warshalls), 7.5, 7.6 (Skip Topological
Sort). |
1.1, 1.2, 1.3, 1.4, 1.5 (Skip
Computer
Representtion), 1.6, 1.7, 1.8, 3.1, 3.2, 3.3, 4.1, 4.2,
4.3,
5.1, 5.2 (Thm 1 and Thm 3 for distinct roots), 5.5, 6.1, 6.3, 6.4, 6.5,
6.6 (Skip Topologcal). |
Whats done in the class?
Course Logistics, Pigeon Hole Principle and Coloring Complete Graph
on 6 vertices by two colors, Propositional Logic (Negation, OR, AND,
XOR,
IMPLICATION, Bicondition, Logical Equivalences, Tautologies,
Contradiction
and Equivalence Rules).
Predicate Logic, existential and universal quantifications, sets -
definitions - cartesian products, union, intersection, difference,
complement,
equality.
Functions - definitions - composition - add- multiply - one-one - onto,
Countability
Growth of Functions and Proof Techniques.
Mathematical Induction I and II. Recursive Definitions.
Recursive Sets. Counting.
More on Counting, Pigeon Hole Principle, Coloring K_6 with red/blue
colors, increasing decreasing
subsequences, permutations and combinations.
Mid-Term and Binomial Theorem
Recurrence Relation and
Relations.
Relations, Equivalence Relations and
Representation of Relations.
Partial Orders, Graphs, Planar Graphs,
Coloring.
More on Graphs and Review and Problems.
Course evaluation :
Final Examination : 55%
Mid-Term Exam (1 Mid-Term Exam: 25%):
Assignments (4 Assignments): 20%
Announcements:
Students with Disabilities: If there
is
any student in this course who, because of a disability, may have a
need
for special accommodations, please contact the Paul Menton
Centre
to obtain a Letter of Accommodation for any special arrangements".
Please
check for deadlines with them.
http://www.scs.carleton.ca/~maheshwa