ELIZABETHTOWN COLLEGE

COMPUTER SCIENCE DEPARTMENT

CS 221

Professor: Dr. Thomas R. Leap

Office: Nicarry Hall room 243, Telephone: 361-1299, E-mail: leap@acad.etown.edu

Office Hours: Mon,Wed, Fri: 1:30 - 3:00 p.m., Tu, Th: 2:00 - 3:00 p.m.

Other hours by appointment or whenever I am in my office. Please request appointments by leaving a note on my door or in my mailbox or by leaving a voice mail message on my telephone.

Course Objective

This course is an in-depth study of data structures and object-oriented programming, their implementation, and the algorithms for using them. The applications of data structures will also be discussed. The programming language Pascal will be used in this study. However, this is not a course in Pascal and the student is responsible for becoming familiar with the language and any of its features as necessary.

Prerequisites

CS 121, CS 122, and a working knowledge of the C programming language.

Text

Data Structures and Program Design in C++, by Robert L. Kruse and Alexander J. Ryba, Prentice Hall, 1999.

Additional Reading and Reference Material (Available in the Library)

Binary Trees, by John Glen, Macintosh Software, (MRD B612).

The Art of Programming, by Donald Knuth.

Reading Assignments

Reading assignments will be made in class. Students are expected to read them before the class in which they will be discussed.

Grading

80% - Two exams and a final exam all of equal weight. The dates of exams will be announced in class.

20% - Homework, programming assignments, class participation and quizzes.

Conversion from percentages to letter grades will be performed according to the following table with any fractional part being rounded off to the nearest integer:

Exams

Make-up exams will be given only in cases of college approved absences such as for medical reasons. At the instructors option, a make-up exam may not be required.

Programming Assignments

There will be programming problems on exams which you will be expected to solve. Adequate practice on your part should make it possible to complete the exams in the time given. DO NOT rely solely on the assigned problems in preparing for exams!! Additional practice will be necessary if you are to prepare for exams adequately. Exams will coverall material covered in lectures and the reading assignments.

Programs will be graded according to the following criteria:

- Understandability and structure

- Efficiency and simplicity

- Documentation

- Program correctness

- Proof of correctness (sample executions)

- Thoroughness in handling all possible situations

Program documentation should include: an overview, a summary of procedures and how they work, operating instructions, and an explanation of the program output. Documentation should be included in the source program. Please fold all large papers to an 8 1/2 by 11 inch size and write your name, the assignment and date in the upper right-hand corner of the outside page when handing in assignments. NOTE that having a working program is not sufficient for a good grade.

Programs must be handed in during the class period on the day in which they are due. Grades on assignments WILL be lowered for each class period which they are late. Include a neat and clean listing of your program and sufficient output from trial runs to completely demonstrate that your program is correct. A program will be marked incorrect if output proving correctness is not included.

Students are expected to write their own programs. Working in small groups of no more than 2 students is acceptable so long as the work you hand in represents your COMPLETE understanding of the problem! You must also indicate anyone else that you collaborated with on the assignment. Failure to meet these requirements may result in disciplinary action.

NOTE: This syllabus will be updated in class as required.

CS 221

I.	Data Organization

	A.	ASCII coding system
	B.	Structures
		1.	Record structures	
		2.	Defining new data types
	C.	Abstract Data Types

II.	An introduction to C++ Classes

	A.	Classes in C++
	B.	Managing projects		

III.	Linear structures

	A.	Arrays and String
		1.	Array representation in memory
		2.	String representation
			a.	Sentinel character representation
			b.	Text and length representation
		3.	String operations
			a.	Character insertion
			b.	Input and output
			c.	Copying
			d.	Concatenation
			e.	Substring searching
			f.	Substring deletion and insertion

IV.	Efficiency

	A.	Searching techniques
		1.	Linear Searches
		2.	Searching times and efficiency comparison
		3.	Binary Search
	B.	Sorting techniques
		1.	Key sorts
		2.	Selection Sort
		3.	Bubble Sort
		4.	Insertion Sort
		5.	Bin Sort
		6.	Sorting times and efficiency comparison
	C.	Recursion
		1.	Quicksort
		2.	Mergesort
V.	Linear Structures

	A.	Stacks	
		1.	FILO, LIFO Lists
		2.	Parts of a stack
			a.	Top
			b.	Bottom
			c.	Stack Pointer (SP)
		3.	Stack Operations
			a.	Push
			b.	Pop
			c.	Status (Empty & Full)
		4.	Implementation
			a.	Linked lists
			b.	Arrays
		5.	Arithmetic expressions
			a.	Notations	
				(1)	Infix
				(2)	Postfix
				(3)	Prefix
			b.	Evaluation of postfix expressions
			c.	Conversion from infix to postfix
	B.	Queues	
		1.	FIFO, LILO
		2.	Parts of a queue
			a.	Front
			b.	Rear
			c.	Queue pointers
		3.	Queue operations
			a.	Insert
			b.	Remove
			c.	Full and Empty status
		4.	Implementation in arrays
			a.	Front and Rear indexes
			b.	Full/empty problem



VI.	Memory and storage allocation

	A.	Storage representation for array and record structures
		1.	Memory allocation
		2.	Record storage
		3.	Array storage
			a.	Row major form
			b.	Column major form
	B.	Static storage allocation
	C.	Stack storage allocation
	D.	Dynamic storage allocation
		1.	Pointers
			a.	Pointer representation
				(1)	Address part
				(2)	Data type
			b.	Nil pointers
			c.	Pointer values
		2.	Heap allocation and management
			a.	Heap allocation 
			b.	Heap deallocation



VII.	Linked Lists
	A.	Singly linked lists	
		1.	List structure
			a.	Elements
			b.	Links
			c.	First pointer
		2.	List insertion in front
		3.	List insertion at rear
			a.	Last pointer
		4.	Sorted lists
			a.	Searching lists
			b.	Element insertion in the middle
			c.	Element deletion
	B.	Doubly linked lists
		1.	Forward and Backward pointers
		2.	List operations
			a.	Insertion
			b.	Deletion
		3.	Dummy head and tail elements
		4.	Circularly linked lists

VIII.	Tree Structures

	A.	Binary Trees
		1.	Structure
		2.	Tree creation
		3.	Tree traversal
			a.	Preorder
			b.	Inorder
			c.	Postorder
		4.	Tree sort
		5.	Tree search
		6.	Tree insertion & deletion
	B.	Threaded Trees