[Link].
(CSBS) Degree Programme Second Semester - 2020 - 2021
Category L T P Credit
20CB230 DATA STRUCTURES AND ALGORITHMS
PC 3 1 0 4
Preamble
This course provides an introduction to the basic concepts and techniques of Linear and
nonlinear data Structures and analyzes the various algorithms. It also discusses the use of
data structures and the algorithm design techniques to provide efficient software solutions.
Prerequisite
20CB130-Fundamentals of Computer Science
Course Outcomes
On the successful completion of the course students will be able to
CO Course Outcome Statement Weightage***
Number in %
CO1 Construct algorithms for performing operations on a data 20
structure, with an understanding of the trade-off between
the time and space complexity.
CO2 Demonstrate how linear data structures like array, stack, 20
queue and linked list are represented in the main memory
and manipulated or used by different operations.
CO3 Apply non-linear data structures like Binary Tree, Threaded 20
Binary Tree, Binary Search Tree, B & B+ Tree, AVL Tree,
Splay Tree and Graphs in different operations.
CO4 Identify the computational efficiency of searching algorithms. 10
CO5 Determine the computational efficiency of sorting and 15
hashing algorithms.
CO6 Illustrate the organization of files and its accessing schemes 15
***
CO Mapping with CDIO Curriculum Framework
CO TCE Learning Domain Level CDIO Curricular Components
# Proficiency Cognitive Affective Psychomotor (X.Y.Z)
Scale
CO1 TPS 3 Apply Value Mechanism 1.2, 2.1.5,2.2.3,2.5.1,3.2.3,
4.5.3
CO2 TPS 3 Apply Value Mechanism 1.2, 2.1.5,2.2.3,2.5.1,3.2.3,
4.5.3
CO3 TPS 3 Apply Value Mechanism 1.2, 2.1.5,2.2.3,2.5.1,3.2.3,
4.5.3
CO4 TPS 3 Apply Value Mechanism 1.2, 2.1.5,2.2.3,2.5.1,3.2.3,
4.5.3
CO5 TPS 3 Apply Value Mechanism 1.2, 2.1.5,2.2.3,2.5.1,3.2.3,
4.5.3
CO6 TPS 3 Apply Value Mechanism 1.2, 2.1.5,2.2.3,2.5.1,3.2.3,
4.5.3
Mapping with Programme Outcomes and Programme Specific Outcomes
Co PO PO PO PO PO PO PO PO PO PO PO PO PS PS PS
s 1 2 3 4 5 6 7 8 9 10 11 12 O1 O2 O3
CO S M L L - L - L L L M L L
1
Passed in Board of Studies Meeting on 06.07.2020 Approved in 60th Academic Council Meeting on 25.07.2020
[Link].(CSBS) Degree Programme Second Semester - 2020 - 2021
CO S M L L - L - L L L M L L
2
CO S M L L - L - L L L M L L
3
CO S M L L - L - L L L M L L
4
CO S M L L - L - L L L M L L
5
CO S M L L - L - L L L M L L
6
S- Strong; M-Medium; L-Low
Assessment Pattern: Cognitive Domain
Continuous Assignment
Cognitive Assessment Tests Terminal
Levels 1 2 3 1 2 3 Examinatio
n
Remember 10 10 10 - - - 10
Understand 30 30 10 - - - 10
Apply 60 60 80 100 100 100 80
Analyse
Evaluate
Create
Assessment Pattern: Psychomotor
Psychomotor Skill Miniproject /Assignment/Practical Component
Perception
Set
Guided Response
Mechanism 100
Complex Overt Responses
Adaptation
Origination
Sample Questions for Course Outcome Assessment**
** (2 to 3 at the cognitive level of course outcome)
Course Outcome 1(CO1):
1. There are three towers and sixty four disks of different diameters placed on the first
tower. The disks are in order of decreasing diameter as one scans up the tower. Monks
were reputedly supposed to move the disks from tower 1 to tower 3 obeying the rules: (i)
only one disk can be moved at any time; (ii) no disk can be placed on top of a disk with
smaller diameter. Write a recursive procedure which prints the sequence of moves which
accomplish this task.
2
2. ), where f(n) is defined to be the running time of the program A(n):
def A(n): a tuple = tuple(range(0, n)) # a tuple is an immutable version of a
# list, so we can hash it
S = set()
for i in range(0, n):
Passed in Board of Studies Meeting on 06.07.2020 Approved in 60th Academic Council Meeting on 25.07.2020
[Link].(CSBS) Degree Programme Second Semester - 2020 - 2021
for j in range(i+1, n):
[Link](atuple[i:j]) # add tuple (i,...,j-1) to set S.
Justify your answer.
3. Given an array A which stores 0 and 1, such that each entry containing 0 appears before
all those entries containing 1. In other words, it is like {0, 0, 0,..., 0, 0, 1, 1,..., 111}.
Design an algorithm to find out the small index i in the array A such that A[i] = 1 using c
log n instructions in the worst case for some positive constant c.
Course Outcome 2(CO2):
1. Two stacks are to be represented in an array V(1:m) .Write algorithms ADD(i.X) and
DELETE(i) to add X and delete an element from stack i, . Your algorithms
should be able to add elements to the stacks so long as there are fewer than m elements
in both stacks together.
2. Explain how to implement doubly linked lists using only one pointer value x:np per item
instead of the usual two (next and prev). Assume that all pointer values can be
interpreted as k-bit integers, and define x:np to be x:np D x:next XOR x:prev, the k-bit
-
describe what information you need to access the head of the list. Show how to
implement the SEARCH, INSERT, and DELETE operations on such a list. Also show
how to reverse such a list in O(1) time.
3. Write an algorithm to transform from prefix to postfix. Carefully state any assumptions
you make regarding the input. How much time and space does your algorithm take?
Course Outcome 3(CO3):
1. Write an algorithm which inserts a new node T as the left child of node S in a threaded
binary tree. The left pointer of S becomes the left pointer of T.
2. Show how the graph below would look if represented by its adjacency matrix, adjacency
lists,adjacency multilist.
3. Write algorithm to insert key values into AVL trees, B-trees of order 3, B*-trees of order
3 and B'-trees of order 3. Evaluate the relative performance of these four
representations of internal tables.
Course Outcome 4 (CO4):
1. Consider linear search - How many elements of the input sequence need to be checked
on the average, assuming that the element being searched for is equally likely to be any
element in the array? How about in the worst case? What are the average-case and
worst-case running times of linear search ? Justify your answers
2.
such that v = A[i] or the special value
sorted, we can perform a binary search: compare P with the midpoint of the array and
repeat the search on one half of array, eliminating the other half from further
consideration.
(a) Construct a pseudocode for binary search as a recursive procedure.
(b) Rewrite your binary search procedure in an iterative style.
3. Show that in an undirected graph, classifying an edge (u, v) as a tree edge or a back
edge according to whether (u, v)or (v, u) is encountered first during the depth-first search
is equivalent to classifying it according to the ordering of the four types in the
classification scheme.
Passed in Board of Studies Meeting on 06.07.2020 Approved in 60th Academic Council Meeting on 25.07.2020
[Link].(CSBS) Degree Programme Second Semester - 2020 - 2021
Course Outcome 5 (CO5):
1. Consider sorting n numbers stored in array A by first finding the smallest element of A
and exchanging it with the element in AOE1_. Then find the second smallest element of
A, and exchange it with AOE2_. Continue in this manner for the first n_1 elements of A.
Write pseudocode for this algorithm, which is known as selection sort. What loop
invariant does this algorithm maintain? Why does it need to run for only the first n _ 1
elements, rather than for all n elements? Give the best-case and worst-case running
-notation
2.
elements and is sorted in decreasing order.
3. Consider implementing a hash table for an application in which we will build an initial
hash table by inserting a substantial collection of records. After this, we expect that the
number of insertions and the number of deletions performed to be roughly the same,
although there may be long runs of consecutive insertions or consecutive deletions.
Furthermore, the table will use a probe strategy to resolve any collisions that occur
during insertion, and therefore we will "tombstone" cells from which a record has been
deleted. If we implement the hash table described above, then when we search for a
record, we cannot conclude the record is not in the table until we have found an empty
cell in the table, not just a tombstone. (We will ensurethat the table never reaches the
state that there are no empty cells.) Explain carefully why the search cannot stopwhen a
tombstone is encountered
Course Outcome 6(CO6):
1. Write an algorithm to process a tape file in the batched mode. Assume the master file is
ordered by increasing primary key value and that all such values are distinct. The
transaction file contains transactions labeled: update, delete and insert. Each such
transaction also contains the primary key value of the record to be updated, deleted or
inserted. A new updated master file is to be created. What is the complexity of your
algorithm?
2. Describe briefly how to do the following:
(i) In a multilist organization: (a) output all records with KEY1 = PROG and KEY2 = NY.
How many accesses are needed to carry this out? (b) Output all records with KEY1 =
PROG or KEY2 = NY. How many accesses are needed for this. Assume that each
access retrieves only one record.
(ii) If a ring organization is used instead, what complications are introduced into (a) and
(b) above?
3. A 105 record file is maintained as an inverted file on a disk with track capacity 5000
characters. This disk has 200 tracks on each of its 10 surfaces. Each record in the file is
50 characters long and has five key fields. Each key is binary (i.e., has only two distinct
values) and so the index for each key can be maintained as a binary bit string of length
105 bits. If 1 character is 6 bits long, then each index takes about 4 tracks. How should
the 5 indexes be stored on disk so as to minimize total seek time while processing the
indexes in order to determine which records satisfy a given boolean query Q? This
processing involves reading in 1 track of each index and testing the query against records
represented by this track. Then the next set of index tracks is input and so on. How much
time does it take to process all the indexes in order to determine which records are to be
retrieved? Assume a seek time of 1/10 sec and a latency time of 1/40 sec. Also assume
that only the input time is significant. If k records satisfy this query, how much more time
is needed to retrieve these k records? Using other file structures it may be necessary to
read in the whole file. What is the minimum time needed to read in the entire file of 105
records? How does this compare with the time needed to retrieve k records using an
inverted file structure?
Passed in Board of Studies Meeting on 06.07.2020 Approved in 60th Academic Council Meeting on 25.07.2020
[Link].(CSBS) Degree Programme Second Semester - 2020 - 2021
Concept Map
Syllabus
Basic Terminologies &Introduction to Algorithm and Data Organisation: Algorithm
specification, Recursion, Performance analysis, Asymptotic Notation - The Big-O, Omega and
Theta notation, Programming Style, Refinement of Coding - Time-Space Trade Off, Testing,
Data Abstraction
Linear Data Structure: Dynamic memory allocation,Array, Stack, Queue, Linked-list and its
types, Various Representations, Operations & Applications of Linear Data Structures
Non-linear Data Structure: Trees (Binary Tree, Threaded Binary Tree, Binary Search Tree,
B & B+ Tree, AVL Tree, Splay Tree) , Priority queue as heap, Graphs (Directed, Undirected),
Various Representations, Operations (search and traversal algorithms and complexity
analysis) & Applications of Non-Linear Data Structures
Searching and Sorting on Various Data Structures: Sequential Search, Binary Search,
Breadth First Search, Depth First Search, Insertion Sort, Selection Sort, Shell Sort, Divide
and Conquer Sort, Merge Sort, Quick Sort, Heap Sort, Introduction to Hashing
File: Organisation (Sequential, Direct, Indexed Sequential, Hashed) and various types of
accessing schemes.
Learning Resources
1. E. Horowitz and S. Sahni , Fundamentals of Data Structures , Computer Science
Press, 1977.
2. [Link], John [Link], Jeffrey [Link], Data Structures and
Algorithms,Pearson Education,2002.
3. Donald E. Knuth ,The Art of Computer Programming: Volume 1: Fundamental
Algorithms, Donald E. Knuth,3rd edition,Pearson Education.
4. Charles E. Leiserson, Thomas H. Cormen, Ronald L. Rivest, Clifford Stein,
Introduction to Algorithms, Third edition, PHI, 2010.
5. Pat Morin,Open Data Structures: An Introduction (Open Paths to Enriched Learning),
31st ed. Edition , AU Press,2013
Passed in Board of Studies Meeting on 06.07.2020 Approved in 60th Academic Council Meeting on 25.07.2020
[Link].(CSBS) Degree Programme Second Semester - 2020 - 2021
Course Contents and Lecture Schedule
Module Topic No. of Course
No. Hours Outcome
1. Basic Terminologies &Introduction to Algorithm
and Data Organisation
1.1 Algorithm specification, 1 CO1
1.2 Recursion 1 CO1
1.3 Performance analysis 1 CO1
1.4 Asymptotic Notation - The Big-O, Omega and Theta 1 CO1
notation
1.5 Programming Style 1 CO1
1.6 Refinement of Coding - Time-Space Trade Off 1 CO1
1.7 Testing 1 CO1
1.8 Data Abstraction 1 CO1
Tutorial 3
2 Linear Data Structure
2.1 Dynamic Memory allocation 1 CO2
2.2 Array 1 CO2
2.3 Stack 1 CO2
2.4 Queue 1 CO2
2.5 Linked-list and its types 1 CO2
2.6 Various Representations 1 CO2
2.7 Operations & Applications of Linear Data Structures 1 CO2
Tutorial 3
3 Non-linear Data Structure
3.1 Trees (Binary Tree, Threaded Binary Tree, Binary 2 CO3
Search Tree)
3.2 Trees (B & B+ Tree, AVL Tree, Splay Tree) 2 CO3
3.3 Priority Queue as Heap 1 CO3
3.4 Graphs (Directed, Undirected) 1 CO3
3.4 Various Representations 1 CO3
3.6 Operations (search and traversal algorithms and 1 CO3
complexity analysis)
3.7 Applications of Non-Linear Data Structures 1 CO3
Tutorial 3
4 Searching and Sorting on Various Data Structures
4.1 Sequential Search, Binary Search 1 CO4
4.2 Breadth First Search, Depth First Search 1 CO4
4.3 Insertion Sort 1 CO4
4.4 Selection Sort, Shell Sort 1 CO5
4.5 Divide and Conquer Sort, Merge Sort 1 CO5
4.6 Quick Sort, Heap Sort 1 CO5
4.7 Introduction to Hashing 1 CO5
Tutorial 3
5 File
5.1 Organisation(Sequential,Direct) 1 CO6
5.2 Organisation (Indexed Sequential, Hashed) 2 CO6
5.3 Various types of accessing schemes. 2 CO6
Total Hours 48
Course Designers:
1. [Link] mviji@[Link]
2. Raja Lavanya rlit@[Link]
Passed in Board of Studies Meeting on 06.07.2020 Approved in 60th Academic Council Meeting on 25.07.2020