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

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

The course is in Slot 5. There will be two lectures per week, each of Most of the readings correspond to the sections in the following Textbooks:

[GTM]:

[RS]:

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

__90 minutes__duration.

[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. |

I am very happy from your lecture notes

ReplyDelete