This page will be updated regularly. Please visit (and reload) often. You are responsible for all information on this page.
|
COL 106: Data Structures
(Sem I, 2019-2020)
Tue, Thu, Fri at 11:00-11:50 in LH121
Lab in LHC504, 1-5pm
|
News & Announcements
Shortlisted good category videos // Uploaded 14 Nov 2019
Disclaimer: All the submitted videos will be graded and marks will be given from 0.1 to 0.5 based on poor , average and good categories. // Updated 15 Nov 2019
PROGRAMMING TEST on NOV 9 2019.
- The exam will be held in two sessions in LH503/504 on 9 Nov 2019. Students with
entry numbers starting with 2018CS and those starting with 2018MT will be taking
the test in the first session at 9 and the rest tin the second session at 1115.
See below for details.
-
Please do not bring your phone or other electronic device. Please avoid carrying
any bag also, as the space for bags in the hallway leading to the labs is limited.
-
The first test will begin at 9:05am and close at 11:05am. There will be no extra
time. (This means you must be logged in and ready by 9:05 to avail yourself of the
entire 2 hours.) Entry will begin for this session at 8:55am. Arrive no earlier
than 850. Please make four queues in the hallway as you arrive for you session.
You must log out and leave the Lab promptly by 11:09. No entry will be allowed
after 9:05. You will not be shifted to the second session if you come late.
-
The second test will begin at 11:20am and close at 1:20. There will be no extra
time. (You must be logged in and ready by 11:20.) Entry for the second session
will begin at 11:10. Please DO NOT arrive in the hallway before 11:00. After you
arrive, please get in one of four queues starting in the hallway and remain quiet.
No entry will be allowed after 11:20. There will be no re-test opportunity if you
come late.
-
The test will be on Moodle, similar to the mock test. You will have access to
Oracle's documentation for packages java.util, java.io and java.lang on Moodle.
You will not have access to any site outside of moodle. In each test, a skeleton
will be provided and you will be directed to fill in some code. Some tests will
run immediately, but the entire suite may have to run off-line and the final grade
may be different from the proposed grade.
Assignment 6
-
List of upcoming topics(Announcement made on 2 Nov 2019)
- Next week : Complete shortest path, Complete quick-sort.
- After that: Radix-sort
OLD ANNOUNCEMENTS
-
List of upcoming topics
- Over next 3 lectures : Insertion sort, Selection sort, Heap sort, Merge sort, Quick sort.
Their analysis and comparison.
- After that: Bucket sort/Radix sort
-
Announcement related to Assignment 4 and 5
- Assignment 4 remains due on Oct 2, one day late penalty applies on Oct 3.
- Assignment 5 will be an extension (superset) of assignment 4.
- If you cannot submit now, but Assignment 4 tests (call it Test4) on Assignment 5
submission are correct, you get up to 3 marks for assignment 4 (along with whatever
you get for assignment 5). In other words, you get a 2 mark late penalty for
assignment 4.
- Those who submit Assignment 4 by Oct 3, may yet improve their assignment 4 marks,
if Test4 on their Assignment 5 submission fetches more marks than Test4 on their
Assignment 4 submission.
- Those who do not get such an improvement in Test4 score on Assignment 5
submission, will still get other opportunity for up to 1 mark improvement (see 6
below).
- Assignment 5 will have correctness tests beyond assignment 4, which will be worth
3 marks. Efficiency testing will be worth 2 marks.
- Those whose Assignment 4 submission is final (i.e., there is no improvement on
Test4 on Assignment 5 submission), will get up to 1 extra mark for their speed tests
in Assignment 5.
-
Mentor and mentee registration
Video Making extra credits
There will be up to 0.5 extra credit marks available for each topic. The video on
any topic cannot be more than 5 minutes and uploaded to YouTube by default. It will
be graded on clarity (not good, useful, or excellent) and marked accordingly. All
excellent and useful videos will also be posted on the class website for others. The videos can be on any class topic. You can make maximum 10 videos. You can do it in a group of 2 if you wish but marks will be shared in that case. Excellent videos will be linked to course web page with col106 Youtube channel.
Kindly make the video with clear audio and landscape mode view only
Lecture material
Minor 2 question paper Set A Set B
Online Resources
Supplementary Material
Video for Credit(PDF)
Instructor and TA information
| Professors: |
Subodh Kumar |
| E-mail: |
s u b o d h @ c s e (.iitd.ac.in)
|
| Office: | IIA 422 |
| Office hours: | Tue, Wed 1215-115, or
by appointment (send mail) |
|
Teaching Assistants:
|
| Name | Email |
|---|
| Sanjana Singh | <csz168122>
| | Soumen Basu | <csz198406>
| | Sandeep Kumar | <anz178353>
| | Prashant Agrawal | <csz188011>
| | Sahil Manchanda | <csz188551>
| | Ankur Sharma | <cs5150278>
| | Prayas Sahni | <mcs182839>
| | Chirag Manwani | <mcs182018>
| | Ruturaj Mohanty | <mcs182012>
| | Sanjana Singh | <mcs152331>
| | Siddhant Arora | <cs5150480>
| | Anant Sushil Gulgulia | <mcs192558>
| | Chinmay Shirish Degwekar | <mcs192560>
| | Het Shaileshkumar Patel | <mcs192562>
| | Kartik Jain | <mcs192563>
| | Deepanshu Jindal | <cs1160312>
| | Rajas Bansal | <cs1160385>
| | Ankita Gupta | <mcs192559>
| | Disha Vijay Kathin | <mcs192561>
| | Vikas Upadhyay | <vikas.upadhyay>
|
|
|
Please add cse.iitd.ac.in after the email id
Syllabus
Introduction to object-oriented programming through stacks queues and
linked lists. Dictionaries; skip-lists, hashing, analysis of collision
resolution techniques. Trees, traversals, binary search trees, optimal
and average BSTs. Balanced BST: AVL Trees, 2-4 trees, red-black trees,
B-trees. Tries and suffix trees. Priority queues and binary heaps.
Sorting: merge, quick, radix, selection and heap sort, Graphs: Breadth
first search and connected components. Depth first search in directed
and undirected graphs. Disjkra's algorithm, directed acyclic graphs and
topological sort. Some geometric data-structures.
The language used will be Java. It is expected that you will learn it on your own and will not be covered in any detail class.
Prerequisites: COL100
Tentative Course Schedule: :
Attendance Policy
100% attendance is expected.
Academic Integrity Code
Academic honesty is required in all your work.
You must solve all programming assignments entirely on your own,
except where group work is explicitly authorised. This means you
must not take, neither show, give or otherwise allow others to take
your program code, problem solutions, or other work.
You are responsible for protecting your design and code against access by others. (Do
not leave it where others can find it. Do not give it to someone
for submission on your behalf. Do no use any fragment of code
obtained online or from someone else.)
Falsifying program output or results is cheating also.
If your submission matches code in our database or another submission, you will be penalized as described below.
Students who are caught cheating in an assignment will be given -10
marks in that assignment. Cheating during exams earns -50 marks. A
second violation earns an F.
Be aware that code analysis tools will be used on every assignment to
detect cases of cheating.
Please see your professor if you have any questions about what is
permissible.
Assignments & Grading
To audit-pass the course, a minimum of C is required.
Late policy:
You are allowed up to 24 hours of late submission for each assignment,
with a penalty of 1 mark. Submissions later than that will not be
graded.
Submission Requirements:
Assignment submissions will be electronic. You will submit a single
ziped file (encoded in b64 format) -- built from assignment directory.
You must include a file called README in your directory, describing the
implementation of each function and its status (whether it compiles,
which tests work, what work remains). Other than that, the directory
should contain all your .java files and a makefile and nothing else.
Appropriately name submission files (entrynumber_assignment1,
entrynumber_assignment2, etc.). All input and output files must stay in
the same directory. The script will extract files, compile them and run
them on test cases. Make sure your code works on linux with java 1.8
(you should test it in one of the CSC/LHC labs, as announced.) If the
script fails to run your code, you will get a 0. If your test results do
not match the description in the README file, you will lose 50% of your
marks obtained in that assignment. If you do not follow the design
given in the assignment, you will lose 25% of the marks obtained.
Textbook
Goodrich, M. and Tamassia, R.
Data Structures and Algorithms in Java ,
John Wiley and Sons, Inc.
Other books on JAVA:
Java in a nutshell by Flannagan, (O'Reilly)
Introduction to Programming using java by Arnow & Weiss,
(Addison-Wesley)