Department of Computational and Data Sciences
Data Structures and Programming
- Instructor: Yogesh Simmhan (email | www)
- Teaching Assistant: Prateeksha Varshney (email)
- Course number: DS286 (Formerly SE286)
- Credits: 2:1
- Semester: Aug, 2016
- Lecture: Wed/Fri 10-11AM, Lab: Mon 10-11AM
- Room: CDS/SERC 202
Overview
This is an introductory course in data structures and programming, meant for students who have not had a formal course in programming, algorithms and data structures as part of their undergraduate program. The course will introduce of problem solving using programs and design of algorithms and their complexity. It will review elementary data structures such as Arrays, Stack, Queues, Maps, and related algorithms for manipulating the data structures. It will also discuss sorting and searching techniques, and their complexity. We will also briefly explore more advanced data structures such as graphs and graph algorithms, balanced trees, tries and heaps. A overview of parallelism and concurrent data structures will also be given toward the end of the course. Algorithmic strategies such as greedy Algorithms, Dynamic Programming and Divide and Conquer will also form part of the learning.
These lectures will be complemented by lab sessions that introduce object oriented programming with C++, implementing the data structures using C++, and also using standard data structure libraries present in the language. There will be periodic programming assignments to validate these concepts.
Topics in this course are loosely based on IEEE and ACM’s Curriculum Guidelines for Undergraduate Degree Programs in Computer Engineering, a draft of which is available online.
This course is a precursor to more advanced courses like E0 251: Data Structures and Algorithms, E0 225: Design and Analysis of Algorithms, DS 292: High Performance Computing, DS 295: Parallel Programming, and DS 256: Scalable Systems for Data Science. Students already familiar with data structures and programming may prefer those rather than this introductory course.
Pre-requisites
This is an introductory course on data structures and programming. So the pre-requisites are minimal — knowing to operate a computer, preferable Linux, using the commandline, installing packages, using SSH, using a text editor or IDE — but students are expected to pick up the skills rapidly as part of the lab sessions.
Assessment
The total assessment score for the course is based on a 1000 point scale. Of this, the weightage to different activities will be as follows:
40% Homework | About 7 programming assignments of 50-100 points each (400 points) |
10% Online Coding | Self-selected programming assignments on online coding website (CodeChef) (100 points) |
50% Exams | One Mid-term (200 points) and one Final (300 points) exam. |
Academic Integrity
Students must uphold IISc’s Academic Integrity guidelines. We have a zero-tolerance policy for cheating and unethical behavior in this course and failure to follow these guidelines will lead to sanctions and penalties. This includes a reduced or failing grade in the course, and recurrent academic violations will be reported to the Institute and may lead to an expulsion.
Learning takes place both within and outside the class. Hence, discussions between students and reference to online material is encouraged as part of the course to achieve the intended learning objectives. However, while you may learn from any valid source, you must form your own ideas and complete problems and assignments by yourself. All works submitted by the student as part of their academic assessment must be their own.
- Plagiarism
- Verbatim reproduction of material from external sources (web pages, books, papers, etc.) is not acceptable. If you are paraphrasing external content (or even your own prior work) or were otherwise influenced by them while completing your assignments, projects or exams, you must clearly acknowledge them. When in doubt, add a citation!
- Cheating
- While you may discuss lecture topics and broad outlines of homework problems and projects with others, you cannot collaborate in completing the assignments, copy someone else’s solution or falsify results. You cannot use notes or unauthorized resources during exams, or copy from others. The narrow exception to collaboration is between team-mates when competing the project, and even there, the contribution of each team member for each project assignment should be clearly documented.
- Classroom Behavior
- Ensure that the course atmosphere, both in the class, outside and on the online forum, is conducive for learning. There are no “stupid” questions, so ask away. Actively participate in discussions but do not dominate or be abusive. Be considerate of your fellow students and avoid disruptive behavior.
Resources
- Textbook:
- Lectures
- Data Structures, Algorithms, and Applications in C++, 2nd Edition, Sartaj Sahni [Tata Book House]
- Select additional readings
- Lab
- The C++ Programming Language, 3rdEdition, Bjarne Stroustrup
- Lectures
- Online Forum: DS286.Aug16@mailman.serc.iisc.in | Mailman Info Webpage (All students MUST join the mailing list for all official announcements)
- Computer Access: Students will be provided access to the CDS student cluster for doing their assignments. All submissions must compile and have been tested on these course machines.
- Other Resources
- THE ART OF COMPUTER PROGRAMMING (Volume 1 / Fundamental Algorithms), Donald Knuth
- Introduction to Algorithms, Cormen, Leiserson, Rivestand Stein
- http://www.geeksforgeeks.org/data-structures/
Teaching & Office Hours
- Lecture: Wed and Fri 10-11AM, CDS/SERC 202 (Yogesh)
- Lab: Mon 10AM-11AM, CDS/SERC 202 (Prateeksha)
- Office Hours: By appointment
Tentative Schedule
The course schedule — both dates and topics — are subject to change. Please subscribe to the mailing list to get notified of changes.
Lecture Schedule
No. Date Topics Slides
1 2016-08-05
Introduction to the Course L1 slides
2 2016-08-12 Introduction to Programming L2 slides
3 2016-08-17 Introduction to Software Design L3 slides
4,5 2016-08-24,26 Lists, Linked list, Arrays, Sparse Matrices L4+5 slides
6,7 2016-08-31,2016-09-02 Introduction to Algorithmic Analysis L6+7 slides
8 2016-09-07 Stacks L8 slides
9 2016-09-09 Queues L9 slides
10 2016-09-14 Dictionary, Skip List L10 slides
11,12 2016-09-16,21 Hashmap, Hash Function L11+12 slides
13,14 2016-09-23,26 Tree, Binary Trees, Expression Trees L13+14 slides
15,16 2016-09-28,30 Binary Search Tree L15+16 slides
17 2016-10-05 Sorting L17 slides
* 2016-10-07 MIDTERM EXAM (200 points)
Topics from Lectures 1-16Midterm review
18 2016-10-14 Balanced Trees: AVL Trees L18 slides
19 2016-10-21 Balanced Trees: B-Tree L19 slides
20-21 2016-10-26,28 Graph Data Structures L20-21 slides
22-23 2016-11-02,04 Graph Algorithms L22-23 slides
24 2016-11-04 Heap, Priority Queue
L24 slides
25-26 2016-11-11,16 Algorithmic Strategies: Dynamic programming, Greedy strategies
L25-26 slides
27-29 2016-11-18,23,25 Concurrent Data Structures L27-28 slides, L29 slides
* 2016-12-07, 11AM FINAL EXAM (300 points)
Topics from Lectures 1-30
Lab Schedule
DS286-Aug16 Lab Schedule
No. | Date | Topics | Slides |
---|---|---|---|
1 | 2016-08-08 | Introduction to C++, Hello World, IDE, compiling | Lab 1 https://www3.ntu.edu.sg/home/ehchua/programming/howto/EclipseCpp_HowTo.html, http://www.ubuntuhandbook.org/index.php/2014/06/install-latest-eclipse-ubuntu-14-04/, http://www.eclipse.org/downloads/eclipse-packages/ |
2 | 2016-08-10 | Introduction to C++, OO programming | Lab 2 |
3 | 2016-08-19 | Intro to C++, primitive types, control flow, Pointers, Memory Management. Assignment 1 To Be Posted | Lab 3? |
4 | 2016-08-22 | Intro to C++, Pointers, Memory Management, Makefile, Headers. Review of Assignment 1. | Lab 4? |
5 | 2016-08-29 | C++ Lists, Linked List, Arrays, etc. Assignment 2 To Be Posted | |
6 | 2016-09-14 | ||
7 | 2016-09-19 | ||
8 | 2016-09-26 | ||
... | ... | ... | |
Assignments
- Assignment 0
- Assignment 1 [PDF] (Posted on 2016-08-20, Due on Sunday 2016-08-28 by 11:59PM IST) [50 points]
- Skeleton Code required for assignment: DS286.Aug16.A01
- Errata: The skeleton code can store only 6 items at a time in the list. So example 4 in Sample Inputs section with 8 inputs retained at a time will not work:
./listdemo.out a157a2.0a3.0a0.0a.1a1.0a.1e10a1e23p [157,2.0,3.0,0.0,0.1,1.0,0.1e10,1e23]
Instead, replace example with:
./listdemo.out a157a2.0a3.0a.1a.1e10a1e23p [157,2.0,3.0,0.1,0.1e10,1e23]
- Assignment 2 (Posted on 2016-08-29, Due on Sunday, September 11, 2016, 11:59pm IST) [50 points]
- Assignment description: DS286.Aug16.A02.pdf
- Skeleton code: DS286.Aug16.A02-Errata.tar (including errata to Complex.h with == operator)
- Assignment 3 (Posted on 2016-09-15, Due on Wednesday, September 28, 2016, 11:59pm IST) [75 points]
- Assignment description: ds286-aug16-assignment3.pdf
- Skeleton code: ds286-aug16-03assgn.tar
- Errata: In ParenMatch.h, the comment:
// Updates the Expression in parenStack as necessary.
should instead read:
// Updates the Expression in exprStack as necessary.
- Assignment 4 (Posted on 2016-10-13, Due on Wednesday October 26, 2016, 11:59pm IST) [75 points]
- Assignment 5 (Posted on 2016-10-28, Due on Monday, 14 November, 2016, 11:59pm IST) [100 points]
- Assignment description: ds286-aug2016-a05.pdf
- TBD: Sample graph files small.in , medium.in and large.in with input parameters.