CSS 501 – Data Structures and Object-Oriented Programming – Fall 2013

University of Washington, Bothell - Computing & Software Systems

http://courses.washington.edu/css501/ksung

 

 

Professor:                   Kelvin Sung                            Class:                 MW 6:00-7:40pm, UW2-240

                                    Office: UW1 – 339                 Office Hours:    MW After Class

                                    Phone: (425) 352-5420                                      or by appointment

                                    E-mail: ksung@uw.edu                     

 

Lab assistants:           Hours will be posted at http://www.bothell.washington.edu/css/advising

 

Prerequisites: CSS 161 and CSS 162

 

Course content:

This course is designed to give students data structures knowledge and object-oriented programming skills that will be necessary in the CSS master’s program. Basic and advanced abstract data types, their uses, and implementations will be studied. Students will learn how to analyze a problem and design a solution using object-oriented design with various data types. Algorithms, and the tradeoffs among memory, running time, and implementation time associated with them are covered. Students develop competencies associated with problem solving, design, testing, programming, and software management. Good software engineering practices and algorithm analysis techniques are used throughout.

 

Textbooks

Required:

  • Frank M. Carrano, Data Abstraction & Problem Solving with C++, 6th edition, Addison Wesley, 2013.

You will probably also want to have a C++ reference book. Examples include:

  • Bruce Eckel, Thinking in C++, 2nd edition, Prentice Hall, 2000.
  • Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley, 3rd ed., 2000.
  • Walter J. Savitch, Problem Solving with C++, Addison-Wesley, 8th ed., 2011.
  • Harvey M. Deitel and Paul J. Deitel, C++: How to Program, Prentice Hall, 8th ed., 2011.
  • Stanley B. Lippman, Josee Lajoie., and Barbara E. Moo, A C++ Primer, Addison-Wesley, 5th ed., 2012.

 

Assignments / Grading

The assignments for this course will consist of four or five programming assignments, one of which will include a design component. There will also be two midterms and a final. The components will be weighted as follows:

 

Assignments:   30% Edit on 11/16/2013: 40%

Midterms:        40% Edit on 11/16/2013: 35%

Final:               30% Edit on 11/16/2013: 25%

 

I expect to use a linear grading scale such that 80% = 2.7 (minimum successful grade) and 95% = 4.0.

Edit on 10/24/2013: The actual grade will be determined based on difficulties of the exams.

 

Note that there is no extra credit in this course, so make sure that you turn in the best work that you can.

 

 

Class policies

Assignments are due prior to class on the due date. The submission site will be closed promptly at the start of class. There will be no individual extensions and there will be no late assignments. Assignments will be turned in using Catalyst at the following web page (please refer to the class website for the Turn-in site URL).

 

All assignments are to be completed independently, unless explicitly stated otherwise. Please be very careful to adhere to the student code of conduct: http://www.washington.edu/students/handbook/conduct.html

 

Lecture notes will be posted on the course web site after the lecture in which they are presented. Please refer to our course web-site for the message board on Catalyst that can be used for questions and discussions.

 

Remember to turn off all cell phones and beepers prior to class as a courtesy to other students. The best way to get hold of me is via email, I can usually response to my emails within 24 hours.

 

The University of Washington is committed to providing equal opportunity and reasonable accommodation in its services, programs, activities, education, and employment for individuals with disabilities. If you believe that you have a disability and would like academic accommodations, please contact Disability Support Services at 425.352.5307, 425.352.5303 TDD, 425.352.3581 FAX, or at dss@uwb.edu. You will need to provide documentation of your disability as part of the review process.

 

Tentative Schedule (subject to change)

Date

Topic

Reading

Assignments

Sep 25

Introduction, image programming

5th Ed: Ch 1, App-A

6th Ed: Ch 1, App-A

6th Ed: Interlude 1

HW 1 assigned

 

 

 

 

Sep 30

C++ classes and OOP

5th Ed: Ch 3

6th Ed: Ch 1

 

Oct  2

Data abstraction and templates

5th Ed: Ch 3

6th Ed: Ch 1

HW1 due, HW2

 

 

 

 

Oct  7

Recursion

5th Ed: Ch 2

6th Ed: Ch 2

 

Oct  9

More recursion

5th Ed: Ch 5

6th Ed: Ch 5

HW2 due, HW3

 

 

 

 

Oct 14

Algorithm analysis

5th Ed: Ch 9.1

6th Ed: Ch 10

 

Oct 16

Induction

See course notes

HW3 due, HW4

 

 

 

 

Oct 21

Midterm

Sequences, recurrence relations

Catchup

 

HW4

Oct 23

Sequences, recurrence relations

Midterm

See course notes

 

 

 

 

 

Oct 28

Pointers and dynamic memory

5th Ed: Ch 4.1

6th Ed: Interlude 2 (Skip C2.2 and C2.4)

 

Oct 30

Linked lists

5th Ed: Ch 4.2

6th Ed: Ch 9

 

 

 

 

 

Nov  4

Linked lists

5th Ed: Ch 4.3-4.5

6th Ed: Ch 8

Nov  6

Stacks and queues

5th Ed: Ch 6 and 7

6th Ed: Ch 6 and 13.1-13.2

HW4 due, HW5

 

 

 

 

Nov 11

Veteran’s Day – no class

 

 

Nov 13

Design reviews Catch up

 

HW5 due

 

 

 

 

Nov 18

Midterm

Sorting

 

 

Nov 20

Sorting

Midterm

5th Ed: Ch 9.2

5th Ed: Ch 11.2

HW6

 

 

 

 

Nov 25

More sorting   

 

 

Nov 27

Number systems and logic

See course notes

HW6 design due

HW6 due, HW7

 

 

 

 

Dec  2

Introduction to trees

5th Ed: Ch 10.1-10.2

6th Ed: Ch 15.1-15.2

 

Dec  4

Binary search trees

CANCELLED

5th Ed: Ch 10.3-10.4

6th Ed: Ch 15.3

HW7 due

 

 

 

 

Dec  9

Final (in class)