Prince Sultan University

College for Women

 Department of Computer and Information Sciences

Fall 2007

 

 

COURSE OUTLINE

 

Course Code : CS210                                                           Pre-requisite: CS 102

Course Title    : Data Structures and Algorithms                                                                  
Name of Faculty: Sarab Al Muhaideb

Credit Hours    : 3                                                                   

 

 

I.     Course Description:  The fundamental data structures and their effective use in a variety of applications including lists, ordered lists, stacks, queues,  binary trees, BST's and AVL trees. Emphasis is on data structure abstraction and choice, modeling of real problems, and implementation for obtaining an efficient algorithm for solving a given problem.  The implementation and analysis of important algorithms for sorting and searching is also addressed.

 

 

II.                  Course Objectives: 

 

Knowledge

To learn different data structures used in computer programming.

To learn different Algorithms used in computer programming.

 

 

Cognitive Skills

To give the students the ability to choose the data structure that best suits a given problem

To give the students the ability to choose the algorithm that best suits a given problem

 

Interpersonal Skills & Responsibility

To work as a team member, implementing a computer programming project.

 

Numerical & Communication Skills

 

 

 

 

III.    Course Content 

 

Topics

No. of Weeks

Contact Hours

1.      Review:

1.1.   Classes and Abstract Data Types.

1.2.    Inheritance.

1.3.   Pointers and dynamic memory.

 

 

 

Week 1

 

 

4

2.      Software Development Life Cycle

2.1.   Problem Analysis and Specification.

2.2.   Design.

2.3.   Coding.

2.4.   Testing, Execution and Debugging.

2.5.   Algorithm Complexity and Analysis.

 

 

Week 2

 

4

3.      Lists.

3.1.   List as an ADT.

3.2.   A Static Array-Based Implementation of Lists.

3.3.   A Dynamic Array-Based Implementation of Lists.

3.4.   Introduction to Linked Lists.

3.5.   A Liked-List Implementation of Lists.

 

 

Week 3-4

 

7

4.      Stacks.

4.1.   Introduction to Stacks.

4.2.   Designing and Building a Stack Class- Array –Based.

4.3.   Linked Stacks.

4.4.   Use of Stacks in Function Calls.

4.5.   Case Study: Postfix (RPN) Notation.

 

 

 

Week 5-6

 

 

7

5.      Queues.

5.1.   Introduction to Queues.

5.2.   Designing and Building a Queue Class- Array –Based.

5.3.   Linked Queues.

5.4.   Applications of Queues: Buffers and Scheduling.

Week 7

4

6.      Templates.

6.1.   Function Genericity- Overloading and Templates.

6.2.   Class Genericity- Templates.

 

Week 8

 

3

7.      Searching: Binary Trees and Hash Tables.

7.1.   Linear Search and Binary Search.

7.2.   Introduction to Binary Trees.

7.3.   Binary Trees as Recursive Data Structures.

7.4.   Binary Search Trees.

7.5.   AVL Trees.

7.6.   Hash Tables.

 

Week 9-11

 

12

8.      Sorting.

8.1.   Some O(n2) Sorting Schemes.

8.1.1.      Insertion Sort.

8.1.2.      Selection Sort.

8.2.   Heaps, Heap Sort and Priority Queues.

8.3.   Quick Sort.

8.4.   Merge Sort.

8.5.   Radix Sort.

 

 

Week 12-13

 

8

9.      Review

Week 14

 

 

 

IV.    Course Components 

 

Component

Contact Hours

Lecture

35

Tutorial

13

Practical/Field

0

 

 

 

V.     Teaching Strategies (Indicate the teaching and student activities to be used to develop the kinds of learning involved in each learning domain).

               

              Domain

                   Strategy

Knowledge

Concept Presentation

Cognitive Skills

Writing C++ programs to apply concepts learned in class, case analysis

Interpersonal Skills & Responsibility

small group projects

Numerical & Communication Skills

Manual Exercises, debates, critique, group projects.

 

 

 

VI.    Course Requirements 

-          Two Major Exams and a Final Examination

-          Class Participation in Discussion  and Writing (pop quizzes)

-          Individual/ Group Programming Projects

-          Quizzes

-          Weekly Tutorials

 

VII.   Student Assessment

 

              A.   Assessment Task (Indicate the kind of assessment tasks to be used to measure student learning in each of the learning domain.  Example: quiz, oral examination,  group work, etc… ).

 

Domain

Assessment Task

Knowledge

Quizzes, Examinations, Assignments

Cognitive Skills

Quizzes, Examinations, Assignments, Computer Programs

Interpersonal Skills & Responsibility

 

Numerical & Communication Skills

Quizzes, Examinations, Assignments, Computer Programs

 

 

 

              B.  Schedule of Assessment 

 

 

Assessment

 

Assessment Task

 

Week Due

Proportion of Final Assessment

1

Quiz 1

Week 3

5%[*]

2

Major Exam 1

Week 6

20%

3

Quiz 2

Week 5

5%

4

Quiz 3

Week 9

5%

5

Major Exam II

Week 12

20%

7

Bi-Weekly Programming Project (Total of 4-5)

Weeks 3-13

10%

8

Final Examination

End of Semester

40%

 

 

 

 

 

VIII.    Learning Resources

 

A.      References -
             Textbook:

            ADT, Data Structures and Problem Solving with C++, 2nd Edition. by Larry Nyhoff, Prentice Hall, 2004.

         

Optional references:

§         C++ Plus Data Structures, By Nell Dale and David Teague, Jones and Bartlett Publishers, 2004.

§          Problem Solving with C++, The Object of Programming, by Walter Savitch, Addison Wesley, 2001.

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

 

 

Course Home Page:

             http://www.geocities.com/pscw_cs210 includes course announcements, notes, important dates, assignments, grades and more.

 

 

 

           

B.   Facilities Required -
        Electronic Lecture Class Room

 

 


[*] Lowest quiz is dropped from total

Hosted by www.Geocities.ws

1