Dr. Alisa Neeman Assistant Professor
  • (740) 245-7042

Data Structures CS 22003

 

 

COURSE SYLLABUS

Fall 2011

August 20-December 7 2012

Lecture:   Mon, Wed, Fri 10:30-11:20

 

Data Structures
CS22003
Computer Science

 

Professor:  Alisa Neeman

Phone:       245-7042

Email:       aneeman@rio.edu, Web site: http://faculty.rio.edu/aneeman
Office:      308 McKenzie Hall
Office Hours:  M, W 12:30-1:30 pm? F 9:30-10:30 am, 1:30-3:30 pm

 

 

COURSE DESCRIPTION:  This course builds on the concepts introduced in CS20104 and CS20204 Computer Programming I and II with emphasis on algorithms design and analysis, object-oriented design, data structures, and software engineering. Data structure topics include stacks, queues, hashing, linked lists, trees, and graphs.

PREREQUISITES:  CS20204 (Programming II)

CREDIT HOURS:   3

TEXTBOOK AND OTHER REQUIRED MATERIALS:

Lewis, J., DePasquale, P., Chase, J. Java Foundations: Introduction to Program Design & Data Structures,  2011,  ISBN: 978-0-13-212881-0. Addison-Wesley.

SOFTWARE:

The J2SE Development Kit (JDK). http://java.sun.com.
Netbeans: http://www.netbeans.org

PROGRAM OUTCOMES--The following outcomes have been adopted for the degree program for which this course is required:

1.     Develop the critical thinking skills and logical skills.

2.     Master modern programming methods and systems.

3.     Be able to analyze problems, form a plan, and a design a solution.

4.     Understand different aspects of computer software and hardware.

5.     Have a clear understanding of the Software Life Cycle.

COURSE OUTCOMES:  The following outcomes have been adopted for this course.  All outcomes listed below have direct relevance to course material.  Upon completion of this course students are expected to:

1.     Understand advanced data structures in Object Oriented programming language

2.     Develop efficient algorithms

3.     Measure algorithm efficiency

4.     Understand Abstract Data Types

5.     Understand recursion and develop recursive methods

6.     Understand and implement data collections

7.     Understand and write common structures such as: stacks, queues, linked lists, and trees

8.     Use common data structures to solve complicated problems

9.     Understand sorting and searching

10.  Understand Hashing techniques

 

GRADING POLICIES/TESTING/ASSIGNMENTS/ATTENDANCE/EXPECTATIONS
Grade calculation                                                                                                                                        

 

% of Grade

Programming Assignments

45%  (10% will be deducted for every day late)

Homeworks and Quizzes

10%  

2 Exams

15% each (5th and 10th week)

Final Exam

15%

 

Scale

 

A:  93%,  A-:90%

B+: 87%, B: 83%, B-: 80%

C+: 77%, C: 73%, C-: 70%

D+: 67%, D: 63%, D-: 60%

F  = < 60%

 
 
 

           

Exams:  There will be two exams during the semester. They will be given during the 5th and 10th week of classes. The exams will cover material discussed in class, labs, programming assignments, and book chapters. Final exam will be comprehensive.

Classroom and Lab Behavior:  The use of mobile devices (making calls, texting, emailing, etc) is not permitted during class and lab times. You may leave your phone on vibrate or silence mode in order to receive emergency calls.

Academic Integrity:

All students are expected to present and represent their own original work and properly credit sources used in preparation of their own original work. Discussion of programming assignments and helping each other with debugging is permissible but copying from others or the internet is not permissible. Data Structures is a core course and you will learn more from attempting the assignments than from copying.

Harassment Policy

The University and Community College strongly disapprove and expressly prohibit any form of harassment or discrimination based on race, color, national origin, ancestry, religion, sex, age, sexual orientation, disability, veteran status, marital status or any other characteristic protected by applicable federal, state or local laws.

ADA POLICY: If a student wishes to be identified as having a physical, mental, or learning disability, that may or may not require reasonable accommodation(s), he/she must register with the Office of Accessibility.  These registered students should identify themselves to their instructors and provide a written statement from the Accessibility Office that indicates the appropriate accommodations.  The process of a student self-proclaiming the need for accommodation should occur as early in the semester as possible.  The Office of Accessibility phone is 245-7339 and is located in Rhodes Hall, Room 116, University of Rio Grande.

FERPA:  The University of Rio Grande and Rio Grande Community College are committed to fully respecting and protecting the rights of students under the Family Educational Rights and Privacy Act (FERPA).  These rights generally include the right to inspect, review and seek amendment to the student's education records and the right to provide written consent before personally identifiable information from education records is disclosed.  Under FERPA, students have the right to file a complaint with the US Department of Education concerning alleged failures to comply with FERPA.  Please see the Student Records Confidentiality/Rights Under FERPA section of the Student Handbook for details and more information.

 

TOPIC OUTLINE

1.     Analysis of Algorithms (Ch. 12)
Algorithm Efficiency
Growth Rate Functions and Big-O Notation
Comparing Growth Rate Functions
Determining Time Complexity

2.     2D Arrays  (Ch. 7)

3.     Collections (Ch. 14)
Introduction to Collections
Stack Collection
A Stack ADT
Exceptions
Implementing a Stack: With Arrays
The ArrayStack Class

4.     Linked Structures (Ch. 14)
References as Links
Elements Without Links
Implementing a Stack

5.     Queues (Ch. 14)
A Queue ADT
Implementing Queues: With Links
Implementing Queues: With Arrays

6.     Lists  
A List ADT
Ordered Lists
Indexed Lists
Implementing Lists: With Arrays
Implementing Lists: With Links (Ch. 14)
Lists in the Java Collections API

7.     Recursion (Ch. 11)
Recursive Thinking and Programming
Using Recursion
Analyzing Recursive Algorithms

8.     Sorting and Searching (Ch. 13)

9.     Trees (Ch. 16)
Strategies for Implementing Trees
Tree Traversals
A Binary Tree ADT
Using Binary Trees: Expression Trees
Implementing Binary Trees with Links
Implementing Binary Trees with Arrays

10.  Binary Search Trees (Ch.17)
A Binary Search Tree
Implementing Binary Search Trees: With Links
Implementing Binary Search Trees: With Arrays
Using Binary Search Trees: Implementing Ordered Lists
Balanced Binary Search Trees
Implementing Binary Search Trees: AVL Trees
Implementing Binary Search Trees: The Java Collections API

11.  Priority Queues & Heaps (Ch. 18)
Using Heaps: Priority Queues
Implementing Heaps: With Arrays
Using Heaps: Heap Sort

12.  Hashing (Ch. 20)
Hashtable structures
Hashing Functions 
Resolving Collisions
Deleting Elements from a Hash Table
Hash Tables in the Java Collections API