Data Structures Lecture Notes PDF

# Basic Concepts - **Motivation**: Consider a product from another Engineering discipline (e.g., building, bridge, car, boat etc.) - We can consider a product from several points of view: - **Components:** - What are the components? - What are their specificat...

# Basic Concepts - **Motivation**: Consider a product from another Engineering discipline (e.g., building, bridge, car, boat etc.) - We can consider a product from several points of view: - **Components:** - What are the components? - What are their specifications? - **Implementation**: How are the components constructed (from raw materials and other components)? - **Architecture**: Arrangement of components. # Program = Algorithms + Data Structures - **What are Data Structures?** - a particular way of organizing data in a computer so that it can be used effectively. - **Clever Ways** to organize information in order to enable efficient computation: - What do we mean by clever? - What do we mean by efficient? - **What are Algorithms?** - a set of instruction or a step by step procedure written to carry out certain tasks or solve a particular function. # Picking the Best Data Structure for the Job - **The data structure** you pick needs to support the **operations** you need - Ideally it supports the **operations** you will use most often in an efficient manner. - **Examples of operations:** - A List with operations insert and delete - A Stack with operations push and pop # Crafting a Program - **Four main ideas** used in creating complex computer programs: - Data Abstraction - Modularity - Algorithmic complexity - Standard Tools # Dealing with Abstraction - **Abstraction:** - Allows you to capture common patterns in things and ignore inessential details. - By abstract we mean that there's more than one way that it could be implemented. - Which one we use doesn't matter to the user of the type. - **Black Box Abstraction:** - Allows us to use things without knowing how they work. For example, a telephone. - **Data Hiding:** - Allows use of a program component without knowing the specifics of how it is implemented. # Layers of Abstraction - We can build up layers of abstraction to create complexity. - Without layers of abstraction we could not understand the most complex programs (e.g. Microsoft Word ~ 1,000,000 lines of code). # Abstract Data Type (ADT) - **Abstract Data Type (ADT)**: - a set of elements with a collection of well-defined operations. - The ADT is defined by what these have in common - their interface. - **Object-oriented languages** such as C++ and Java provide explicit support for expressing ADTs by means of classes. - **Examples of ADTs** include list, stack, queue, set, tree, graph, etc. # Data Structures - **Data Structures:** an implementation of an ADT is a translation into statements of a programming language. - **Each data structure** is built up from the basic data types of the underlying programming language using the available data structuring facilities, such as arrays, records (class in C++), pointers, files, sets, etc. - **Example**: - A "Queue" is an ADT which can be defined as a sequence of elements with operations such as null(Q), empty(Q), enqueue(x, Q), and dequeue(Q). This can be implemented using data structures such as: - array - singly linked list - doubly linked list - circular array # Abstract Data Type (ADT) - The ADT is defined by what these have in common - their interface. - **How would you choose between the implementations?** - Cost of implementing. - Chance of making errors. - Cost of use: One is fast for additions, other is fast for multiplications. - Accuracy. # Modularity - The best programs are modular. - The pieces can fit together and be used in many different ways. - Lego building blocks are a classic example of modularity. # Algorithmic Complexity - Not all computer programs are equal. - The efficiency of programs can be measured as: - The amount of time the program takes to run. - The amount of memory space used. # Standard Programming Tools - **Data Structures:** - Stacks - Queues - Lists - Tables - Trees - Graphs - **Algorithms:** - Searching - Sorting - Tree Traversal - Graph Algorithms # Terminology - **Abstract Data Type (ADT):** - Mathematical description of an object with set of operations on the object. Useful building block. - **Algorithm:** - A high-level, language-independent, description of a step-by-step process. - **Data Structure:** - A specific family of algorithms for implementing an abstract data type. - **Implementation of data structure:** - A specific implementation in a specific language. # Summary - **What is the "Data Structure"?** - Ways to represent data - **Why Data Structure ?** - To design and implement large-scale computer systems - Have proven correct algorithms - The art of programming - **Use the right tool for the right problem** and solving the problem becomes easier, and possibly faster and more efficient. - **This class is going to:** - Present you with some tools - Show you a way to select the right tools for problems you are given. - And how to show you made the right choice. - Or rather why one tool may be better than another. # Thank you - The document ends with an image of a "thank you" message in Arabic and English.