Data Structures and Algorithms

Data Structures and Algorithms

Course Contents

This is an introductory level course in Data structures and algorithms, offered by CSE dept, to students of other departments who have been permitted to register for a 'minor'. The course is meant for non-CSE, UG students. CSE/PG students should take one of the other algorithms courses being offered.The syllabus definition given for this course is available from the ASC website. It is copied here for information:
Introduction to data structures, abstract data types, analysis of algorithms. Creation and manipulation of data structures: arrays, lists, stacks, queues, trees, heaps, hash tables, balanced trees, tries, graphs. Algorithms for sorting and searching, order statistics, depth-first and breadth-first search, shortest paths and minimum spanning tree.
The course will not go into much excruciating details of various C++ implementation issues of data structures and algorithms; It will not be too top-level either. The course will focus on concepts that are 'broadly useful', not only in CSE but also other disciplines. Mostly we will study "What are some useful data structures and algorithms?”.
We will do in-class group discussions to design data structures for simpler versions of real-life applications amd programming problems. We will focus on "Why are the data structures and algorithms designed in a given way?". We will study pros-and-cons of various solutions to a given problem (Why is a particular data structure or algorithm "better" than some other?). We will also discuss "How to implement these data structures and algorithms?" in a systematic manner.

Lecture Schedule

The course is in Slot 5. There will be two lectures per week, each of 90 minutes duration.Most of the readings correspond to the sections in the following Textbooks:
[GTM]: Data Structures and Algorithms in C++ , by M. Goodrich, R. Tamassia and D. Mount, Seventh Edition.
[RS]: Algorithms in C++ , by R. Sedgewick, Third Edition.

No	Date	Topic	Reading/Slides	Remarks
-	05 Jan	No class	-	Registration still ongoing
-	07 Jan	No class	-	Institute: Techfest 2011
1	12 Jan	Introduction	-	Need for data structures, their relation with algorithms, ideas of correctnesss, complexity
2	14 Jan	C++ recap	[GTM Ch.1]	Complete this topic as self study
3	19 Jan	Arrays and Linked Lists	[RS Ch.3]	-
4	21 Jan	List processing	[RS Ch.3]	-
-	26 Jan	No class	-	Republic Day
5	28 Jan	String processing	[RS Ch.3]	-
6	02 Feb	Complexity analysis	[GTM Ch.3]	-
7	04 Feb	Quiz 1	-	10% weightage; One A4 sheet of handwritten notes allowed
8	09 Feb	Stack applications	[RS Ch.4]	Slides for Stack-Queue
9	11 Feb	Queue and Deque	[RS Ch.4]	Activity: Implementing a Queue using Stacks
-	16 Feb	No class	-	Institute Holiday
10	18 Feb	Tutorial	-	Problem-solving on topics covered so far
-	23 Feb	No class	-	Midsem week
11	25 Feb	Midsem: All topics so far	-	30% weightage; One A4 sheet of handwritten notes is allowed. Links to:Some Animations, and More animations.
12	02 Mar	Trees	[GTM Ch. 6]	-
13	04 Mar	Tree traversal	[GTM Ch. 6]	Homework 1 to be assigned
14	09 Mar	Quicksort and Mergesort	[RS Ch. 7, 8]	Elementary sorting [RS Ch. 6] - self study
15	11 Mar	Priority Queue	[RS Ch. 9]	Homework 1 is due on 14th March
16	16 Mar	Heapsort	[RS Ch. 9]	Slides for Priority Queues and Heapsort
17	18 Mar	Binary Search Trees	[GTM Ch. 9]	Homework 2 to be assigned
18	23 Mar	AVL Trees	[GTM Ch. 9]	-
19	25 Mar	Hashing	[RS Ch. 14]	Homework 2 is due on 28th March
20	30 Mar	Quiz 2: All topics after Midsem	-	10% weightage; One A4 sheet of handwritten notes is allowed.
21	01 Apr	Graphs: Data Structures	[GTM Ch. 12]	Homework 3 to be assigned
22	06 Apr	Graphs: Traversal	[GTM Ch. 12]	-
23	08 Apr	Shortest Path, MST	[GTM Ch. 12]	Homework 3 is due on 15th April
24	13 Apr	Tutorial	-	Problem-solving and Practice Test
25	15 Apr	Closure	-	More problem-solving; Last day of classes
26	28 Apr	End-sem: All topics	-	40% weightage; One A4 sheet of handwritten notes is allowed.