COP 4530 Data Structures, Algorithms, and Generic Programming

Course Description:         

Making efficient use of computational resources is one of the important tasks of any computer scientists. In this course we will explore different ways of organizing data to facilitate such sufficient use. This course covers the following topics:
  • Data structures: Abstract data types (ADTs), vector, deque, list, queue, stack, graph, digraph, table, map (associative array), priority queue, set, and tree, etc. 
  • Algorithms: Algorithms are formalizations of processes that result in predictable and desirable outcomes. They are used in a variety of contexts. Particularly, data structures are made usable by implementing algorithms for searching, sorting, and indexing the structures. Algorithm design, complexity analysis and correctness proof form important components in study of algorithms. 
  • Generic programming: Generic programming is the science of component re-use. We will explore coding for re-use of both data structures and algorithms in C++. Coding for re-use and re-use of code are important aspects of software engineering.
We will also have several substantial programming projects that involve the implementation and use of data structures, algorithms, and generic programming.

Course Objective:

The objective of the course is to teach students how to design, write, and analyze the performance of C/C++ programs that handle structured data and perform more complex tasks, typical of larger software projects. Students should acquire skills in using generic principles for data representation and manipulation with a view for efficiency, maintainability, and code-reuse. Successful students will, at the end of the course, be able to demonstrate analytical comprehension of concepts such as abstract data types (vectors, lists, deques, trees, etc.), generic programming techniques (containers, adaptors, accessing data through interface, iterators, etc.), algorithms (sorting, using stacks and queues, tree exploration algorithms, etc.), and efficiency analysis (which data structures allow efficient interfaces to particular forms of data access, such as random vs. sequential data access or insertion). The students should be able to demonstrate similar skills in related implementation tasks in the C/C++ language, including extensive use of templates to allow for modularity and re-usability of code. 

Prerequisites:

  • COP 3330: Object-Oriented Programming
  • MAD 2104: Discrete Mathematics
  • CDA  3100: Computer Organization I (co-requisite)
  • This course requires that the student be proficient with C++ and object oriented programming concepts.
  • Student also need to have a user-level knowledge of Unix, and be comfortable working in a Unix environment.
  • The pre-requisites will not be waived.
  • If you have doubts whether you satisfy the course pre-requisites, please contact the instructor.

Textbooks

  • Required textbook
    • “Data Structure and Algorithm Analysis in C++”, by Mark Allen Weiss. Publisher: Addison Wesley, 4th Edition, 2013.
  • Recommended optional textbooks
    • “C++ Primer”, by Lippman, Lajoie, and Moo. Publisher: Addison-Wesley
    • “Data Structures with C++ using STL”, by William Ford and William Topp. Publisher: Prentice Hall.
    • “Absolute C++”, by Walter Savitch, 3rd Edition. Publisher: Addison Wesley
    • “The C++ Standard Library: A Tutorial and Reference”, by Nicolai M. Josuttis. Addison-Wesley.
    • “C++ How to Program”, by H. M. Deitel, and P. J. Deitel. Publisher: Prentice Hall.
    • “Introduction to Algorithms”, by Cormen, Leiserson, and Rivest, Publisher: MIT press and McGraw-Hill Book Company

Course Contents

The course outline will closely follow the material presented in book by Mark Allen Weiss. We will cover chapters 1–7 in detail and other chapters in any remaining extra time.