CS/SE 2630 - Object-Oriented Programming and Data Structures II

Instructor: Yan Shi

Office: 210Ullrich Hall;phone: 342-1512; email:

Office hours: Please check

Other times by appointment

Text:C++ plus Data Structures, 4thEd, by Dale, Jones & Bartlett, 2007

Course Description: Continuation of the object-oriented programming and data structure topics from CS/SE 2430. Coverage of pointers, templates, linked lists, trees, recursion, graphs, and algorithm analysis. Use of software engineering techniques such as inspections, test plans, and configuration management within a group-based project environment.

Prerequisite:CS/SE 2430

Course Outcomes: Upon completion of this course, students should be able to:

  1. Abstract, implement, and apply dynamic data structures including linked lists, binary search trees, and graphs; and solve programming problems in C++ using the STL
  2. Understand and write recursive programs, including sorts such as quicksort and heapsort
  3. Analyze the complexity of operations on arrays, lists, trees, and graphs
  4. Work in a small team to analyze, design, implement, and test a project
  5. Use configuration management tools
  6. Perform inspections and reviews within a team
  7. Begin to understand and improve the process by which you develop software.

Grading:

Points

2 Tests (70 points each):140

Final Exam100

Quizzes 60

5 Programs *150 (Must complete all programs to pass the course)

10 Labs 50

Total:500

* You must submit a runnable - and at least partial - solution to each of the 5 programming assignments to pass the course!

Grading scale:

Total PointsGrade Total Points Grade Total Points Grade

460 - 500A 445 - 459 A-

435 - 444B+ 410 - 434 B 395 - 409 B-

385 - 394C+ 360 - 384 C 345 - 359 C-

335 - 344D+ 300 - 334 D

below 300F

Students auditing the course must see the instructor to determine what is required for an "S".

Additional Notes:

  1. Good programs are completed on time! To allow for unforeseen circumstances, a grace period will be given for each program. Programs turned in or demonstrated after the grace period are worth 0 points. To honor the due date, a program submitted after the due date but during the grace period will receive 1-point penalty per day. Since the grace period already allows for "excuses", the only exception to this rule is a Doctor's Excuse for an illness lasting more than 3 days. Note that even if a program is late, you must still finish the program to pass the course.
  1. All program descriptions will be available on the CS/SE 263 web page at .
  1. All grades will be posted on D2L.
  1. Read your UWP email at least twice per day: morning and night.
  1. When you come to my office for help, have your code in K:\Courses\CSSE\shiy\cs2630\username so that I have access to it.
  1. All programs must follow the software development ground rules and be submitted as outlined in the program description.
  1. A test missed because of an excused absence such as illness verified by physician or participation in an authorized university activity can be made up in one of the following ways, provided the instructor is notified in advance: a) Written make-up test b) Count final 70% more
  1. Quizzes cannot be made up. However, if you let me know in advance of an expected absence, we can attempt to schedule some alternative.
  1. Attendance: Do not skip class. If you happen to miss a class for a legitimate reason, get the notes from a friend prior to the next class period. You are responsible for any material missed.
  1. Text: You are expected to read the corresponding text chapters.
  1. Exercises: You are expected to do the assigned exercises.
  1. Academic misconduct: You are responsible for honestly completing and representing your work, for appropriately citing sources, and for respecting the academic endeavors of others. You will be penalized for violating these standards and may even be expelled from the University. See Chapter UWS 14 (p. 172) in the Student Handbook for details.
  1. You have the right to miss class for religious observances. If you wish time off for this reason, let the instructor know within the first two weeks of the semester.
  1. Reasonable accommodations will be provided for students with physical, sensory, cognitive, systemic, and psychiatric disabilities. Please discuss any accommodations you may need with the instructor. A VISA from Services for Students with Disabilities authorizing your accommodations will be needed.

Course Outline:

Topics Textbook Chapters

Java to C++, C++ classes, OO Review, Stack/Queue Review2, 5.1, 5.3

Test Plans, Inspections1

Configuration Management, software development process, Preprocessorsupplements

Pointers, Memory Management, Destructors, Arrays, Linked Lists3.3, 2.2, 4.2, 6

Special C++ Language Constructs: Operator Overloading, Templates 6.12

C++ Miscellany: const correctness, friends, void *, this, inline, vtable3.2, supplements

Advanced Lists, Big 3, Iterators3, 6

Recursion7

Binary Search Trees8

Complexity, Recursive Sorts and Searches10

STL: List, Vector, Algorithm, Iterators, Set, MapAppendix E

Expression Trees, Heaps, Priority Queues9.1-9.2

Graphs, Graph Algorithms9.3

Exercises

You should try to do all these exercises. Pay particular close attention to those in bold.

ChapterExercises

11, 2, 7, 8, 9, 10, 16, 17, 19, 20, 21, 23, 25

21-2, 10, 11, 14-22, 28, 32

31, 9-12, 14, 18-19

41-4

5 3, 4-7, 8, 12, 13

61, 2, 7, 8, 10, 11, 12

71, 2, 5, 6-9, 11, 14, 16, 21a, 22

83, 5, 6, 9-11, 13, 15, 17, 21, 22, 27, 29, 31, 33, 35, 42-44

94, 5, 8, 10, 11-13, 19-21, 24, 25

101-3, 4, 11-17, 21