Transcript CSCI 210 Data Structures & Algorithms

CSCE 210
Data Structures and Algorithms
Prof. Amr Goneid
AUC
Part 0. Course Outline
Prof. Amr Goneid, AUC
1
Course Resources
 Instructor: Prof. Amr Goneid
 E-mail: [email protected]
 Office: Rm 2152 SSE
 Textbook: "ADTs, Data Structures and Problem
Solving with C++" by Larry Nyhoff, 2nd Edition,
Pearson Prentice Hall, 2005
 Reference: "Problem Solving, Abstraction, and
Design using C++" by Friedman and Koffman, Fourth
Edition, Addison Wesley, 2005
 Lab: To be assigned soon
 Web Site: www.cse.aucegypt.edu/~csci210/
Prof. Amr Goneid, AUC
2
Course Goals
 To
introduce concepts of Data Models, Data
Abstraction and ADTs in problem solving and S/W
development
 To deepen the experience in Object Oriented
Programming as an efficient software development
methodology.
 To gain experience in the design of algorithms for
problem solving and to introduce the concepts of
algorithm analysis
 To gain experience in the design and implementation
of various ADTs and their applications to practical
problems
Prof. Amr Goneid, AUC
3
Course Contents
Revision and Expansion on CSCI 110 Material
R1. ADTs as Classes (Revision of some CSCI 110 material)
R2. Elementary Data Structures (Revision of some CSCI 110 material)
R3. Dictionaries(1): Key Tables and Lists (Revision of some CSCI 110
material)
Prof. Amr Goneid, AUC
4
Course Contents
Data Modeling and ADT’s
2.
Simple Containers: Stacks and Queues
2.
Introduction to the Analysis of Algorithms
3.
Trees
4.
Dictionaries(2): Binary Search Trees
5.
Dictionaries(3): Hash Tables
6.
Priority Queues
7.
Sorting
Sorting (1): Elementary Algorithms
Sorting (2): (n log n) Algorithms
9.
The Set Data Structure: Disjoint Sets
10. Graphs
1.
Prof. Amr Goneid, AUC
5
Course Contents
R1

ADTs as Classes
(Revision of some CSCE 110 material)







Class Definition: Private & Public Members
Constructors & Destructor
Data and Function Members
Accessors & Mutators
Polymorphism and Overloading
Example: Rational Numbers Class
Example: Simple String Class
Prof. Amr Goneid, AUC
6
Course Contents
R2

Elementary Data Structures
(Revision of some CSCE 110 material)
 Static and Dynamic Data Structures
 Static Arrays
 Pointers
 Run-Time Arrays
 The Linked List Structure
 Some Linked List Operations
 Variations on Linked Lists
Prof. Amr Goneid, AUC
7
Course Contents(continued)
R3
Dictionaries(1):Key Tables and Lists
 The Key Table




ADT Key Table
The Key Table Class Definition
Key Table Class implementation
Example Application
 The Linked List
 ADT Linked List
 The Linked List Class Definition
 Linked List Class implementation
 Example Application
Prof. Amr Goneid, AUC
8
Course Contents
Part 1

Data Modeling and ADTs







Data Modeling
Abstract Data types (ADTs)
A Classification of Abstract Structures
Another Classification
Special Data Structures
OOP and Classes
Examples on Modeling
Prof. Amr Goneid, AUC
9
Course Contents(continued)
Part 2

Simple Containers: Stacks and Queues








Introduction to the Stack data structure
Designing a Stack class using dynamic arrays
Linked Stacks
Some Applications of Stacks
Introduction to the Queue data structure
Designing a Queue class using dynamic arrays
Linked Queues
An Application of Queues
Prof. Amr Goneid, AUC
10
Course Contents(continued)
Part 3

Introduction to the Analysis of Algorithms
 Algorithms
 Analysis of Algorithms
 Time Complexity
 Bounds and the Big-O
 Types of Complexities
 Rules for Big-O
 Examples of Algorithm Analysis
Prof. Amr Goneid, AUC
11
Course Contents(continued)
Part 4

Trees


Binary Trees
Tree Traversal
Prof. Amr Goneid, AUC
12
Course Contents(continued)
Part 5

Dictionaries(2): Binary Search Trees







The Dictionary Data Structure
The Binary Search Tree (BST)
Search, Insertion and Traversal of BST
Removal of nodes from a BST
Binary Search Tree ADT
Template Class Specification
Other Search Trees (AVL Trees)
Prof. Amr Goneid, AUC
13
Course Contents(continued)
Part 6

