Information information

Data and File Structures Laboratory | aka PDS Lab
MTech (CS) First Year First Semester | Syllabus

This Lab will have some joint lectures with the following course.
Introduction to Programming by Mandar Mitra (MM)
Schedule : 3 Lectures + 1 Practice Lab per week (before Mid-Sem)

Schedule : 2 Lectures / Lab Session per week (after Mid-Sem)
Venue : CSSC Lab, 4th Floor, S N Bose Bhavan (Library Building)

Assignments (~ 10) : Lab Tests (~ 5) = 50 : 50
There will be no Mid-Sem or End-Sem examination for this course.

Lecture schedule for a typical week will be as follows (after Mid-Sem). Changes will be notified in class.

Time Mon Tue Wed Thu Fri
14:15 - 17:00 Lecture/Lab -- -- Lecture/Lab --


Programming Environment

If CS15xx is your ISI MTech CS roll number, login to the CSSC Matlab server as follows: 
ssh mtc15xx@192.168.54.156
If you want to access gedit editor for programming, login to the Matlab server as follows: 
ssh -X mtc15xx@192.168.54.156
Follow the slides of Lecture 1 to get yourself acquainted with the basics of GNU/Linux.

Lectures lectures

Day Date Topic Note Ref
1 20 Jul 2015 Introduction to Linux [DeM] Slides [PDF] (B3), (B16)
2 22 Jul 2015 Preliminaries [MM] Slides [PDF]
blood-groups.c
gcd.c		 (B1), (B14),
(B15)
3 23 Jul 2015 Basics of C [MM] Slides [PDF] (B1)
4 24 Jul 2015 Practice Lab [DeM] -- --
5 27 Jul 2015 Problem Solving in C [SSG] Slides [PDF] (B1), (B2)
6 29 Jul 2015 Arrays, Sorting in C [ArB] Slides [PDF]
bubble-sort.c
selection-sort.c 		(B1), (B4),
(B13)
7 30 Jul 2015 Practice Lab [DeM, SSG] -- --
8 03 Aug 2015 Functions - I [MM] Slides [PDF] (B1)
9 05 Aug 2015 Functions - II [MM] Slides [PDF] (B1)
10 06 Aug 2015 Pointers in C [ArB] Slides [PDF] (B1)
11 07 Aug 2015 Practice Lab -- --
12 10 Aug 2015 Shell Programming [DeM] Slides [PDF] (B3), (B16)
13 12 Aug 2015 File I/O and Buffers [SSG] Notes
dog.c 		(B1)
14 13 Aug 2015 Practice Lab -- --
15 17 Aug 2015 Structures and
Unions - I [MM]		 Slides [PDF]
common.h
student-data.c 		(B1)
16 19 Aug 2015 Recursion [ArB] Slides [PDF]
permute-I.c
permute-II.c 		(B2), (B4),
(B13)
17 20 Aug 2015 Misc. Programming
Problems [MM]		 Slides [PDF] (B2)
18 21 Aug 2015 Practice Lab -- --
19 24 Aug 2015 Debugging with GDB
and Valgrind [SSG]		 GDB [PDF]
Valgrind [PDF]
Programmes 		GDB [vid]
Valgrind [vid]
20 26 Aug 2015 Linked Lists [ArB] -- (B5), (B6),
(B11)
21 27 Aug 2015 Stack and Queue [SSG] -- (B5), (B6),
(B11)
22 28 Aug 2015 Practice Lab -- --
23 31 Aug 2015 Dynamic Programming
[ArB]		 Slides [PDF] (B4), (B13)
24 02 Sep 2015 Makefile [DeM] Slides [PDF]
Programs 		(B17)
25 03 Sep 2015 Abstract Data Types [ArB] -- (B5), (B6),
(B11)
26 04 Sep 2015 Practice Lab -- --
Break for Mid-Semester Examinations
27 24 Sep 2015 Heaps, Skip Lists [ArB] -- (B5), (B11),
(B18)
28 28 Sep 2015 Basics of OOP : Java [DeM] Slides [PDF] --
29 01 Oct 2015 Threaded binary tree, Trie,
Range search: Kd-tree [ArB]		 -- (B11),
Note #1
30 05 Oct 2015 Basics of OOP : Java [DeM] Slides [PDF] --
31 07 Oct 2015 Introduction to GCC [AnB] Slides [PDF] --
32 15 Oct 2015 Convex hull, Geometry
problems [AnB]		 Slides [PDF]
Slides 50-62		 Note #2
33 29 Oct 2015 OOP applications [DeM] -- --
34 02 Nov 2015 Python [SSG] Hard Way GoogleClass
35 05 Nov 2015 OOP Revision [DeM] -- --
36 05 Nov 2015 Python [SSG] Think Python GoogleClass
37 09 Nov 2015 Python [SSG] Slides [PDF] B4 (Ch.13)
Note #3
38 12 Nov 2015 Applications [AnB] Decision Diagrams
Data Compression		 Note #4
Note #5


Note #1 : See the chapter on "Orthogonal range searching" in David Mount's lecture notes for Kd-trees.

Note #2 : Slide courtesy: Robert Sedgewick (Princeton).
The slide-deck contains elementary sorts with their codes as well, in case the students find them useful.

