CSE220: Data Structure

Taught CSE220: Data Structure across Fall 2024, Spring 2025, and Summer 2026. This course serves as an introduction to fundamental data structures and algorithms, emphasizing their construction, analysis, and implementation using a standard programming language (Java).

Pre-requisite: CSE111
Semesters Taught: Fall 2024, Spring 2025, Summer 2026
Institution: BRAC University, Department of Computer Science and Engineering

Course Description

This course provides an introduction to data structures where students study elementary data structures such as arrays, lists, stacks, queues, trees, and heaps. These data structures are used to study and implement foundational algorithms such as sorting, searching, and tree traversal. Students use a standard programming language (Java) to implement various data structures and algorithms, focusing on algorithmic efficiency, design choices, and practical problem solving.

Course Objectives

• Teach the fundamentals of circular arrays and their advantages over linear arrays.
• Demonstrate the construction and manipulation of different types of linked lists (singly linked, circular doubly linked lists).
• Introduce stack and queue data structures and explain how they are implemented and applied.
• Discuss the fundamental concept of recursion to build recursive models for computational problems.
• Discuss trees and explain related algorithms and traversals.

Course Topics & Outline

• Arrays & Circular Arrays: Linear arrays, circular array operations, shifting, rotation, and resizing.
• Linked Lists: Singly linked lists, dummy-headed circular doubly linked lists, node insertion, deletion, and traversal.
• Stacks: Array-based and linked list-based implementations, applications in parenthesis balancing and expression evaluation.
• Queues: Linear queues, circular array-based queues, and list-based queues with practical problem applications.
• Recursion: Principles of recursion, base cases, recurrence models, and recursive problem-solving.
• Hashing & Key-Indexing: Direct addressing, key-indexing, hash functions, collision resolution, and hash tables.
• Trees & Binary Search Trees (BST): Tree terminology, binary trees, binary search trees, and tree traversals (pre-order, in-order, post-order).
• Heaps: Introduction to min-heaps, max-heaps, and priority queues.
• Searching & Sorting: Linear and binary search; elementary and advanced sorting techniques.

Course Outcomes (COs)

• CO1: Show different operations such as insertion, removal, rotation, shifting, etc. on linear arrays, circular arrays, linked lists, stack, queue, and tree data structures.
• CO2: Demonstrate basic algorithms related to searching and tree traversal using various data structures.
• CO3: Compare the suitability and merits of various data structures and basic algorithms when given certain requirements or constraints.
• CO4: Apply concepts of recursion to solve programming problems.
• CO5: Construct general-purpose data structures and basic algorithms for solving programming problems.

Textbooks & Reference Materials

1. Algorithms in Java, Robert Sedgewick and Kevin Wayne, 4th Edition, Addison-Wesley, ISBN-10: 032157351X, ISBN-13: 978-0321573513.
2. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 3rd Edition, MIT Press, ISBN-10: 0262033844, ISBN-13: 978-0262033848.
3. Departmental lecture slides, problem sets, and course materials provided via buX.