Course No.: CSE 1201
Course Title: Data Structure
Prerequisite: CSE 1101
Contact hours/week: 3
Credits: 3.00
Course Description
Introduction: Concepts and Examples of Elementary Data Objects, Necessity of Structured Data, Types of Data Structure, Ideas on Linear and Nonlinear Data Structure.
Linear Array: Linear Array & its representation in memory, Traversing LA, Insertion & Deletion in LA, Bubble Sort, Linear Search & binary Search, Multidimensional Array & its representation in memory, Algebra of matrices, Sparse matrices.
Stack: Stack representation & applications; PUSH and POP operation on stack. Polish Notation, reverse polish notation; Evaluation of a postfix expression; Transforming infix expression into postfix expression.
Queue: Its representation, Insertion & deletion in Queue, Priority Queues, Recursion [Factorial function, Fibonacci sequence, Ackermann function, Towers of Hanoi].
Linked List: Linked list & its representation in memory, Traversing, Searching, Insertion & Deletion operation on Linked list, Circular List, Header linked lists, Two way lists.
Complexity: Algorithm and flow chart, Complexity of algorithms, Rate of growth, Big-O notation, Complexity of Linear Search, Binary search & Bubble sort algorithm.
Sorting: Insertion sort, selection sort, quick sort, merge sort, Searching & data modification, Hash function, collision resolution, Chaining.
Tree: Tree terminology, representation of binary trees in memory, Traversing binary tree, Binary search tree, Insertion & deletion on binary search tree, Insertion & deletion on heap, Heap sort, B trees, General tree.
.
Grading
Quizzes/Class Test: 20 Marks* (3 best out of 4 quizzes/class tests may be taken for awarding grade)
Homework’s/Attendance: 8 Marks*
Semester Exam: 72 Marks
* - We reserve the right to change the above grading scheme.
Homework's
A new homework is released and is then due after 9 days. No grade will be given to homework submitted afterwards. Homework solutions should be written and submitted individually, but discussions among students are encouraged.
Class Outline
Referred Books
Seymour Lipschetz : Data Structure
Y. Langsam, Augenstein, A. M. Tanenbaum : Data Structures Using C and C++
Edward M. Reingold : Data structures
Robert Sedgwick : Algorithms in C
Niklaus wirth :Algorithms and Data Structures Program
Notice
Class Test Marks - #1 -
Class Test Marks - #2 -
Class Test Marks - #3 -
Class Test Marks - #4 -
Handouts
Course Details:
Lecture00 (Download)
Introduction and Overview -Lecture01-06 (Download)
Basic Terminology
Data Structure
Classification of Data Structure
Data Structure Operations
Abstract Data Type (ADT)
Algorithm: Complexity and Time-Space Tradeoff
Preliminaries - Lecture01-06 (Download)
Mathematical Notations and Functions
Algorithm Notation
Control Structure
Complexity of Algorithm
Asymptotic Notations
Sub-algorithm
Variables, Data Type
Arrays, Pointers and Records - Lecture07-11 - Part 01 (Download)
Introduction
Linear Array
Representation of Linear Array in Memory
Traversing Linear Array
Inserting and Deleting
Sorting: Bubble Sort
Searching: Linear Search
Binary Search
Arrays, Pointers and Records - Lecture07-11 - Part 02 (Download)
Multidimensional Array
Pointers: Pointer Array
Records: Record Structure
Representation of Records in Memory: Parallel Arrays
Matrices
Sparse Matrices
Linked List - Lecture12-17 - Part01 (Download - Zip)
Introduction
Linked List
Representation of Linked Lists in Memory
Linked List - Lecture12-17 - Part02 (Download - Zip)
Traversing a Linked List
Searching a Linked List
Memory Allocation; Garbage Collection
Insertion into a Linked List
Linked List - Lecture12-17 - Part03 (Download - Zip)
Deletion from a Linked List
Linked List - Lecture12-17 - Part04 (Download)
Header Linked List
Two Way Lists
Stacks - Lecture 18-22 (Download)
Stacks
Array Representation of Stacks
Linked Representation of Stacks
Arithmetic Expression: Polish Notation
Stacks - Lecture 18-22 (Download)
QuickSort; an application of Stack
Recursion - Lecture 23-27 - Part01 (Download)
Definition
Factorial Function and Procedure
Fibonacci Sequence
Divide-and-conquer Algorithm (definition and example)
Ackermann Function and Procedure
Tower of Hanoi
Queue - Lecture 23-27 - Part02 (Download)
Queue
Representation of Queue
Linked Representation of Queue
Deques
Priority Queue
Tree - Lecture 28-33 - Part01 (Download - Zip)
Binary Tree
Representing Binary Trees in Memory
Traversing Binary Trees
Traversal Algorithm using Stacks
Tree - Lecture 28-33 - Part02 (Download)
Header Nodes: Threads
Binary Search Trees
Searching and Inserting in Binary Search Trees
Deleting in Binary Search Tree
Tree - Lecture 28-33 - Part03 ( Extra - Download)
AVL Search Trees
Insertion in an AVL Search Tree
Deletion in an AVL Search Tree
Tree - Lecture 28-33 - Part04 ( Extra - Download)
m-way Search Trees
Searching, Insertion and Deletion in an m-way Search Tree
B Trees
Searching, Insertion and Deletion in a B-tree
Tree - Lecture 28-33 - Part05 ( Download )
Heap; Heapsort
Path Lengths; Huffman’s Algorithm
General Trees
Sorting and Searching - Lecture 34-36 - Part01 (Download - Zip)
Sorting
Insertion Sort
Selection Sort
Merging
Merge-Sort
Radix Sort
Sorting and Searching - Lecture 34-36 - Part02 (Download)
Searching and Data Modification
Hashing
Course No.: CSE 1202
Course Title: Sessional based on CSE 1201
Prerequisite: None
Contact hours/week: 3
Credits: 1.50
Course Description
Sessional based on the theory course CSE 1201.
Grading
Quiz Test: 20 Marks*
Homework's/Attendance: 8 Marks*
Board Viva: 25
Others: 47 Marks*
* - We reserve the right to change the above grading scheme.
Class Outline
Referred Books
Seymour Lipschetz : Data Structure
Y. Langsam, Augenstein, A. M. Tanenbaum : Data Structures Using C and C++
Edward M. Reingold : Data structures
Robert Sedgwick : Algorithms in C
Niklaus wirth :Algorithms and Data Structures Program
Notice
Quiz Test -
Attendance
Handouts
Lab Report - Template (optional)
Course Feedback
FORM - Report