Optional texts

Any C++ book,

“Beginning C++” (by Ivor Horton) recommended

Attendance Although class attendance is not mandatory, you are responsible for whatever is done in class. While our textbooks cover most basic concepts, class is your only source for the specifics that will allow you to learn the material – and pass the class. Make sure you get the notes and assignments if you miss a class. You should get at least one other students phone number.

Grading Your grade will be determined by your performance on 3 in-class examinations and a number of programming assignments. Attendance is not mandatory but class participation will also be taken into account.

These will contribute to your grad as follows:

Programming assignments 20 %

Mid term #1 25 %

Mid term #2 25 %

Final exam 30 %

Programming assignments

There will be a total of 5-6 programs assigned throughout the semester. Your programs will run on PC’s using any C compiler (Visual C++ Ver.6.0 or higher recommended) or on the Unix platform (up to you).

The programs will be assigned roughly every two weeks. Typically, each program will be due two weeks after it is assigned. There will be a penalty for lateness, 10 % per week late. Each program will be graded and returned to you, usually within a week.

All handouts and assignments are posted on my web page. You are responsible to download them before each class meeting !!!

Course Outline

· Course overview

· CIS 15 review – advanced array and string handling, pointers, struct types, dynamic memory allocation, function parameter passing, the preprocessing phase, macros, header files, separate and conditional compilation, file I/O.

Mastering the review topics is essential in order for you to proceed with the main topics of this course, without a thorough understanding of these topics you will encounter difficulties with the technical details (code) that are necessary to implement the concepts covered in class.

· Introduction to data structures and ADT’s.

· Stacks – concept, applications, array implementation in C, infix/postfix/prefix expressions.

· Recursion

· Queues – concept, array implementation in C, priority queues

· Introduction to C++ for data structures – A tutorial will be handed out and covered in class. The topic will be summarized by a C++ implementation of stacks.

· Linked lists – concept, nodes, linked lists, stack and queues as linked lists, ordered linked lists, array implementation, dynamic implementation, C++ implementation of: dynamic linked lists, dynamic stacks and queues.

· Advanced list structures, C++ implementation – introduction to Inheritance in C++, sorted linked lists, priority queues, list iterators, circular lists, doubly linked lists.

· Trees – concept, binary trees, traversing binary trees, expression trees, binary search trees, implementation in C and C++, array implementation, deleting from binary trees, threaded binary trees, general trees and forests.

· Sorting – efficiency considerations, O notation, bubble sort, quick sort, selection sort, insertion sort, binary tree sort, merge sort, heap sort, radix sort.

· Searching – search algorithms, index structures, hashing.