Data
Structures - 605227
Summer
Semester 2008/2009
Course News:
- Wednesday, July,
1:
First Day of semester.
Course Description:
Algorithmic problem solving, Data Structures (static & dynamic), lists, stacks, queues, graphs, trees, sets and dictionaries). Recursion and iteration. Students are expected to do lab experiments using C++ or Java.
Learning Outcomes:
At the end of the
course, students are expected to learn: -
How to represent and implement linked lists and their operations. -
To think recursively and implement recursion. -
Understand and utilize stacks and queues are in their implementations. -
String representations and their basic operations. -
How to allocate and deallocate memory dynamically. -
Trees terminology, their representations and their usages in applications. -
Basic vocabulary of graph concepts, graph representations.
Course Outline:
|
|
Topic |
Sections |
Notes |
|
1 |
Introduction ( 6 Hrs) |
Introduction and Motivation |
|
|
2 |
What are References? |
|
|
|
3 |
Reference and Objects |
|
|
|
4 |
Dynamic Memory Allocation |
|
|
|
5 |
Linked
Data Representation
(9 Hrs) |
Linear Linked Lists & Definition |
|
|
6 |
Linked List Diagramming |
|
|
|
7 |
Add, Delete, Search, Print |
|
|
|
8 |
Other Linked Data Structures |
|
|
|
9 |
Introduction
to Recursion (3 Hrs) |
Introduction and Motivation |
|
|
10 |
Thinking Recursively |
|
|
|
11 |
Applications |
||
|
12 |
Linear Data Structures Stacks & Queues (9 Hrs) |
Introduction and Motivation |
|
|
13 |
Some background on Stacks |
|
|
|
14 |
ADT's for Stacks and Queues |
|
|
|
15 |
Using Stacks to Check Balanced parentheses |
|
|
|
16 |
Using Stacks to evaluate Postfix Expressions |
|
|
|
17 |
Implementing the Stack |
|
|
|
18 |
How C implement Recursive Function Calls Using Stacks |
|
|
|
19 |
Implementation of Queue ADT |
|
|
|
20 |
More Queue Applications |
|
|
|
21 |
Trees (6 Hrs) |
Introduction and Motivation |
|
|
22 |
Basic Concepts and Terminology |
|
|
|
23 |
Binary Trees |
|
|
|
24 |
Sequential Binary Tree Representation |
|
|
|
25 |
Applications - Heaps and Priority Queues |
|
|
|
26 |
Traversing Binary Trees |
|
|
|
27 |
Binary Search Trees |
|
|
|
28 |
AVL Trees (Optional) |
|
|
|
29 |
Two-Three Trees (Optional) |
|
|
|
30 |
Tries (Optional) |
||
|
31 |
Graphs (6 Hrs) |
Introduction and Motivation |
|
|
32 |
Basic Concepts and Terminology |
|
|
|
33 |
Graph Representation |
|
|
|
34 |
Graph Searching |
|
|
|
35 |
Advanced
Topics (6 Hrs) |
Introduction to Algorithm Analysis |
|
|
36 |
String Processing |
Final Exam |
Textbook:
·
Java Foundations: Introduction to Program Design and Data Structures, Addison-Wesley,
2008
Suggested references:
- Data Structures and Program Design, Kruse, Leung,
Tondo, Prentice Hall.
- Data Structures through C Language.
- Data Structures using C and C++, Langsam, Augenstein,
Tenenbaum, Prentice Hall.
- Programming and Data Structures.
- Introduction to Data Structures and Algorithms with
C++.
Grading
- First Exam: 25
- Second Exam: 25
- Activity: 10
- Final Exam: 40
Tools used in the course:
- JDK 6
- Textpad 5.x