Welcome to Data Structures and Algorithms.
Instructor: Dr. Vaide Narvaez
Schedule: Tuesday and Thursday 8:30-10:00am
An understanding of data structures and algorithm analysis will be presented in the following topics: stacks queues, recursion, linked lists, trees, graphs, sorting and searching. This will serve as the basis for further studies in information systems and approaches using an application perspective. Case Studies are required.
The course will cover:
- basic algorithm analysis (e.g., asymptotic analysis of upper and average complexity, big-O, little-o, omega, and theta notation);
- general algorithm strategies such as brute-force algorithms, greedy algorithms, divide-and-conquer, and dynamic programming;
- fundamental computing algorithms including numeric computations, searching and sorting, graph algorithms, and string matching; introduction to data structures, covering stacks, queues, linked lists, and rooted trees; advanced data structures, including B-trees and heaps.
Course Syllabus and Material
|1||Lecture 1: The role of algorithms in computingLecture 2: Java: a crash course||
|2||Lecture 1: Arrays vs. Linked ListsLecture 2: Analyzing Algorithms||
|3||Lecture 1&2: Growth of functions: Asymptotic notation||
|4||Lecture 1: Elementary data structures: Stacks and QueuesLecture 2: Linked Lists||
Important!!:The queue is full when head=tail+1, which allows one empty cell in the array. If we allow to enqueue in such a case, we wont be able to distinguish between empty and full queues.
|5||Lecture 1&2: Hash tables||
|6||Lecture 1&2: Binary search trees||
|7||Lecture 1&2: Sorting algorithms||
|8||Lecture 1&2: Elementary Graph AlgorithmsMidterm review||
|9||(No classes this week!!!)|
|10||Lecture 1: Minimum Spanning TreesLecture 2: Single source shortest paths(1)||
|11||Lecture 1: Single source shortest paths(2)Lecture 2: All pairs shortest paths||
|12||Lecture1: B-TreesLecture 2: B-trees: Basic operations||
|13||Lecture: String Matching||
Important!!!:Assignment 4, question 3, assume the B-tree is of minimum degree t=3
|14||Lecture 1&2: Red-Black Trees||
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms. 2nd edition, 2001 MIT Press.
Supplementary reading materials
- Robert Lafore, Data structures and algorithms in JAVA, 2nd edition, 2003, Sams Publishing.
- Adam Drozdek, Data Structures and Algorithms in C++, 3rd edition, 2005, Thomson Course Technology.
- Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, Algorithms, 2006, McGraw-Hill.