B.Sc (Computer Science) Syllabus 2015 North Eastern Hill University
CS101T and CS101P: Data Structures using C
Objective:
The objective of the course is to introduce the fundamentals of C programming language and develop the
skills for solving problems using computers. After completion of this course, a student will be able to
Understand and use the process of abstraction using a programming language such as „C‟
Analyse step by step and develop a program to solve real world problems
Understand File handling in C and the basics of Graphics programming.
Understanding and implementing Linear and Nonlinear data structures: Arrays, lists, stacks, queues,
trees and graphs
Implementation of various sorting and searching methods and their complexity analysis.
Outline of the Course
Minimum Class Hours Exam time (Hours) Marks
Theory Practical
Theory Practical Total Theory Practical Total
External Internal External Internal
60 40 100 2 3 37.5 12.5 37.5 12.5 100
Marks
Minimum Class Hours
Unit Topic (Theory)
Theory Practical Total
C fundamentals, I/O functions, Control
I statements, Functions, Arrays and Pointers, 15 10 25 9.5
Structure and Union
Linear Data Structures: Linked List, Stacks
II 10 10 20 6.5
and Queues
III Trees 15 7 22 8.5
IV Graphs 10 8 18 6.5
Searching and Sorting, and their complexity
V 10 5 15 6.5
analysis
Total 60 40 100 37.5
Detailed Syllabus
Unit I: C Fundamentals, I/O functions, Control statements, Functions, Arrays and
Pointers, Structure and Union 15 Hours
C Fundamentals: Algorithms, Flow charts, Development of algorithms, The C character set, identifiers
and keywords, Data types, constants, variables and arrays, declarations, symbolic constants, Operators
(Arithmetic, unary, relational, logical, bitwise, assignment),
I/O functions: Header files (stdio.h, conio.h) getch(), getche(), getchar(), putch(), putchar(), scanf(),
printf(), gets(), puts(), clrscr(), window().
Control statements: Decision making and branching (if..else, switch), Decision making and looping
(while, do .. while, for), Jumping (break, continue, goto), Nested loops.
Page of 4/ 474
, B.Sc (Computer Science) Syllabus 2015 North Eastern Hill University
Functions: Overview (definition, declaration), defining and accessing a function, function prototypes,
call by value, call by reference, recursion, Advantages and disadvantages of recursion over iteration,
Storage classes (Automatic, Register, External, Static), String functions , Math functions , Memory
allocation functions,
Arrays and Pointers: Defining an array, array initialization, processing an array, passing array to a
function, multidimensional arrays, arrays and strings, pointer declarations, passing pointer to a function,
pointer and one dimensional arrays, Operation on pointers.
Structures and Unions: Defining a structure, processing a structure, user defined data types, structures
and arrays, structures and pointers, passing structures to a function, self-referential structures, Union,
Union of structures, Enumerated, typedef.
Unit II: Linear Data Structures: Linked List, Stacks and Queues 10 Hours
Data Type, Abstract Data Type, Data Structure, Complexity measures in terms of time and space; Big O
notation. Linked List as a data structure (characteristics, advantages, disadvantages); operations on lists
(creation, insertion, deletion, traversal, merging, splitting); singly linked list, doubly linked list, circular
list; use of linked lists for polynomial representation and manipulation (addition and multiplication).
Stacks and Queues as data structures; implementation of stacks and queues using arrays and linked lists;
Definitions of Circular Queue, Priority Queue, D-Queue; Application of stacks : Conversion of
infix(containing arithmetic operators including exponential operator, and parenthesis) to postfix,
evaluation of postfix expression.
Unit III: Trees 15 Hours
Definition of tree as a data structure (Binary Trees and General Trees), Basic Terms (father, son,
descendant, ancestor, height, depth, leaf, node, forest, ordered trees, strictly binary tree, complete binary
tree, internal nodes, external nodes); Representation of trees using linked lists, Binary tree traversal
methods (pre-order, in-order, post-order), recursive algorithms for traversal methods, Binary search trees
(creation, insertion and deletion of a node), Height balanced (AVL) binary trees (construct and traverse an
AVL tree), Definitions and characteristics of threaded binary trees, multi-way search trees and B-tree.
Unit IV: Graphs
Definition of a graph, Basic Terms, Graph representation: Adjacency matrix, adjacency lists, incidence
matrix, adjacency multi-lists; Traversal schemes: Depth first search, Breadth first search (Recursive and
non-recursive algorithms); Shortest Path algorithms (Dijkstra‟s), Spanning tree, Minimal spanning tree
algorithms (Kruskal‟s algorithm)
Unit V: Searching and Sorting, and their complexity analysis 10 Hours
Linear and binary search and their complexity analysis; Hashing, Hash Functions (division method, mid
square method, folding), Analysis of ideal hash function; Conflict resolution (linear and quadratic probe,
double hashing, separate chaining, coalesced chaining); Analysis of collision resolution techniques;
Sorting algorithms(Insertion, Selection, Bubble, Quick) and comparison of their time complexity.
Instructions For Paper Setter
The question papers will be set according to the following scheme
Cont’d …
Page of 5/ 475
CS101T and CS101P: Data Structures using C
Objective:
The objective of the course is to introduce the fundamentals of C programming language and develop the
skills for solving problems using computers. After completion of this course, a student will be able to
Understand and use the process of abstraction using a programming language such as „C‟
Analyse step by step and develop a program to solve real world problems
Understand File handling in C and the basics of Graphics programming.
Understanding and implementing Linear and Nonlinear data structures: Arrays, lists, stacks, queues,
trees and graphs
Implementation of various sorting and searching methods and their complexity analysis.
Outline of the Course
Minimum Class Hours Exam time (Hours) Marks
Theory Practical
Theory Practical Total Theory Practical Total
External Internal External Internal
60 40 100 2 3 37.5 12.5 37.5 12.5 100
Marks
Minimum Class Hours
Unit Topic (Theory)
Theory Practical Total
C fundamentals, I/O functions, Control
I statements, Functions, Arrays and Pointers, 15 10 25 9.5
Structure and Union
Linear Data Structures: Linked List, Stacks
II 10 10 20 6.5
and Queues
III Trees 15 7 22 8.5
IV Graphs 10 8 18 6.5
Searching and Sorting, and their complexity
V 10 5 15 6.5
analysis
Total 60 40 100 37.5
Detailed Syllabus
Unit I: C Fundamentals, I/O functions, Control statements, Functions, Arrays and
Pointers, Structure and Union 15 Hours
C Fundamentals: Algorithms, Flow charts, Development of algorithms, The C character set, identifiers
and keywords, Data types, constants, variables and arrays, declarations, symbolic constants, Operators
(Arithmetic, unary, relational, logical, bitwise, assignment),
I/O functions: Header files (stdio.h, conio.h) getch(), getche(), getchar(), putch(), putchar(), scanf(),
printf(), gets(), puts(), clrscr(), window().
Control statements: Decision making and branching (if..else, switch), Decision making and looping
(while, do .. while, for), Jumping (break, continue, goto), Nested loops.
Page of 4/ 474
, B.Sc (Computer Science) Syllabus 2015 North Eastern Hill University
Functions: Overview (definition, declaration), defining and accessing a function, function prototypes,
call by value, call by reference, recursion, Advantages and disadvantages of recursion over iteration,
Storage classes (Automatic, Register, External, Static), String functions , Math functions , Memory
allocation functions,
Arrays and Pointers: Defining an array, array initialization, processing an array, passing array to a
function, multidimensional arrays, arrays and strings, pointer declarations, passing pointer to a function,
pointer and one dimensional arrays, Operation on pointers.
Structures and Unions: Defining a structure, processing a structure, user defined data types, structures
and arrays, structures and pointers, passing structures to a function, self-referential structures, Union,
Union of structures, Enumerated, typedef.
Unit II: Linear Data Structures: Linked List, Stacks and Queues 10 Hours
Data Type, Abstract Data Type, Data Structure, Complexity measures in terms of time and space; Big O
notation. Linked List as a data structure (characteristics, advantages, disadvantages); operations on lists
(creation, insertion, deletion, traversal, merging, splitting); singly linked list, doubly linked list, circular
list; use of linked lists for polynomial representation and manipulation (addition and multiplication).
Stacks and Queues as data structures; implementation of stacks and queues using arrays and linked lists;
Definitions of Circular Queue, Priority Queue, D-Queue; Application of stacks : Conversion of
infix(containing arithmetic operators including exponential operator, and parenthesis) to postfix,
evaluation of postfix expression.
Unit III: Trees 15 Hours
Definition of tree as a data structure (Binary Trees and General Trees), Basic Terms (father, son,
descendant, ancestor, height, depth, leaf, node, forest, ordered trees, strictly binary tree, complete binary
tree, internal nodes, external nodes); Representation of trees using linked lists, Binary tree traversal
methods (pre-order, in-order, post-order), recursive algorithms for traversal methods, Binary search trees
(creation, insertion and deletion of a node), Height balanced (AVL) binary trees (construct and traverse an
AVL tree), Definitions and characteristics of threaded binary trees, multi-way search trees and B-tree.
Unit IV: Graphs
Definition of a graph, Basic Terms, Graph representation: Adjacency matrix, adjacency lists, incidence
matrix, adjacency multi-lists; Traversal schemes: Depth first search, Breadth first search (Recursive and
non-recursive algorithms); Shortest Path algorithms (Dijkstra‟s), Spanning tree, Minimal spanning tree
algorithms (Kruskal‟s algorithm)
Unit V: Searching and Sorting, and their complexity analysis 10 Hours
Linear and binary search and their complexity analysis; Hashing, Hash Functions (division method, mid
square method, folding), Analysis of ideal hash function; Conflict resolution (linear and quadratic probe,
double hashing, separate chaining, coalesced chaining); Analysis of collision resolution techniques;
Sorting algorithms(Insertion, Selection, Bubble, Quick) and comparison of their time complexity.
Instructions For Paper Setter
The question papers will be set according to the following scheme
Cont’d …
Page of 5/ 475
