CSS 342A: Mathematical Principles of Computing
Autumn 2009 MW 545-750pm at UW2-005

Prof. Munehiro Fukuda


Professor:

Munehiro Fukuda <mfukuda@u.washington.edu>, room UW1-331, phone 352-3459, office hours TTh 4:40pm-5:40pm

Course Description:

This sequenced course integrates mathematical principles with detailed instruction in computer programming. Topics include presentation of formal arguments to prove mathematical statements; development of algorithms; sorting and searching; algorithm analysis; introduction to object-oriented programming; and basic abstract data types including stacks, queues, and lists.

Prerequisites:

Calculus, Probability & Statistics, and two quarters of programming (C/C++ competency).

Grading:

Course Work Percentage Achievements Corresponding Numeric Grade
Midterm Exam 25% 90s 3.5 -- 4.0
Final Exam 25% 80s 2.5 -- 3.4
Prog. Assignments 1 - 7 28% (4% each) 70s 1.5 -- 2.4
Quizses 1 - 4 12% (3% each) 60s 0.7 -- 1.4
Labs 1 - 7 7% (1% each)
In-Class Exercises 1 - 4 4% (1% each)
Total 101% (including 1% bonus credit)

All homework assignments are graded in accordance with the corresponding grading guide which you can see through the class website. The key answer will be made available to you through ePost when you receive your graded work. You have a right to discuss about regrading your work, which must be however done within a week after I have returned graded work in the class. Regrading will be discussed thoroughly based on the grading guide and key answer.

Textbooks:

  1. Data Structures and Problem Solving Using C++, Mark Allen Weiss, Addison-Wesley, 2nd Ed. 2000.
  2. Discrete mathematics and Its Applications, Sixth Edition, Kenneth H. Rosen, McGraw Hill, 2007.
  3. A C++ book of your choice.

Some C++ Books:

References:

Data Structure Books:

Policies:

Homework: All homework assignments are to be done independently. Any collaboration of work will result in severe penalty. You may discuss the problem statement and any clarification with each other, but any actual work to be turned in, must be done without collaboration. Plagiarism is 100% intolerant and thus reported to Office of Academic Affairs.

Both hard and soft copies of assignment work are due at the beginning of class on the due date. No late submisions will be accepted. Except for special circumstances such as medical and other emergencies, in which case you must present a written proof to me. Barring emergencies, the professor must be informed before the assignment due date. Note that disk crash is not considered as an emergency.

Laboratory work: Seven short programming problems will be given in the class as a post-lecture task and an introduction to each homework assignment. Each student is supposed to independently turn in the code and execution results through CollectIt (for Lab Work).

In-class exercises: This series of mathematical exercises will be done by a group of students. At the end of each session, each group is supposed to turn in a short report that describes an answer and lists all group members' names. If you miss a session and still hope to make it up, you need to work on its topic by yourself and turn in a report with a written proof of your emergency.

Exams and quizses: Each quiz will be given from the scope covering its previous non-turn-in writing exercise and in-class exercise. It will be given for the first 20 minutes of the class. So, don't be late. Midterm and final examinations cover weeks 1 - 5 and 6 - 10 respectively. All quizes and examinations will take place in the same classroom. Niether make-up exams nor quizzes will be given unless you inform me of your medical/family/business emergency.

Special needs: To request academic accommodations due to a disability, please contact Disabled Student Services (DSS) in Library Annex Building, Room 106, (email dss@uwb.edu, TDD: 425-352-5303, and FAX: 425-352-5455). If you have a documented disability on file with the DSS office, please have your DSS counselor contact me and we can discuss accommodations.

Course Goals:

The overall goal of CSS 342 is to learn discrete mathematics concepts and computer programming. You solve mathematical problems, present formal mathematical arguments, and program solutions to problems. The class reviews programming basic data types, learns searching and sorting algorithms, discuesses object-oriented programming and basic abstract data types, and studies algorithm analysis. The programming language C++ is studied. Good software engineering techniques are used throughout. As with most technical courses, besides ability and motivation, it takes time to learn and master the subject. Expect to spend an additional 10 to 15 hours a week outside of class time on the average.

Programs:

Turn in both a hard and a soft copy of your programming assignments.

Syntax errors and run-time errors without much output yield a low grade. Run-time errors (occurring after the majority of the output), or incorrect answers will result in a significant number of points being deducted from your grade. Otherwise, you will be graded on documentation (clarity and completeness), style (indentation, use of blank lines and spaces), meaningful identifier names, organization of your program (modularity, design), efficiency (no useless, unnecessary, or unnecessarily complicated code), output (clarity and format), the overall readability of your entire program, and following directions.

Read assignment.html for more details.

Sample code:

You can find some sample programs regarding standard template libraries, templates, recursion, sorting, lists, stacks, and queues in http://courses.washington.edu/css342/fukuda/code/. You may refer to those programs when working on your lab work and homework. Note that you cannot read all files under this directory, since those unreadable files are key answers.

Catalyst EPost (Message Board):

You can access CSS342A GoPost to exchange messages with your classmates. Please use this board for only dicussions. No junk email. Note that the professor will not keep track of all messages. The professor monitors this board once a day (in the morning) from Monday to Friday.

Topics covered and tentative 342 winter schedule:

Note that this is an approximate ordering of topics. Chapters will take about the allotted time and not all sections in all chapters are covered. (Topics labeled C++, refer to Data Structures and Problem Solving Using C++. Topics labeled Math, refer to the Discrete Mathematics and Its Applications.)

Week Date Topics Lab, Exercises, and Quizes Reading Assignment
0 Oct 1 Introduction   C++ ch1  
1 Oct 6 Objects and classes Lab work 1 C++ ch2 Program 1 assigned
  8 Templates   C++ ch3, ch5  
2 13 Algorithm analysis   C++ ch6
Math Ch3.2,3.3
 
  15 Algorithm analysis (continued) Lab work 2   Program 1 due
Program 2 assigned
Non-turn-in writing exercises 1 assigned
3 20 Recursion   C++ ch8
Math Ch7.1-3.3
 
  22 Recursion (continued) Lab work 3   Program 2 due
Program 3 assigned
4 27 Induction Exercise 1 Math 2.4,4.1,4.2,4.4  
  29 Sorting algorithms Quiz 1 C++ ch9,
Math 3.1,4.4
 
5 Nov 3 Sorting algorithms (continued) Lab work 4   Program 3 due
Program 4 assigned
  Nov 5 Midterm exam      
6 Nov 10 Linked lists   C++ ch17  
  12 Linked lists (continued)
Lab work 5   Program 4 due
Program 5 assigned
7 17 Stacks and compilers   C++ ch12  
  19 Stacks and compilers (continued) Lab work 6   Program 5 due
Program 6 assigned
8 24 Queues Lab work 7 C++ ch16  
  26 no school - holiday      
9 Dec 1 Propositions Exercise 2 Math ch1.1,1.2 Program 6 due
Program 7 assigned
Non-turnin writing exercise 2 assigned
  Dec 3 Quantifiers Quiz 2
Exercise 3
Math ch1.3,1.4 Non-turnin writing exercise 3 assigned
10 Dec 8 Proofs Quiz 3
Exercise 4
Math ch1.5,1.6 Non-turnin writing exercise 4 assigned
  10 Review and wrap-up Quiz 4    
11 15 Final exam     Program 7 due