Data Structures and Algorithms

Syllabus:

Session

Lecture 1

Introduction to “Data structures & algorithms”

Chapter 1 (Introduction to Data Structures, Tanenbaum)

Lecture 2

Lab 0

Abstract data types (ADT)

Introduction & installation (C/ C++ refresher)

Pointers, Arrays, Structures, Class

Lecture 3

Algorithmic analysis and complexity I: Mathematical review, Model, What to Analyze?

Chapter 2

(Algorithm analysis, Weiss)

Lecture 4

Lab 1

Algorithmic analysis and complexity II: Running Time Calculations with Examples

Implementation of basic data structures (vector)

Lecture 5

Algorithmic analysis and complexity III: Recursion, Masters Theorem

Chapter 2

(Algorithm analysis, Weiss, Corman)

Lecture 6

Lab 2

Lists, stacks, queues I: LIST ADT

Implementation of basic data structures (list)

Lecture 7

Lists, stacks, and queues II: LIST ADT (Contd.), STACK ADT

Chapter 3 (Lists, Stacks, and Queues, Weiss)

 Lecture 8

Lab 3

Lists, stacks, queues III: Queue ADT

Algorithmic complexity of elementary operations

Lecture 9

Sorting algorithms I: Insertion sort, lower bound for Simple Sorting Algorithms

Chapter 7 (Sorting)

Lab 4

Using lists, stacks, and queues I

Lab 5

Sorting algorithms II: Quick Sort, Analysis, Bucket Sort

 Using lists, stacks, and queues II

Lecture 10

Priority Queues, Heaps, Application of Heaps, Heap Sort

Chapter 7 (Sorting)

Lecture 11

 Lab                                                                   

Lecture 12

Lab 6

Trees I: Implementation, Trees Traversals

 Sorting algorithms

Chapter 4 (Trees)

Lecture 13

Trees II: Binary Trees: Implementation, Expression Trees

 Chapter 4 (Trees)

Lecture 14

Lab 7

Trees III: Search Tree ADT, Tree Operations (Find, Insert, Delete, Average Case Analysis)

Trees III: Balanced trees & AVL trees (**Nov 3**) 2-3:15 pm

Lecture 15

Trees IV: Balanced Trees, AVL Trees

Lecture 16

Lab 8

Graph algorithms I: Definitions, Representations

Binary search trees

Chapter 6 (Priority Queues)

Lecture 17

Graph algorithms II: Topological sorting, Shortest Path Algorithms (Dijkstra’s Algorithm)

Chapter 9 (Graph algorithms)

Lecture 18

Lab 9

Graph algorithms III: DFS, BFS, Applications

Tree traversals

Lecture 19

Graph algorithms IV: Minimum Spanning Trees, Prim’s, Kruskal’s Algorithm

Chapter 9 (Graph algorithms)

Lecture 20

Lab 10

Hashing I: General Idea, Hash Functions, Separate Chaining

Heaps

Lecture 21

Hashing II: Open Addressing, Rehashing, Extendible Hashing

Chapter 5 (Hashing)

Lecture 22

Lab 11

Other Topics: Introduction to NP-completeness

Graphs I

Lecture 23

Other Topics: Algorithm Design Techniques I (Greedy Algorithms, Dynamic Programming)

Chapter 5 (Hashing)

Lecture 24

Lab 12

Other Topics: Algorithm Design Techniques II (Randomized Algorithms, Backtracking)

Graphs II