Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Syllabus

 


SEMESTERS 3

DATA STRUCTURES AND ALGORITHMS
(Common to CS/CA/CM/CD/CR/AI/AM/AD/CB/CN/CC/CU/CI/CG)

 

Course Code

PCCST303

CIE Marks

40

Teaching Hours/Week (L: T:P: R)

 

3:1:0:0

ESE Marks

60

Credits

4

Exam Hours

2Hrs.30Min.

Prerequisites(if any)

UCEST105

Course Type

Theory


Course Objectives:


1. To provide the learner a comprehensive understanding of data structures and algorithms.
2. To prepare them for advanced studies or professional work in computer science and related fields.

SYLLABUS

 

Module No.

Syllabus Description

Contact Hours

 

  

1

Basic Concepts of Data Structures

Definitions; Data Abstraction; Performance Analysis - Time& Space Complexity, Asymptotic Notations; Polynomial representation using Arrays, Sparse matrix (Tuple representation); Stacks and Queues - Stacks, Multi-Stacks, Queues, Circular Queues, Double Ended Queues; Evaluation of Expressions-Infix to Postfix, Evaluating Postfix Expressions.

 

 

11

 

 

2

Linked List and Memory Management

Singly Linked List - Operations on Linked List, Stacks and Queues using Linked List, Polynomial representation using Linked List; Doubly Linked List; Circular Linked List; Memory allocation - First-fit, Best-fit, and Worst-fit allocation schemes; Garbage collection and compaction.

 

 

11

 

 

 

3

Trees and  Graphs

Trees :- Representation Of Trees; Binary Trees - Types and Properties, Binary Tree Representation, Tree Operations, Tree Traversals; Expression Trees; Binary Search Trees-Binary Search Tree Operations; Binary Heaps

-Binary Heap Operations, Priority Queue.

Graphs:-Definitions; Representation of Graphs; Depth First Search and

 

 

 

11

 

Breadth First Search;Applications of Graphs -Single Source All

Destination.

 

 

 

4

Sorting and Searching

Sorting Techniques: - Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Radix Sort.

Searching Techniques :- Linear Search, Binary Search, Hashing - Hashing functions : Mid square, Division, Folding, Digit Analysis; Collision Resolution: Linear probing, Quadratic Probing, Double hashing, Open hashing.

 

  

11

 

 Course Assessment Method(CIE: 40 marks, ESE: 60 marks)

 

Continuous Internal Evaluation Marks(CIE):

 

 

Attendance

 

Assignment/ Microproject

Internal Examination-1 (Written)

Internal Examination-2 (Written)

 

Total

5

15

10

10

40

 

End Semester Examination Marks(ESE)

In PartA, all questions need to be answered and in PartB, each student can choose anyone full question out of two questions

 

Part A

Part B

Total

•     2 Questions from each module.

•     Total of 8 Questions,each carrying 3 marks

 

(8x3=24marks)

•     Each question carries 9 marks.

•     Two questions will be given from each module, out of which 1 question should be answered.

•     Each question can have a maximum of 3sub divisions.

(4x9=36 marks)

 

 

 

 

60

Course Outcomes(COs)

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

 

 

Course Outcome

Bloom’s Knowledge Level(KL)

CO1

 Identify appropriate data structures for solving real world problems.

K3

CO2

 Describe and implement linear data structures such as arrays, linked lists,stacks,and queues.

K3

CO3

 Describe and Implement non linear data structures such as trees and graphs.

K3

CO4
Select appropriate searching and sorting algorithms to be used in Specific circumstances.

K3

Note:K1-Remember,K2-Understand,K3-Apply,K4-Analyse,K5-Evaluate,K6-Create

  CO-PO Mapping Table(Mapping of Course Outcomes to Program Outcomes)

 

 

PO1

PO2

PO3

PO4

PO5

PO6

PO7

PO8

PO9

PO10

PO11

PO12

CO1

3

3

3

 

 

 

 

 

 

 

 

3

CO2

3

3

3

 

 

 

 

 

 

 

 

3

CO3

3

3

3

 

 

 

 

 

 

 

 

3

CO4

3

3

3

 

 

 

 

 

 

 

 

3

Note:1:Slight(Low),2:Moderate(Medium),3:Substantial(High),-:NoCorrelation

  

Text Books

Sl.No

Title of the Book

Name of the Author/s

Name of the Publisher

Edition and Year

 

1

 

Fundamentals of DataStructures in C

Ellis Horowitz,Sartaj Sahni and Susan Anderson-Freed,

Universities press,

 

2/e,2007

 

2

 

Introduction to Algorithms

Thomas H Cormen,Charles Leisesrson, Ronald L Rivest, Clifford Stein

 

PHI

 

3/e,2009

Reference Books

Sl.No

Title of the Book

Name of the Author/s

Name of the

Publisher

Edition

And Year

1

Classic Data Structures

Samanta D.

Prentice Hall India.

2/e,2018

 

2

 

Data Structures and Algorithms

Aho A.V.,J.E.

Hopcroft and J.D. Ullman

Pearson Publication.

 

1/e,2003

3

Introduction to Data Structures with

Applications

TremblayJ.P.and P.G.

Sorenson

Tata McGraw

Hill.

2/e,2017

4

Theory and Problems of Data Structures

Lipschuts S.

Schaum’sSeries

2/e,2014

  

Video Links(NPTEL, SWAYAM…)

Module

No.

Link ID

1

https://nptel.ac.in/courses/106102064

2

https://ocw.mit.edu/courses/6-851-advanced-data-structures-spring-2012/

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more