BALIWAG POLYTECHNIC COLLEGE

Dalubhasaan Kong Mahal

2nd Semester
A.Y. 2020 – 2021

CC 104
DATA
STRUCTURES AND
ALGORITHMS

1|Page
 BALIWAG POLYTECHNIC COLLEGE
Dalubhasaan Kong Mahal
nd
2 Semester, A.Y. 2020 - 2021

STUDY GUIDES
For you to successfully finish this module, the possibility is within your reach. This
module is created in order for you to learn additional knowledges and skills independently.
With the help of this module, you will be prepared to become a responsible student whilst
aiming your goals. This is just a step to a long way of becoming successful and professional
on your chosen field. Keep your eye on the target and always stay focused and motivated to
achieve your desires. Follow these guidelines to help you be on track of this module.

1. Manage your time efficiently, schedule your task and be on strict compliance with
your schedule.
2. If you can’t seem to understand a specific topic, re-read the module again or seek
the help of your family members. If none of this works out, send me a message so I
can be of assistance.
3. Understand and comprehend the task being asked before you proceed on answering
them. Always remember that in order to be successful in any line, one must not aim
for a good, but rather aim for the best.
4. Think twice and go over again with your outputs before you come up with your final
answer. Follow the instructions and make sure that your answer is understandable
by your instructor.
5. Communication is the key for better understanding. Remember that I am always
willing to help and assist, just be sure to seek my attention if needed.
6. Your outputs are highly expected throughout this module.
7. Being the student, you are expected to excel and study this module on your own
way. A little help from the others is okay, but keep in mind that answers should be
done by you.

2|Page
GRADING SYSTEM
Self-paced Activities and Quizzes - 60%

Examination - 40%

COURSE DESCRIPTION
The course focuses on basic and essential topics in data structures, including array-based
lists, linked lists, skip lists, hash tables, recursion, binary trees, scapegoat trees, red–black
trees, heaps, sorting algorithms, graphs, and binary tree.

Study of advanced programming topics focused on logical structures of data as well as the
design, implementation and analysis of algorithms operating on these structures. Topics
include linked lists, stacks, trees, queues, graphs and analysis of efficiency. Also covers
searching, sorting and hashing techniques.

3|Page
STUDY SCHEDULE

DATE MODULE / TOPICS

Module 1: Data Structure and Algorithm
WEEK 1 Lesson 1: Orientation
August 3 – 7, 2020 Lesson 2: Introduction
Lesson 3: Environment Setup
Module 2: Algorithm
WEEK 2 Lesson 1: Algorithm Basics
August 10 – 14, 2020 Lesson 2: Asymptotic Analysis
Lesson 3: Divide and Conquer
Lesson 4: Dynamic Programming
Module 3: Data Structures
WEEK 3 Lesson 1: Data Structure Basics
August 17 – 28, 2020
Lesson 2: Array Data Structure
WEEK 4
PRELIM EXAMINATION
August 31 – September 4, 2020
Module 4: Linked List
WEEK 5 Lesson 1: Linked List
September 7 – 18, 2020 Lesson 2: Doubly Linked List
Lesson 3: Circular Linked List
-
Module 5: Stack and Queue
WEEK 6 Lesson 1: Stack
September 21 – 25, 2020 Lesson 2: Queue

Module 6: Searching Techniques

WEEK 7 Lesson 1: Linear Search
September 28 – October 2, 2020 Lesson 2: Binary Search
Lesson 3: Hash Table

WEEK 8
MIDTERM EXAMINATION
August 31 – September 4, 2020
-
Module 7: Sorting Techniques
WEEK 9 Lesson 1: Sorting Algorithms
September 21 – 25, 2020 Lesson 2: Bubble Sort
Lesson 3: Insertion Sort
Lesson 4: Selection Sort

Module 8: Graph Data Structure

WEEK 10 Lesson 1: Graph Data Structure
September 21 – 25, 2020 Lesson 2: Depth First Traversal
Lesson 3: Breadth First Traversal

4|Page
 Module 9: Tree Data Structure
WEEK 11 Lesson 1: Binary Search Tree
September 21 – 25, 2020 Lesson 2: Spanning Tree
Lesson 3: Heap

WEEK 4
FINALS EXAMINATION
August 31 – September 4, 2020

5|Page
 MODULE 1

Data Structure and Algorithm

What will you learn from this module?

Data Structures are the programmatic way of storing data so that data can be used
efficiently. Almost every enterprise application uses various types of data structures in one
or the other way. This tutorial will give you a great understanding on Data Structures
needed to understand the complexity of enterprise level applications and need of
algorithms, and data structures.

This module has three lessons:

1. Orientation of the Course

2. Introduction
3. Environment Setup

6|Page
LESSON 1

ORIENTATION OF THE COURSE

Why learn Data Structure and Algorithms?

As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.
 Data Search − Consider an inventory of 1 million (10 6) items of a store. If the application is
