CSS 342C: Data Structures, Algorithms, and Discrete Mathematics I
Winter 2019 TF 1100am-100pm at UW1-040

Prof. Munehiro Fukuda


Professors:

Munehiro Fukuda <mfukuda@uw.edu>, room UW1-271T, phone 352-3459, office hours TF 10:00am-11:00pm or by appointment

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:

Minimum grade of 2.8 in CSS 143 or equivalent; minimum grade of 2.5 in STMATH 125 or equivalent.

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 35.5% (5% each for Prog.1 - 6, 5.5% each for Prog.7) 70s 1.5 -- 2.4
Quizses 1 - 3 9% (3% each) 60s 0.7 -- 1.4
Labs 1 - 7 3.5% (0.5% each)
In-Class Exercises 1 - 4 2% (0.5% each)
Total 100%

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 Canvas 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.

Changes/Announcements

Any changes on the course schedule and/or materials will be announced through Canvas.

Textbooks:

  1. Data Abstraction and Problem Solving with C++, 7th ed, Frank M. Carrano, Addison-Wesley, 2017.
  2. An Active Introduction to Discrete Mathematics and Algorithms, Charles A. Cusack, David A. Santos, Version 2.6.3, March 30, 2018.
  3. A C++ book of your choice.

Some C++ Books:

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.

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. Although students can work together in the class, each student is supposed to independently turn in the code and execution results through Canvas. Indicate your collaborators' names in the header comments of your code

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 in a week.

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. The final is not cumulative. 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 Disability Resources for Students (DRS) , (email rosal@uwb.edu, Phone:425-352-5307 and FAX: 425-352-5114). If you have a documented disability on file with the DRS office, please have your DRS counselor contact me and we can discuss accommodations.

In-class use of electronic devices: Turn off and store all devices in your bag or backpack except a laptop computer. Only for in-class lab sessions, you can use your laptop computer. However, don't use your laptop for any other purposes including video games, facebook, email response, etc., which are quite distructive to other students and the professor.

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 a soft copy of your programming assignments.

Each soft copy must be a zipped file (in tar or zip only) that includes your source code (in ASCII texts) and a Linux executable (which we will try to run in case if your source cannot be compiled) as well as some documents such as graphs, tables, and/or your sumamry if specified by an assignment.

Your code should compile and run properly with g++ compiler on Linux, the professors will test your code only with this execution environment. Upload your file through Canvas.

Don't email your softcopy to the professors.

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.

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 under the css342 home directory of UW1-320 Linux machines. 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.

Canvas (Discussion):

You can access CSS342A Canvas 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 CSS342 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 An Active Introduction to Discrete Mathematics and Algorithms.)

Week Date Topics Lab, Exercises, and Quizes Reading Assignment
1 Jan 8 Introduction and Abstraction   C++ ch1  
  11 Objects and classes Lab work 1 C++ ch interlude 1.1-1.2, 6 Program 1 assigned
2 15 Templates Lab work 1 Continued
due on Jan. 17
C++ ch interlude 1.3, 7  
  18 Algorithm analysis   C++ ch10
Math Ch7.1.1-7.1.3, 7.2, 7.3.1-7.3.3
 
3 22 Algorithm analysis (continued) Lab work 2
due on Jan. 24
  Program 1 due extended to Jan. 23 (11am)
Program 2 assigned
Non-turn-in writing exercises 1 assigned
  25 Recursion   C++ ch2, ch5.3-5.4
Math Ch8.2
 
4 29 Recursion (continued) Lab work 3
due on Jan. 31
  Program 2 due extended to Jan. 30 (11am)
Program 3 assigned
  Feb 1 Induction Exercise 1 Math 8.1.1 and 8.1.4  
5 Feb 5 Sorting algorithms Quiz 1 C++ ch11
Math 7.3.3 and 8.4
 
  8 Sorting algorithms (continued) Lab work 4
due on Feb. 19
  Program 3 due
Program 4 assigned
6 12 Midterm exam      
  15 Linked lists   C++ ch8-9  
7 19 Linked lists (continued)
Lab work 5
due on Feb. 26
  Program 4 due extended to February 23 (11am)
Program 5 assigned
  22 Stacks and compilers   C++ ch6 and ch5.1-2  
8 26 Stacks and compilers (continued) Lab work 6
due on March 5
  Program 5 due extended to March 3 (11am)
Program 6 assigned
  Mar 1 Queues   C++ ch13-14  
9 5 Queues (continued) Lab work 7
due on March 12
  Program 6 due extended to March 9 (11am)
Program 7 assigned
  8 Propositions Exercise 2 Math ch4.1-4.2 Non-turnin writing exercise 2 assigned
10 12 Quantifiers Quiz 2 (postponed to March 15)
Exercise 3
Math ch4.3,4.4 Non-turnin writing exercise 3 assigned
  15 Proofs Quiz 3 (a take-home quiz)
Exercise 4
Math ch2.1-2.3,4.2 Non-turnin writing exercise 4 assigned
11 19       Program 7 due extended to March 20 at 3:30pm
  22 Final exam