Study Notes for CSC301: Data Structures

CSC301: Data Structures Course Notes

Course Contents

  • Course Units: 3 Units

  • Lecture Hours (LH): 30

  • Practical Hours (PH): 45

  • Topics Covered:

    • Primitive types

    • Arrays

    • Records

    • Strings and String Processing

    • Data Representation in Memory

    • Stack and Heap Allocation

    • Queues

    • Trees

    • Implementation Strategies for Stacks, Queues, Trees

    • Run Time Storage Management

    • Pointers and References

    • Linked Structures

  • Lab Work:

    • Writing C/C++ functions to perform practical exercises and implement algorithms on arrays, records, string processing, queues, trees, pointers, and linked structures.

Learning Outcomes

At the end of this course, students should be able to:

  1. Discuss the appropriate use of built-in data structures.

  2. Apply object-oriented concepts (inheritance, polymorphism, design patterns, etc.) in software design.

  3. Implement various data structures and their algorithms, and apply them in simple applications.

  4. Choose the appropriate data structure for modeling a given problem.

  5. Analyze simple algorithms and determine their efficiency using big-O notation.

  6. Apply the knowledge of data structures to other application domains such as data compression and memory management.

Textbooks

  1. Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data Structures and Algorithms in Python. John Wiley & Sons Ltd.

  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.

Course Writer/Developer

  • Dr. Femi E. Ayo

  • Department of Computer Sciences, Olabisi Onabanjo University, Ago-Iwoye

  • Email: ayo.femi@oouagoiwoye.edu.ng

1. Data Structures

1.1 Introduction

  • Data: Organized in various forms.

  • Data Structure: A logical or mathematical model for organizing data.

  • Key considerations in choosing a data structure:

    1. Short access time.

    2. Ease of update.

    3. Economy of storage.

    4. Simple maintenance.

    5. Reliability.

1.2 Basic Terminology

  • Data: Values or sets of values.

  • Data Items: A single unit of values.

    • Group Items: Data items divisible into sub-items (e.g., an employee name).

    • Elementary Items: Data items that cannot be further divided (e.g., Social Security Number).

  • Entity: An object with attributes that can hold values.

    • Example: Attributes (Name, Age, Sex) and values ("Rohland Gail", 34, "F").

  • Entity Set: Collection of entities sharing similar attributes.

  • Field: A single elementary unit representing an attribute of an entity.

  • Record: A collection of fields from a given entity.

  • File: A collection of records. Each record may be uniquely identified by a primary key.

1.3 Classification of Records

  • Records classified by length:

    • Fixed-length Records: Same length for all records.

    • Variable-length Records: Different lengths (e.g., student records with varying numbers of courses).

  • Classification of data structures typically involves a few steps:

    1. Logical/mathematical description.

    2. Implementation on a computer.

    3. Quantitative analysis (memory and processing time).

1.4 Classification of Data Structures

  • Primitive Data Structures: Fundamental data types supported by programming languages (integers, floats, characters, booleans).

  • Non-Primitive Data Structures: Data structures derived from primitive data structures (arrays, linked lists, trees, etc.).

  • **Linear Data Structure:

    • Characteristics:** Elements form a sequence (e.g., arrays, linked lists).

  • Non-linear Data Structure: Elements not arranged sequentially, representing hierarchical relationships (e.g., trees, graphs).

1.5 Arrays

  • Definition: A collection of similar data types indexed by integers.

  • Notation:

    • 1-D Array: Elements denoted as $A[1], A[2],
      ightarrow A[N]$.

    • 2-D Array: Elements denoted as $A[i][j]$.

Example 1: A linear array 'STUDENT' having names of six students:

  • Example 2: A 2-dimensional array to store store sales with 28 rows (stores) and 4 columns (departments) denoted as:
    SALES[i][j]extwhereiisthestoreindexandjisthedepartmentindex.SALES[i][j] ext{ where i is the store index and j is the department index.}

  • Example 3: Address calculations using defined formulae for array addresses.

    • Length Calculation:
      extLength=extUpperBound−extLowerBound+1ext{Length} = ext{Upper Bound} - ext{Lower Bound} + 1

    • Address Calculation:
      extLOC(A[K])=extBase(A)+w(K−LB)ext{LOC}(A[K]) = ext{Base}(A) + w(K - LB)

1.6 Trees

  • Definition: Non-linear data structures representing hierarchical relationships.

  • Key Properties of Trees: Examples illustrate structures such as an employee record hierarchy.

1.6.1 Binary Trees

  • Definition: A tree structure with each node having at most two children (left and right).

  • Node Definitions: Terminal nodes (no children), internal nodes (at least one child).

  • Algebraic Representations:

    • Example of how binary trees can represent algebraic expressions by parsing those expressions through tree notation.

1.6.2 Complete Binary Trees

  • A tree of height d having nodes filled as much as possible.

    • Formula for depth $dn = loor{ ext{log}2 n + 1 }$

1.7 Representation of Binary Trees in Memory

  • Linked Representation: Uses three parallel arrays: INFO, LEFT, RIGHT.

  • Sequential Representation: Uses a single linear array where the indexing follows specific rules.

1.8 Traversing Binary Trees

  • Types of Traversal: Preorder, Inorder, Postorder methods described in detailed steps.

  • Example algorithms provided with sample trees illustrating traversal orders.

2. Stacks and Queues

2.1 Stack

  • Definition: LIFO (Last In First Out) structure for storing elements.

  • Operations: PUSH (insert) and POP (remove).

  • Example operations illustrated using a visual stack.

2.2 Queue

  • Definition: FIFO (First In First Out) structure where one can insert at the rear and remove from the front.

  • Example operations illustrated with a visual queue.

3. Graphs and Their Applications

3.1 Graph Theory Terminology

  • Graph Composition: Nodes (vertices) and edges.

  • Directed and Undirected Graphs: Definitions and examples.

  • Key Concepts: Degree, paths, cycles, connected graphs, complete graphs.

3.2 Representation of Graphs in Memory

  • Adjacency Matrix and List: Efficient storage and retrieval techniques explained.

4. Records, Strings, and String Processing

4.1 String Basic Terminology

  • Definitions: Strings, length, empty strings, substrings, concatenations, in C language representation.

4.2 Storing Strings

  • Methods of storage: Fixed-length, variable-length, and linked structures.

5. Linked Lists

5.1 Introduction

  • Definition and Characteristics: Comparison with arrays, strengths, and weaknesses discussed.

5.2 Types of Linked Lists

  1. Single Linked List

  2. Double Linked List

  3. Circular Linked List

  4. Circular Double Linked List

5.3 Operations on Linked Lists

  • Basic Operations: Creation, insertion, deletion, traversal methods detailed along with examples.

6. Data Structures Operations

6.1 Common Operations

  1. Traversing: Accessing nodes/records.

  2. Searching: Finding desired nodes based on keys.

  3. Inserting: Adding new nodes/records.

  4. Deleting: Removing nodes/records from structures.

6.2 Sorting and Merging

  • Definitions of specific algorithms for sorting (e.g., Bubble sort, Merge sort, etc.).

6.3 Searching Techniques

  • Detailed algorithms and complexity analysis for linear and binary search.

7. Conclusion

Exercises

  • A comprehensive list of exercises designed to reinforce learning objectives and practical skills with data structures, algorithms, and coding practices in C/C++.