to search an item, it has to search an item in 1 million (10 6) items every time slowing down
the search. As data grows, search will become slower.
 Processor speed − Processor speed although being very high, falls limited if the data grows
to billion records.
 Multiple requests − As thousands of users can search data simultaneously on a web server,
even the fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue. Data can be organized in a
data structure in such a way that all items may not be required to be searched, and the required
data can be searched almost instantly.

Applications of Data Structure and Algorithms

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a

certain order to get the desired output. Algorithms are generally created independent of underlying
languages, i.e. an algorithm can be implemented in more than one programming language.
From the data structure point of view, following are some important categories of algorithms −
 Search − Algorithm to search an item in a data structure.
 Sort − Algorithm to sort items in a certain order.
 Insert − Algorithm to insert item in a data structure.
 Update − Algorithm to update an existing item in a data structure.
 Delete − Algorithm to delete an existing item from a data structure.

The following computer problems can be solved using Data Structures −

 Fibonacci number series

 Knapsack problem
 Tower of Hanoi
 All pair shortest path by Floyd-Warshall
 Shortest path by Dijkstra
 Project scheduling

7|Page
LESSON 2

INTRODUCTION
Data Structure is a systematic way to organize data in order to use it efficiently. Following terms are
the foundation terms of a data structure.
 Interface − Each data structure has an interface. Interface represents the set of operations
that a data structure supports. An interface only provides the list of supported operations,
type of parameters they can accept and return type of these operations.
 Implementation − Implementation provides the internal representation of a data structure.
Implementation also provides the definition of the algorithms used in the operations of the
data structure.

Characteristics of a Data Structure

 Correctness − Data structure implementation should implement its interface correctly.

 Time Complexity − Running time or the execution time of operations of data structure must
be as small as possible.
 Space Complexity − Memory usage of a data structure operation should be as little as
possible.

Need for Data Structure

As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.
 Data Search − Consider an inventory of 1 million (10 6) items of a store. If the application is
to search an item, it has to search an item in 1 million (10 6) items every time slowing down
the search. As data grows, search will become slower.
 Processor speed − Processor speed although being very high, falls limited if the data grows
to billion records.
 Multiple requests − As thousands of users can search data simultaneously on a web server,
even the fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue. Data can be organized in
a data structure in such a way that all items may not be required to be searched, and the required
data can be searched almost instantly.

Execution Time Cases

8|Page
There are three cases which are usually used to compare various data structure's execution time in
a relative manner.
 Worst Case − This is the scenario where a particular data structure operation takes
maximum time it can take. If an operation's worst case time is ƒ(n) then this operation will
not take more than ƒ(n) time where ƒ(n) represents function of n.
 Average Case − This is the scenario depicting the average execution time of an operation of
a data structure. If an operation takes ƒ(n) time in execution, then m operations will take
mƒ(n) time.
 Best Case − This is the scenario depicting the least possible execution time of an operation
of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation
may take time as the random number which would be maximum as ƒ(n).

Basic Terminology

 Data − Data are values or set of values.

 Data Item − Data item refers to single unit of values.
 Group Items − Data items that are divided into sub items are called as Group Items.
 Elementary Items − Data items that cannot be divided are called as Elementary Items.
 Attribute and Entity − An entity is that which contains certain attributes or properties,
which may be assigned values.
 Entity Set − Entities of similar attributes form an entity set.
 Field − Field is a single elementary unit of information representing an attribute of an entity.
 Record − Record is a collection of field values of a given entity.
 File − File is a collection of records of the entities in a given entity set.

LESSON 3

ENVIRONMENT SETUP
If you are still willing to set up your environment for C programming language, you need the
following two tools available on your computer, (a) Text Editor and (b) The C Compiler.

9|Page
Text Editor
This will be used to type your program. Examples of few editors include Windows Notepad, OS Edit
command, Brief, Epsilon, EMACS, and vim or vi.
The name and the version of the text editor can vary on different operating systems. For example,
Notepad will be used on Windows, and vim or vi can be used on Windows as well as Linux or UNIX.
The files you create with your editor are called source files and contain program source code. The
source files for C programs are typically named with the extension ".c".
Before starting your programming, make sure you have one text editor in place and you have
enough experience to write a computer program, save it in a file, compile it, and finally execute it.

The C Compiler
The source code written in the source file is the human readable source for your program. It needs
to be "compiled", to turn into machine language so that your CPU can actually execute the program
as per the given instructions.
This C programming language compiler will be used to compile your source code into a final
executable program. We assume you have the basic knowledge about a programming language
compiler.
Most frequently used and free available compiler is GNU C/C++ compiler. Otherwise, you can have
compilers either from HP or Solaris if you have respective Operating Systems (OS).
The following section guides you on how to install GNU C/C++ compiler on various OS. We are
mentioning C/C++ together because GNU GCC compiler works for both C and C++ programming
languages.

10 | P a g e