CprE 310: Theoretical Foundations of Computer Engineering
Spring 2008

Tue, Thu 8 - 9.20am in Carver 0101


Messages Staff Syllabus Textbooks Schedule Homeworks
Assignments Exams Grading Course Policies WebCT Assorted Links

Messages

Course Staff

Instructor Teaching Assistant Teaching Assistant
Srikanta Tirthapura Somya Gupta Tycho Andersen
Email: snt@iastate.edu Email: somyag@iastate.edu Email: tanderse@iastate.edu
Office: Room 3212, Coover Hall Office: ALC Village D, Cubicle 15 Office: ALC Village C, Cubicle 14
Phone: (515) 294-3546
Office Hours: Tuesday 9.30-10.30am Office Hours: Monday 3-4pm Office Hours: Monday 11-12am, Thursday 2-3.30pm

Description

This course is an introduction to the mathematics and logical thinking needed for computer engineering. It will provide a foundation for further study of computer algorithm design and analysis. We will cover the following topics: The course syllabus in pdf.

Textbooks

Grading

The course grade is based on regular homeworks and three exams, according to the following weights. Late Policy: There is a late submission penalty of 20 percent per (working) day for the homeworks. We will not accept homeworks later than five working days after the deadline.

Course Schedule

Day Topic Reading Homeworks/Assignments
Tue Jan 15 Introduction
Thu Jan 17 Introduction to Proofs, Logical Equivalences Sections 1.6, 1.7
Tue Jan 22 Direct Proof, Proof by Contradiction Sections 1.6, 1.7 HW 1 out
Thu Jan 24 More Proofs by Contradiction Sections 1.6, 1.7
Tue Jan 29 Propositions and Sets Sections 1.1, 1.2
Thu Jan 31 Overview of Functions, More Proofs Sections 2.1, 2.2, 2.3 HW 1 due, HW 2 out
Tue Feb 5 Predicates and Quantifiers, Proof by Induction Sections 1.3 (predicates), 4.1 (Induction)
Thu Feb 7 Proof by Induction Sections 4.1, 4.2 HW 2 due, HW 3 out
Tue Feb 12 More Proofs
Thu Feb 14 Recursive Definitions Section 4.3 HW 3 due
Tue Feb 19 Introduction to Graphs Section 9.1
Thu Feb 21 More Graphs + Recap for Exam 1 HW 4 due, Assignment 1 out
Tue Feb 26 EXAM 1 Proofs + Basics of Graphs
Thu Feb 28 Graph representations, Breadth First Search Section 9.3
Tue Mar 4 Depth First Search, Big-Oh Notation Section 3.2
Thu Mar 6 Big-Oh Notation Section 3.2 HW 5 out
Tue Mar 11 Asymptotic Analysis of Algorithms,
Bubble Sort Analysis		 Assignment 1 due
Thu Mar 13 Recap of midterm and Homework 5,
Special Classes of Graphs 		HW 5 due, HW 6 out
Tue Mar 18 Spring Break
Thu Mar 20 Spring Break
Tue Mar 25 Trees, Basic Properties Section 10.1
Thu Mar 27 Minimum Spanning Trees,
Kruskal's and Prim's algorithms.
Look at animations here 		Sections 10.4 and 10.5 Assignment 2 out (due Apr 15), HW 7 out
Tue Apr 1 Euler Circuits
Thu Apr 3 Recap for Exam 2 HW 7 due
Tue Apr 8 EXAM 2
Thu Apr 10 Hamilton Circuits,
Traveling Salesperson Problem
Graph Isomorphism
Look here for TSP slides. 		Sections 9.3, 9.5
Tue Apr 15 Basics of Counting, Sum and Product Rules Section 5.1 Homework 8 out, Assignment 2 due
Thu Apr 17 Permutations Section 5.3
Tue Apr 22 Combinations Homework 8 due
Thu Apr 24 Permutations with Repetitions
Tue Apr 29 Binomial Theorem
Thu May 1 Recap for Final Exam Homework 9 due
Monday May 5, 7.30-9.30 am Final Exam

Homeworks

You can check your homework grades on WebCT .

Assignments

Login to the webCT discussion board to see discussion about the assignments.

Exams

Old Exams:

Practice Problems for Exam 2 are here.

Course Policies

Disability

If you have a documented disability and anticipate needing accommodations in this course, please make arrangements to meet with me soon. Please request that a Disability Resources staff send a SAAR form verifying your disability and specifying the accommodations you will need.

Academic Integrity

All your work should be done individually unless otherwise specified. You are not allowed to use work done by others, or obtain the answers directly in any form (such as from the web). If you have any questions about what is allowed/not, please contact the instructor, and please refer to the university policies on academic dishonesty .

Assorted Links