Course: Computer Science II (CS 171)
Day/Time/Room: MW/1:30-3:10pm/WS 116
Instructor: William J. Joel
Office: WS 110
Office Hours: Posted
Email: joelw@wcsu.edu
Website: http://mathcs.wcsu.ctstateu.edu/joelw
Text: Data
Structures & Other Objects Using C++
Michael Main & Walter Savitch
Addison-Wesley, 2005
Course Objectives:
1. Discuss the design and implementation of classes in C++, specifically for dynamic arrays, lists, trees and graphs.
2. State and describe basic algorithms for list, tree and graph, traversals and sorting.
3. Evaluate the performance of a given algorithm using Big-O notation.
Tests: Five (5),
non-cumulative tests, approximately 1 hour in duration
No mid-term exam
Cumulative final exam
Assignments: Five (5) programming projects. Projects handed in early will be returned for further work if there are errors. No initial project submission will be accepted after its due date. All re-submissions are due by the next project due date.
Attendance: You are expected to be present for each class session. If you are absent, it is your responsibility to obtain class notes and handouts (if any) from your classmates; I will not keep extra copies of materials after they are initially distributed. 24-hour notice must be given if you cannot make a scheduled test, otherwise you will receive a grade of ‘0’ for the test.
Grading:
Tests 40%
(lowest dropped)
Final exam 20%
Class 10%
Total 100%
Tentative Topic Outline:
|
Week |
Topic(s) |
Due dates |
Main & Savitch |
|
1-2 |
Review Pointers Dynamic arrays |
- |
|
|
3 |
Standard Template Library |
Project 1 |
|
|
4 |
Algorithm analysis |
Test 1 |
|
|
5 |
Lists: Singly-Linked, Recursion; List traversal |
Project 2 |
|
|
6 |
Stacks & Queues |
|
|
|
7 |
Recursion |
Test 2 |
|
|
8 |
Trees: Binary trees; AVL
trees; |
Project 3 |
|
|
9 |
Trees: Search trees |
- |
|
|
10 |
Trees: M-Way trees, B-trees |
Test 3 |
|
|
11 |
Graphs |
Project 4 |
|
|
12 |
Sorting: Insertion sort; Shellsort, Heapsort |
Test 4 |
|
|
13 |
Sorting: Quicksort; Mergesort, Radix Sort |
Project 5 |
|
|
14 |
Hashing |
- |
|
|
15 |
Review for Final |
Test 5 |
|
|
16 |
Final exam |
- |
|