Note #3 : Slide courtesy: Erik D. Demaine and Charles E. Leiserson (MIT).

Note #4 : Slide courtesy: Pallab Dasgupta, IIT Kharagpur.

Note #5 : Slide courtesy: Robert Sedgewick (Princeton).

Assignments assignments

Assignments constitute 50% of the total marks (tentatively 10 assignments in total).

Assignment Uploaded Clarification Submission Note Marks
Assign. 1 [1]
Assign. 1 [2]		 30-07-2015 31-07-2015 03-08-2015 [guide] Marks
Comments
Solutions
Assign. 2 12-08-2015 14-08-2015 17-08-2015 [guide] Marks
Assign. 3 15-08-2015 18-08-2015 24-08-2015 [guide] Marks
Assign. 4 24-08-2015 28-08-2015 31-08-2015 [guide] TBA
Assign. 5 16-09-2015 24-09-2015 28-09-2015 [guide] TBA
Assign. 6 16-09-2015 25-09-2015 05-10-2015 [guide] TBA
Assign. 7 07-10-2015 09-10-2015 16-10-2015 [guide] TBA
Assign. 8 26-10-2015 30-10-2015 03-11-2015 [guide] TBA
Assign. 9 27-10-2015 05-11-2015 09-11-2015 [guide] TBA
Assign. 10 09-11-2015 16-11-2015 23-11-2015 [guide] TBA

Tests tests

The Lab tests constitute 50% of the total marks (tentatively 5 lab tests in total).

Test Date Question Solution Marks/Comments
1 31-07-2015 Lab Test - I Solution : P1
Solution : P2(a)
Solution : P2(b-g)		 Marks
Comments
2 14-08-2015 Lab Test - II TBA Marks
Comments
3 21-09-2015 Lab Test - III TBA TBA
4 07-11-2015 Lab Test - IV TBA TBA
5 30-11-2015 Lab Test - V TBA TBA

 

Announcements

  • Assignment 10 posted (due on 23rd Nov).
  • Assignment 9 posted (due on 9th Nov).
  • Assignment 8 posted (due on 3rd Nov).
  • Lab Test 2 marks/comments posted.
  • Assignment 2 marks posted.
  • Assignment 7 posted (due on 16th Oct).
  • Assignment 3 marks posted.
  • Assignment 6 posted (due on 5th Oct).
  • Assignment 5 posted (due on 28th Sept).
  • Lab Test 3 (scheduled on 21st Sept).
  • Assignment 4 posted (due on 31st Aug).
  • Assignment 1 marks/comments posted.
  • Assignment 3 posted (due on 24th Aug).
  • Lab Test 1 marks and comments posted.
  • Assignment 2 posted (due on 17th Aug).
  • Lab Test 2 (scheduled on 14th Aug).
  • Lab Test 1 questions and solutions posted.
  • Assignment 1 posted (due on 3rd Aug).
  • Lab Test 1 (scheduled on 31st July).
  • Basic course information posted.
  • Course website is now online.

Instructors

Teaching Assistants

  • Amit Yadav (AY)
  • Ashwin Jha (AJ)
  • Avik Chakraborti (AC)
  • Gopinath Mishra (GM)
  • Soumi Chattopadhyay (SC)

Study Material

  • (B1) The C Programming Language
    B. W. Kernighan and D. M. Ritchie
    Prentice Hall, India
  • (B2) How to Solve it by Computer
    R. G. Dromey
    Pearson Education
  • (B3) The Unix Programming Environment
    B. W. Kernighan and R. Pike
    Prentice Hall, India
  • (B4) Introduction to Algorithms
    T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein
    MIT Press
  • (B5) Fundamentals of Data Structures
    E. Horowitz and S. Sahni
    Universities Press
  • (B6) Data Structure Techniques
    T. A. Standish
    Addison Wesley
  • (B7) The C++ Programming Language
    Bjarne Stroustrup
    Addison Wesley
  • (B8) C++ - The Complete Reference
    Herbert Schildt
    McGraw Hill Education (India)
  • (B9) Object-Oriented Programming in C++
    Robert Lafore
    SAMS
  • (B10) Programming Languages Design and Implementation
    T. W. Pratt and M. V. Zelkowitz
    Pearson
  • (B11) Fundamentals of Data Structures in C
    E. Horowitz, S. Sahni and S. Anderson-Freed
    Silicon Press
  • (B12) Data Structures and Algorithm Analysis in C++
    Mark A. Weiss
    Pearson
  • (B13) Algorithms
    Robert Sedgewick and Kavin Wayne
    Addison-Wesley Professional
  • (B14) The Practice of Programming
    Brian Kernighan and Rob Pike
    Addison-Wesley Professional
  • (B15) Programming Pearls
    Jon Bentley
    Pearson
  • (B16) The Linux Command Line  
    William Shotts
    No Starch Press
  • (B17) The GNU Make Manual  
    R. M. Stallman, R. McGrath and P. D. Smith
    Free Software Foundation
  • (B18) Randomized Algorithms
    Rajeev Motwani and Prabhakar Raghavan
    Cambridge University Press