14:332:351 Programming Methodology II

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.