Department of CSE
CSE 220: Data Structure
Spring 2005
By Manzur Ashraf
Objective:
To understand the basis of efficient computer programming.
Expectations:
To apply the learning into real-life computer programming in the best way.
Text:
Larry R Nyhoff, C++: an introduction to data
structure
Ref: E. M Reingold, Data
Structure
Ref
web address regarding relevant tutorials: http://www.oocities.org/manzur_bd
|
symbols |
meaning |
|
# |
Advanced and generic idea
from classical examples |
|
N |
Larry R Nyhoff,
C++: an introduction to data structure |
|
R |
E. M Reingold,
Data Structure |
|
T |
Tutorials posted in webaddress (http://www.oocities.org/manzur_bd) |
1.
Preliminary: Overview of basic computation upon
architecture (#), compilation of high level to lower level languages, scenario
of memory and role of operating system, evolution of data structure over there.
à Aspects and applicability of Data Structure in
Computer Sc. & Engg
à Our objective in this course (and Lab)
Ref: class notes, R- ch1
2.
Array and Linear
searching, binary searching, entering element in array data structure;
Ref:
R- ch 1.3
Efficiency and cost of a program using
probabilistic approximation, operator counts, space time analysis
3.
Structure:
applicability and “a general database engine” simulation (#)
Structure
Ref: (T)
Packed
words (R- ch 2.3) and string (#)
Coding
systems ( R- ch 2.4, #)
4.
Pointers and
applicability (T)
Linked
Lists (T)
Problems:
Sparse polynomials ( N ch
9.2), sparse matrices ( N ch 9.5), generalized list (
N 9.5),
5.
Stack ( T, #, R ch 4)
Problems-
(#)à Program execution,
function calls and stack usability ( additional ref: N
4.3)
Reverse
polish notation ( N- 4.3)
Base
conversion (N 4.1), 2-way stack
6.
Queue ( T, #, R ch 4)
Problems-
scheduling queues ( N 5.1), circular queue (N 5.1)
7.
Recursion ( N ch 7.1,7.2)
8.
Graphs –
implementing using different types of data structure ( R ch
4, #)
9.
Binary tree (
Ordering and implementation) ( T)
n
Traversing
n
Heap ( N)
10.
Hashing ( R ch 7.4)
11.
Sorting ( N, T)
12.
B tree, B+ tree,
AVL tree, Threaded tree, Digraphs (N)
[ Topics
can be adjusted according to instructor later ]