Program Overview

Course Description

This course covers fundamental data structures and their use in programming, including both class design and features of the C++ programming language. Much of the discussion will be built around the design and use of the C++ standard library (STL). By using the standard library, students will be able to write reasonably sophisticated programs quickly.

Learning Outcomes

Students who have successfully completed this course will be able to:

• Demonstrate strong problem-solving skills in constructing complete C++ programs to tackle exercises inspired by real-world problems.
• Analyze the performance of algorithms and data structures.
• Select and use the most appropriate data structure from the C++ standard library (STL) for a particular programming task.
• Design and implement efficient customized data structures.

Prerequisites

The prerequisite for this course is a C- or better in RPI's CSCI 1100 Computer Science I, transfer credit of a course similar to CSCI 1100 from another university, or a 5 on the AP Computer Science A Exam. Students may contact the instructor for a waiver/override of this prerequisite if they believe they have sufficient preparation for the course through other experiences.

Assumed Prior Knowledge

Students are assumed to have learned the following concepts prior to taking CSCI 1200 Data Structures:

• Programming:
  • Arithmetic expressions, if/else statements
  • Writing your own functions, including:
    • Passing arguments to the function from the calling function
    • Reference variables (call by value vs. call by reference)
    • Returning a value from a function to the calling function
    • Scope and lifetime of variables, local vs. global variables
  • One and two-dimensional arrays and/or vectors
  • while and for loops, including nested loops
  • Reading data from files, and writing data to files
  • Some basic understanding and use of classes
    • Creating your own simple classes
    • Calling member functions
• Problem Solving: Given a problem, students should be able to design an algorithm or algorithms to solve the problem, and implement and debug an efficient solution. Examples include:
  • Count the number of times each letter appears in a file
  • Find the maximum value in an array or vector
  • Insert a new element into a sorted array in its correct place
  • Find the value closest to the average in a vector
  • Find the two closest values in a vector
• Algorithmic Concepts: Students should have seen and have a basic understanding of the following concepts:
  • Recursion
  • Run time analysis of algorithms (big O notation)
  • Elementary searching and sorting algorithms

Programming Languages

The language used in this course is C++, but students do not need to know C++ before taking this class. Transitioning a solid foundation in problem-solving, computational thinking, and implementation to a new programming language is an important skill for all computer scientists.

Course Warning

This course moves at a rapid pace and will likely be substantially more difficult than previous programming classes. The homework assignments are challenging, and students should start the assignments as soon as they are posted. Students should not get behind at any point in the semester and should work practice problems and study examples from lecture. Working with other students and working with tutors and TAs are both encouraged, but students need to be certain they understand the material and can do problems on their own.