Data Structure and Algorithms
(CoSc2083– 5ECTS)
Sem. I - 2021
Department of Computer Science
Institute of Technology
Ambo University
Outline
Course Description:
This course focuses on the study of data structures,
algorithms and program efficiency. Topics include:
analysis of time and space requirements of algorithms;
program efficiency improving techniques
abstract data types such as linked lists, stacks, queues, trees
(traversal, implementations)
simple searching algorithms (linear search, binary search,)
simple sorting algorithms (bubble sort, insertion sort, selection sort,)
advanced sorting algorithms (merge sort, quick sort, heap sortt)
…
Course Goals or Learning Outcome:
The course aims:
To introduce the most common data structures like stack, queue, linked list
To give alternate methods of data organization and representation
To enable students use the concepts related to Data Structures and
Algorithms to solve real world problems
To practice Recursion, Sorting, and searching on the different data
structures
To implement the data structures with a chosen programming language
Prerequisites:
Fundamentals of Programming II
…
Required Texts:
Text book:
E. Horowitz, S.Sahni and Dinesh Mehta. Fundamentals of data structures in
C++, W.H Freeman and Company (1995
Sanjay Pahuja, A practical approach to data structures and algorithms,
New age International publishers, 2008
Weiss, Mark. Data structures and algorithm analysis in C, Benjamin
Cummings Publishing (1997)
The Design and Analysis of Computer Algorithms. Aho, Hopcroft, and
Ullman
Summary of Teaching Learning Methods:
There will be Lecture, Demonstrations, Lab work Tutorials, Reading
assignments and Group Discussions.
Summary of Assessment Methods:
Quizzes 10,Assignments 15, Project 20,Tests 25,Final Exam 30
Chapter One: Introduction
Chapter 1: Introduction to Data Chapter 5: Stacks and Queues
Structures Basic Stack Operations
Introduction Basic Queue Operations
Abstract Data Type and Abstraction Implementation of Stacks and queues
Chapter 2 – Algorithm and Algorithm Chapter 6: Tree Structures
Analysis Binary Trees and Binary Search Trees
Properties of Algorithm Basic Tree Operations
Analysis of Algorithm Traversing in a Binary Tree
General Trees and Their Implementations
Chapter 3: Simple Sorting and Searching
Algorithms Chapter 7: Graphs
Sorting {Selection Sort, Bubble Sort, Insertion Sort, Introduction
Pointer Sort} Describing graphs
Searching{Linear/Sequential Searching, Binary
Directed Graphs
Searching}
Traversing a graph
Chapter 4: Linked Lists
Review on Pointer, Chapter 8: Advanced Sorting and Searching
Dynamic Memory allocation and De-allocation Sorting {Heap Sort, Quick Sort, Merge Sort, Shell
Singly & Doubly Linked Lists Sort}
Implementation of Linked Lists Advanced Searching
Hashing
Chapter One:
Introduction to Data
Structures
This Chapter Covers:
Introduction
Abstract Data Type and Abstraction
Introduction
What do programs do?
A program solves a problem
A solution to a problem consists of:
A way to organize the data (Data Structures)
Sequence of steps to solve the problem (Algorithms)
In other words:
Program = data structures + algorithms
Data Structures are used to model the world or some part of the world.. How?
The value held by a data structure represents some specific characteristic of the world
The characteristic being modeled restricts the possible values held by a data structure
The characteristic being modeled restricts the possible operations to be performed on the data
structure.
Do all characteristics need to be modeled?
No – it depends on the model
No – it depends on the reason for developing the model
Introduction
The first step to solve the problem is obtaining ones own abstract
view, or model, of the problem.
This process of modeling is called abstraction
The model defines an abstract view to the problem. The model should focus
on problem related stuff.
Abstraction
Abstraction is a process of classifying characteristics as relevant and irrelevant and
ignoring the irrelevant ones.
Applying abstraction correctly is the essence of successful programming
Example: Model of Student Ambo University
Relevant Non relevant
Char Name[15]; float height, weight;
Char ID[11[;
Char Department[20];
int Age, year;
Abstract Data Types
Using the model (previous Example), a programmer tries to
define the properties of the problem. These properties include
The data which are affected and The operations that are
involved in the problem
An entity with the properties just described is called an abstract data type (ADT).
Abstract Data Types Consists of data to be stored
and operations supported on them.
Abstract Data Types is a specification that describes
a data set and the operation on that data.
Abstract Data Types
The ADT specifies:
What data is stored.
What operations can be done on the data.
However, it does not specify how to store or how to implement the operation.
It is also independent of any programming language.
Example:
ADT employees of an organization:
This ADT stores employees with their relevant attributes
and discarding irrelevant attributes.
Relevant:- Name, ID, Sex, Age, Salary, Dept, Address
Non Relevant :- weight, color, height
This ADT supports hiring, firing, retiring, … operations
Data Structure
In Contrast a data structure is a language construct that the programmer
has defined in order to implement an abstract data type.
What is the purpose of data structures in programs?
Data structures are used to model a problem.
Attributes of each variable:
Example: Name: Textual label.
struct Student_Record Address: Location in memory.
{ Scope: Visibility in statements of a
char name[20]; program.
char ID_NO[10]; Type: Set of values that can be stored + set
char Department[10]; of operations that can be performed.
int age; Size: The amount of storage required to
}; represent the variable.
Life time: The time interval during execution
of a program while the variable exists.
Data Structure
A data structure is a way of storing data in a computer so that it
can be used efficiently.
It is the specification of the elements of the structure, the
relationships between them, and the operation that may be
performed upon them.
It can be said that the study of data structures involves the
storage, retrieval and manipulation of information.
In other words, the possible logical and physical arrangement of
data items to provide an efficient solution for a problem is called
Data Structure.
The various operations that can be performed over Data
Structures are :Create ,Destroy ,Access ,Update
Chapter 2 :
Algorithm and Algorithm
Analysis
This Chapter Covers:
Properties of Algorithm
Analysis of Algorithm