Dictionaries(3): Hash Tables







Hash Tables as Dictionaries
Hashing Process
Collision Handling: Open Addressing
Collision Handling: Chaining
Properties of Hash Functions
Template Class Hash Table
Performance
Prof. Amr Goneid, AUC
14
Course Contents(continued)
Part 7

Priority Queues
 Definition of Priority Queue
 The Binary Heap
 Insertion and Removal
 A Priority Queue Class
Prof. Amr Goneid, AUC
15
Course Contents(continued)
Part 8a

Sorting(1): Elementary Algorithms
 General
 Selection Sort
 Bubble Sort
 Insertion Sort
Prof. Amr Goneid, AUC
16
Course Contents(continued)
Part 8b

Sorting(2): (n log n) Algorithms

General
 Heap Sort
 Merge Sort
 Quick Sort
Prof. Amr Goneid, AUC
17
Course Contents(continued)
Part 9

The Set Data Structure: Disjoint Sets







What are Disjoint Sets?
Tree Representation
Basic Operations
Parent Array Representation
Simple Find and Simple Union
Disjoint Sets Class
Some Applications
Prof. Amr Goneid, AUC
18
Course Contents(continued)
Part 10
Graphs
 Basic Definitions
 Paths and Cycles
 Connectivity
 Other Properties
 Representation
 Examples of Graph Algorithms:



Graph Traversal
Shortest Paths
Minimum Cost Spanning Trees
Prof. Amr Goneid, AUC
19
Summary
Part No.
Subject
R1
ADTs as Classes
R2
Elementary Data Structures
R3
Dictionaries(1): key Tables and Lists
Book
Chapter
4
2 , 3, 6
6
1
Data Modeling and ADTs
2,3
2
Simple Containers: Stacks and Queues
7,8
3
Introduction to the Analysis of Algorithms
10
4
Trees
12
5
Dictionaries(2): Binary Search Trees
12
6
Dictionaries(3): Hash Tables
12
7
Priority Queues
13
8a
Sorting(1): Elementary Algorithms
13
8b
Sorting(2): (n log n) Algorithms
13
9
The Set Data Structure: Disjoint Sets
16
10
Graphs
16
Parts R1,R2,R3 are revisions of CSCE110 material
Prof. Amr Goneid, AUC
20
Lab Assignments
Hands-on experience will be gained through programming projects
that cover the course material. Design documents are required for
all the problems given.
Design Document:
The basic items in the design document will include:

Problem Definition

Requirement Specifications

Solution Strategy

S/W Design for the whole problem:
Structured (Top-Down) Design in the form of modules
(C++ functions) in which each module is associated with a
given subproblem.
Prof. Amr Goneid, AUC
21
Lab Assignments
 S/W Design for Each Module:





Functional Specifications: the purpose of the module
and what it is supposed to do (What to do)
Data Specifications: the data resources needed by the
module to achieve it functionality (with what)
Precondition: the state of processing or data before the
module is executed (state before)
Postcondition: the state of processing or data after the
module is executed (state after)
Algorithm Specification: the algorithm or methodology
used by the module (How to do it)
Prof. Amr Goneid, AUC
22
Coursework Grading
 30% Programming Assignments.
 5 % Quizzes, class participation and
attendance
 20% Midterm Exam (1)
 20% Midterm Exam (2)
 25% Final Exam
Prof. Amr Goneid, AUC
23
Course Outcomes
After completing the CSCE 210, students should be able to:
1. Demonstrate knowledge and understanding of Data Models,
Data Abstraction and ADTs and their role in problem solving
and S/W development.
2. Choose the appropriate data structure for modeling a given
problem.
3. Design and implement various ADTs in a high level language
(C++) using Object Oriented Concepts. Topics include Linked
lists, Simple Containers (Stacks, Queues), Dictionaries (Key
Tables and Lists, Binary Search Trees, Hash tables), Priority
Queues and Heaps, Disjoint Sets and Graphs.
Prof. Amr Goneid, AUC
24
Course Outcomes
4.
5.
6.
7.
Compare alternative implementations of data structures with
respect to performance.
Demonstrate experience in the design of algorithms for solving
problem that use the above data structures.
Demonstrate knowledge of common applications for each data
structure in the topic list.
Practice basic algorithm analysis using complexity bounds
(Big-Oh, Big-Theta and Big-Omega). Applications include
Quadratic Sorting methods and Divide & Conquer recursive
sorting (n log n) examples (Merge Sort and Quick Sort).
Prof. Amr Goneid, AUC
25