Algorithm Analysis and Advanced Data Structure
A study of data structures and the algorithms used to process them. Algorithms for handling strings, stacks, lists, trees and graphs. Sorting and searching techniques. Recursive and non-recursive algorithms. Efficiency considerations. Prerequisites: CPSC 2100 and MATH 2030 or MATH 3030 with minimum grades of C or department head approval.
- Understand and develop recursive algorithms. Implement recursive programs.
- Understand and implement classical sorting and searching algorithms.
- Understand and implement classical data structures and associated algorithms (trees, heaps, linked lists, graphs).
- Understand and implement applications of classical data structures.
- Demonstrate an understanding of "Big O" notation, and its mathematical definition.
- Determine the computational complexity of algorithms.
- Determine the memory storage requirements of data structures.
- Evaluate and compare options regarding algorithms, data structures and other aspects in the design, implementation and analysis of a software product.
Required: Data Structures and Algorithms in Java, 5th Edition
by Michael T. Goodrich, Roberto Tamassia
Lecture 1: Indices, Nodes, and Recursion
Lecture 2: Analysis Tools
Lecture 3: Stacks, Queues, and Deques
Lecture 4: Trees
Lecture 5: Heaps and Priority Queues
Lecture 6: Hash Tables, Maps, and Skip Lists
Lecture 7: Sorting, Sets, and Selection
Lecture 8: Graph Algorithms