CS 260 – Data Structures	May 2009

Course Title:	Data Structures
Course Number:	CS 260
Credit:	4
Institution:	Clackamas Community College
Outline Developed by:	Nick Molatore
Course Description:
Topics include linked lists, binary trees, balanced trees, forests, graphs, sorting techniques, algorithms and their analysis.
Expected Student Outcomes: 
	Upon successful completion, the student should be able to
•	Apply data abstraction in a C++ programming problem. 
•	Become proficient at evaluating the benefits and drawbacks of their design in terms of memory and run time efficiency. 
•	Program using classes and linear linked lists, circular linked lists, doubly linked lists, binary search trees, arrays of linear linked lists. 
•	Select the proper sorting algorithm for a problem. 
•	Design solutions to problems requiring complex data structures (combinations of lists, stacks, queues, hash tables, and trees). 
•	Apply data abstraction. 
•	Apply both static and dynamic implementations of lists, stacks, queues, hash tables and trees. 
•	Build and traverse data structures to manage a simple graph. 
•	Apply recursion and key transformations. 
•	Make judgments about the practical and social application of algorithm concepts as they apply to large scale programming projects
Length of Course:
One quarter with 4 lecture hours and 2 lab hours per week
Prerequisite:
CS162
Grading Method:
Letter grades are assigned on the standard 10% increment scale. The course may also be taken as a Pass/No-Pass by prior arrangement only.
Required Texts:
C++ Programming: Program Design Including Data Structures  by D. S. Malik. 3rd edition

Use of library and information resources is integrated into computer science certificate and degree programs in general education requirements and in computer science classes as relevant to the curriculum. Use of library and information resources is encouraged and students can access a variety of program-appropriate materials via the library's web-based electronic databases and print materials. Instruction in use of library  and information resources is available to all students

Course Outline
I.	Data Structures	 4
	A.	Review
		1.	ADT (Abstract Data Type)
		2.	stacks, queues
		3.	Implementation of ADT
	    	4.	linear and linked lists

II.	Sorting and Algorithm Analysis	12
	A.	Sorting Arrays
		1.	Insertion
		2.	Selection
		3.	Exchanging
		4.	Shell
		5.	Heapsort
		6.	Quicksort
	B.	Sorting Files
		1.	Mergesort
		2.	Balanced Mergesort

II.	Recursive Algorithms	 6
	A.  When to use recursion and when not to use recursion
	B.	Backtracking Algorithms
		1.	Knight Tours
		2.	Eight Queens
		3.	Optimal Solution
	C.	Recursive data types
	D.	Top down parsing

III.	Trees		10
	A.	Concepts and terminology
	B.	Binary trees
	C.	Binary search trees
	D.	General trees

IV.	Key Transformation (Hashing)	3
	A.	Transformation functions
	B.	Collision handling

V.	Exams and review	5

VI. Labs	30

Total		70