COMMUNITY COLLEGE OF ALLEGHENY COUNTY
COURSE NUMBER: CIT505 COURSE TITLE: Data Structures and
Algorithms
SEMESTER CREDITS: 4 credits/ 4
class hours PREREQUISITES: CIT503
CATALOG COURSE DESCRIPTION
This
course focuses on understanding the dependence of execution time, bandwidth and
memory requirements on the data structures and algorithms chosen. Students
learn to reason informally about algorithm and data structure correctness and
complexity. Primary emphasis is given to intelligent selection of algorithms
and representations. Programming assignments use C++ and the Standard Template
Library. Topics: abstract data types;
data structures and invariants; simple algorithm analysis; sorting and
searching; trees and graphs; associative data structures; C++ programming with
the STL. (This is Carnegie Technology
Education (ICARNEGIE/CMU) course SSD5; it is comparable to CIT245, and can be
used in place of CIT245 in all CCAC programs.)
Familiarity
with the C or C++ programming language is recommended before taking this
course. Students not having this
background should consider not taking this course. Students not having this background should consider taking CIT145
prior to CIT505. Also, students should
have math abilities equivalent to MAT135 or MAT142.
LEARNING
OUTCOMES:
Upon
successful completion of this course, the student should be able to:
· Reason informally about algorithms and data
structures chosen to solve a problem
· Chose an appropriate algorithm and data
representation to solve problems selected
· Program in C++ at an intermediate level, using both
object-based and object-oriented approaches
· Use the Standard Template Library in problem
solutions
· Be familiar with selected data structures, including
vectors, linked lists, stacks, queues,
graphs, trees and hash tables.
LISTED TOPICS
Unit 1. Introduction
to C++
1.1
The Basic
Language: Introduction, Expressions and Types, Statements, Functions, Input
and Output,
Program
Organization, Debugging and Testing, Examples
1.2
Pointers and References,
C++ Memory Model: Pointers, Pointer Arithmetic, References, Memory Management
C-style Strings, Examples
1.3
Object-Based
Programming: Classes, Con/Destructors, Operator
Overloading, Function Objects, User-Defined Types
Examples
1.4 Templates: Template Functions, Template
Classes, Examples
1.5 Object-Oriented
Programming: Object-Oriented Programming, Polymorphism, Examples
1.6 Algorithms
and Recursion: Algorithms,Recursive
Functions, Recursive Types, Examples
1.7 Performance
Analysis and Measurement: Program
Analysis, Asymptotic Analysis, Examples
Multiple-choice Quiz 1, Practical Quiz 1, Exam 1
Unit 2. Problem
Solving with the STL
2.1 The
Standard Template Library: STL Overview, STL Containers, STL
Iterators, STL Algorithms, Examples
2.2 An
Example: Student Records: Student
Records, Examples
2.3 Sequential
Container Types: Vectors, Matrices, Linked Lists, Stacks, Queues, Graphs, Graph
Exploration, Examples
2.4 Trees: The Tree Data Model, Binary
Trees, Binary Search Trees, Examples
2.5 Hash
Tables: Hash Tables, Implementing Hash Tables, Examples
Multiple-choice Quiz 2, Practical Quiz 2, Exam 2
REFERENCE, RESOURCE, OR LEARNING
MATERIAL TO BE USED BY STUDENT:
1. Use of ICARNEGIE's web based materials for topics,
including quizzes, exercises, and exams.
Instructors will strictly adhere to iCarnegie criteria
regarding course content, materials, procedures, and grading.
2. Appropriate
textbook on Data Structures & Algorithms and the C++ language.
This is iCarnegie course SSD5