BCs: 2020-21, [Link]. Computer Science Semester IV. (Total credits=22) Course | Paper | Paper title Credits) Evaluation type Code CA_| UE | TOTAL (SIM [Pata Structures and 2? | 15) 35 50 [Algorithms ~ I cox! [S242 Komputer Networks 1 z [15 | 35 50 (5243. [Practical course on S241] 2 | 15 | 35 50 land cs 242 [Mathematics -1 ECE 50 [Mathematics 2 [15 | 35 50 cox Practical course in 2 | a5) 35 50 [Mathematics Electronics -1 7 | 3 50 Electronics z [15 | 35 50 ccxit Practical course in 2 | a5) 35 50 Electronics ECC Environment Science ~ ECCI [Language Communication ~I ‘+ Bach theory Lecture time for S.Y. [Link] Computer Science is of 50 min (3 lectures! week for 2 credit course) ‘© Each practical session time for $.Y. [Link] Computer Science is of 4 hrs 20 minutes (260 min) Practical batch size =12 ‘Savieribai Phule Pune University Page 3CBCS: 2020-21 [Link]. ‘Computer Science ‘Savitribai Phule Pune University [Link]. (Computer Science) Computer Science Paper - I Course Code: CS 241 Title : DATA STRUCTURES AND ALGORITHMS-II Teaching Scheme No. of Credits Examination Scheme 3 Lectures / week (50 mins. 0 IE: 15 marks duration) UE: 35 marks Prerequisites ‘+ Knowledge of € Programming Language ‘© Basic knowledge of algorithms + Basic knowledge of linear data structures Course Objectives: + To leam the systematic way of solving problems ‘+ To design algorithms ‘+ To understand the different methods of organizing large amount of data + To efficiently implement the non-linear data structures Course Outcomes: On completion of this course students will be able to ‘Implementation of different data structures efficiently ‘+ Usage of well-organized data structures to handle large amount of data ‘+ Usage of appropriate data structures for problem solving Course Contents Chapter! | Tree 10 lectures T1 Concept and Terminologies 1.2 Types of Binary trees - Binary tree, skewed tree, strictly binary tree, full binary tree, complete binary trée, expression tree, binary search tree, Heap 1.3 Representation ~ Static and Dynamic 1.4 Implementation and Operations on Binary Search Tree - Create, Insert, Delete, Search, Tree traversals- preorder, inorder, postorder ( recursive implementation), Level-order traversal using queue, Counting leaf, non-leaf and total nodes, Copy, Mirror. LS Applications of trees 1.5.1 Heap sort, implementation 1.5.2 Introduction to Greedy strategy, Huffman encoding (implementation using priority queue) Chapter? | Efficient Search Trees Tiectures | 2.1 Terminology: Balanced trees - AVL Trees, Red Black tree, splay tree, Lexical search tree -Trie 2.2 AVL Tree- concept and rotations 2.3 Red Black trees - concept, insertion and deletion 2.4 Multi-way search tree - B and B+ tree - Insertion, Deletion Chapter3__| Graph 12 lectures 3.1 Concept and terminologies 3.2 Graph Representation ~Adjacency matrix, Adjaceney list, Inverse Adjacency list, Adjaceney multilist 3.3 Graph Traversals — Breadth First Search and Depth First Search (with implementation) 3.4 Applications of graph Savieribai Phule Pune University Page 11CBCS: 2020-21 [Link]. ‘Computer Science 3.4.1 Topological sorting 3.4.2 Use of Greedy Strategy in Minimal Spanning Trees (Prims and Kruskals algorithm) 3.4.3 Single source shortest path - Dijkstra’s algorithm 3.4.4 Dynamic programming strategy, All pairs shortest path - Floyd Warshall algorithm 3.4.5 Use of graphs in social networks Chapter4 | Hash Table G lectures 4.1 Concept of hashing 4.2 Terminologies — Hash table,Hash function, Bucket, Hash address, collision, synonym, overflow ete. 4.3 Properties of good hash function 4.4 Hash functions : division function, MID square , folding methods 4.5 Collision resolution techniques 4.5.1 Open Addressing - Linear probing, quadratic probing, rehashing 4.5.2 Chaining - Coalesced , separate chaining Reference Books: 1. Fundamentals of Data Structures in C- Ellis Horowitz, SartajSahni,Susan Anderson-Freed, 2 Edition, Universities Press. 2. Data Structures using C and C+-+-YedidyahLangsam, Moshe J. Augenstein, Aaron M. Tenenbaum, Pearson Education 3. Data Structures: A Pseudo code approach with C, Richard Gilberg Behrouz. A. Forouzan, Cengage Learning. 4, Introduction to Data Structures in C-Ashok Kamthane, Pearson Education, 5. Algorithms and Data Structures, Niklaus Wirth, Pearson Education 6. Introduction to Algorithms—Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein--MIT Press 7. Fundamentals of Computer Algorithms-- Ellis Horowitz, SartajSahni, SanguthevarRajasekaran, Universities Press c Algorithm Design Manual - Steven S Skiena, Springer Savieribai Phule Pune University Page 12CBCS: 2020-21 [Link]. ‘Computer Science Savitribai Phule Pune University [Link]. (Computer Science) Computer Science Paper - I Semester II Course Code: CS 242. Title : Computer Networks-I Teaching Scheme No. of Credits Examination Scheme 3 lectures / week (50 mins, 0 IE: 15 marks duration) UE: 35 marks Prerequisites Principles of Digital Electronics Communication Principles Course Objectives To prepare students with basic networking concepts: data communication, protocolsand standards, various topologies and applications of network. ‘Course Outcomes 1. Have a good understanding of the OSI and TCP/IP Reference Models and in particular have a good knowledge of Layers. 2. Understand the working of various protocols. 3. Analyze the requirements for a given organizational structure and select the most appropriate networking architecture and technologies Course Contents Chapter I Introduction to Networks and Network Models lectures: T1 Data communication, components, data representation 1.2 Networks, network criteria, network types - LAN, WAN, Switching, The Internet, Accessing the Intemet 1.3 Network Software- Protocol hierarchies, Design Issues of the layer, Connection Oriented and Connectionless Servic 1.4 Reference models - OSI Reference Models, TCP/IP Reference model, Connection devices in different layers, Comparison of OSI and TCPAP Reference Models. Chapter 2__| Lower Layers 10 lectures 2.1 Communication at the physical layer, data rate limits - Noiseless channel (Nyquist bit rate), noisy channel (Shannon capacity), Performance - bandwidth, throughput, latency, bandwidth-delay produet, jitter 2.2 Design issues of Data Link Layer, Services - Framing, flow control, error control, congestion control, Link layer addressing 2.3 Framing Methods - Character Count, Flag bytes with Byte Stuffing, Flags bits with Bit Stuffing, Physical Layer Coding Violations 2.4 The Channel allocation problem, Static and dynamic allocation, Media Access Methods - Taxonomy of multiple-access protocols 2.5 Switching and TCP/IP layers, Types - circuit switching, packet switching and message switching 2.6 Wired LANs - Standard Ethemet characteristics, Addressing, Access method, implementation, Fast and Gigabit Ethernet 2.7 Wireless LANs - Architectural comparison, Characteristics, Access control, IEEE 802.11 Savieribai Phule Pune University Page 13CBCS: 2020-21 [Link]. ‘Computer Science architecture, Physical layer, MAC sublayer, Bluctooth architecture, Layers Chapter 3_| Network Layer 12 lectures 3.1 Network layer serviees - Packetizing, Routing and forwarding, other services, 3.2 Open and closed loop congestion control 3.3 IPv4 addressing- Address space, classful addressing, Subnetting, Supemetting, classless addressing, Network address resolution (NAT) 3.4 Forwarding of IP packets- based on destination address, based on label 3.5 Network Layer Protocols- Intemet Protocol (IP), IPv4 datagram format, Fragmentation, options 3.6 Mobile IP-addressing, agents, Three phases 3.7 Next Generation IP- IPV6 address representation, address space, address types, IPV6 protocol, packet format, extension header, Difference between IPv4 and IPv6 3.8 Routing - General idea, Algorithms - Distance vector routing, link state routing, path- vector routing, Chapter 4 | Transport Layer 10 Lectures 4.1 Transport layer Services- Process-to-process communication, Addressing, Encapsulation and decapsulation, Multiplexing and demultiplexing, Flow control, Pushing or pulling, Flow control, Buffers, Sequence numbers, Acknowledgements, sliding window, congestion control 4.2 Connectionless and Connection-oriented service, Port numbers 43 Transport layer protocols- User datagram protocol, user datagram, UDP service 4.4 Transmission Control Protocol - TCP Services, TCP Features, TCP Segment format, ‘three-way handshake for connection establishment and termination, State transition diagram, windows in TCP. Reference Books: 1. Computer Networks-Andrew S. Tanenbaum, 5" Edition, Pearson Education 2. Data Communication and Networking- BchrouzFourouzan, 5" Edition, McGraw Hill Pvt. Ltd, Savieribai Phule Pune University Page 14CBCS: 2020-21 [Link]. ‘Computer Science Savitribai Phule Pune University [Link]. (Computer Science) Computer Science Paper - III Course Code: CS 243 Title : Practical course on CS 241(Data Structures and Algorithms II) and CS 242 (Computer Networks 1) Teaching Scheme No. of Credits Examination Scheme 4 hrs 20 mins / week 2 IE : 15 marks Batch size : 12 UE: 35 marks Lab Bool The lab book is to be used as a hands-on resource, reference and record of assignment submission and completion by the student, The lab book contains the set of assignments. which the student must complete as a part of this course. Programming Assignments: Programs should be done individually by the student in the respective login. The codes should be uploaded on either the local server, Moodle, Github or any open source LMS. Print-outs of the programs and output may be taken but not mandatory for assessment, Assessment: Continuous assessment of laboratory work is to be done based on overall performance and lab assignments performance of student. Each lab assignment assessment will be assigned sgrade/marks based on parameters with appropriate weightage. Suggested parameters for overall assessment as well as each lab assignment assessment include-timely completion, performance, innovation, efficient codes and good programming practices. + Internal Evaluation : © 10 marks will be given based on Networking assignments. © 5 marks will be allocated for Assignment completion and practical attendance ‘© University Evaluation : ©. The Practical slip will be of 35 Marks which will be based on Advanced Data structures. Operating Environment: For Data Structures: © Operating system: Linux * Edit Any linux based editor like vi, gedit ete. ‘+ Compiler : ce or gee ‘Course Contents := Savieribai Phule Pune UniversityCBCS: 2020-21 [Link]. ‘Computer Science ‘Assignment | Binary Search Tree and Traversals 1, Implement Binary Search Tree (BST) to perform following operations on BST- Create, Recursive Traversals - Inorder, Preorder, Postorder 2. Perform following operations: insert, delete Assignment 2. Binary Search Tree Operations 1, Implement Binary Search Tree (BST) to perform following operations on BST-copy and mirror image of BST, counting leaf, non-leaf and total nodes, 2. Level-order traversal of binary search tree using queue. Assignment 3 Applications of Binary Tree 1. Sort set of elements using Heap sort 2, Encode a set of characters using Huffman encoding Assignment 4 Graph implementation 1. Implement Graph as adjacency matrix and adjacency list 2. Calculate indegree and outdegree of vertices 3. Graph traversals: BFS and DFS. Assignment 5 Graph Applications - I I. Implementation of Topological sorting 2. Implementation of Prims/Kruskals Minimum spanning tree algorithm Assignment 6 Graph Applications - II 1. Implementation of Dijkstra’s shortest path algorithm for finding Shortest Path from a given source vertex using adjacency cost matrix. 2. Implementation of Floyd Warshall algorithm for all pairs shortest path. Assignment 7 Hash Table 1. Implementation of static hash table with Linear Probing. 2. Implementation of static hash table with chaining, Assignment 8 Hash Table-2 I, Implementation of linked hash table with chaining, Assignment 9 Networking Assignment Assignment 10 Networking Assignment Savieribai Phule Pune University Page 16