Course catalog description: In-depth analysis of algorithms using object-oriented techniques. Comparative algorithm analysis, in-depth sorting algorithms, graphs, NP-Completeness, object-oriented design. Emphasis is on programming and practical applications in Electrical and Computer Engineering. Programming languages include C++ and Java.
Credits and contact hours: 3 credits; 1 hour and 20-minute session twice a week, every week
Pre-Requisite courses: 14:332:252, 14:332:254
Co-Requisite courses: None
Topics Covered:
- Review of Data Structures portion of PM-I, stacks, queues, linked lists, sorting algorithms
- Basics of object-oriented programming (C++)
- Standard conversion under derivation, virtual functions, virtual base classes, OO design.
- Algorithm Analysis, Big-Oh notation, Solution of Recurrence Equations
- Multiway Search Trees, Top Down Trees, Traversal and Insertion in Top Down Trees
- B-Trees, Search Traversal and Insertion, Implementation of algorithms for B-Tree
- Efficiency of B-Tree and Top Down Trees; B+ Trees and algorithms to implement them
- Graphs, Adjacency Matrix Representation, Transitive Closure; Transitive Closure using Warshall’s Algorithm
- Shortest Path Algorithm, Adjacency List representation of Graph, Network Flow Problem and the algorithm to compute the optimal flow
- Spanning Forests of Graph, Graph Traversal, Depth First Traversal, Breadth First Traversal Minimum Spanning Trees
- Basics of Java
Textbook: F. Carrano, Data Abstraction & Problem Solving with C++, Prentice Hall.