Course Goals, Required Background and Potential Topics
for CSCI 2341 and CSCI 2342

Before starting any course, or course sequence, it is a good idea to have an overview of the goals you are expected to achieve and the topics to be covered in pursuit of those goals, as well as what you are expected to know in preparation for the work to be undertaken.

Course Goals

The overall goal of the two-course sequence comprised of CSCI 2341 and its sequel CSCI 2342 can be broadly expressed as follows: to help you review, consolidate and extend your ability to solve certain kinds of problems whose solutions may be implemented as computer programs, and to help you learn how to evaluate alternative solutions to such problems. Currently the major tool used in the implementation of these solutions is the C++ programming language.

In particular, you will have an opportunity, and you should make it your goal, to:

• Review and extend your knowledge of some useful mathematics
• Review, refine and extend your catalog of problem-solving approaches, techniques, strategies and "best practices"
• Review and extend both your personal "algorithm toolkit" and your knowledge of data structures, and also
  • Learn how to compare algorithms and develop some criteria for choosing the "best" one to perform a given task
  • Learn how to compare data structures and develop some criteria for choosing the "best" one to model a given real world entity
• Review and extend your knowledge of
  • The C++ programming language
  • Your current C++ programming environment (the one used for this course)
  • C++ programming style
    You may need to adjust your own programming style as necessary to conform to the conventions required for programming in this course, and you will be expected to develop an appreciation, if you don't have it already, for the close connection between being able to use a good, consistent coding style and being able to think clearly about any program you happen to be writing.
• Review and extend your knowledge of program development in general, and C++ program development in particular, including this principle:
  Import what you need if possible; implement it only if necessary (or if required by your instructor!).

Required Background

To achieve the above goals, you must begin with a certain level of skill and knowledge, which you are assumed to have obtained in prior courses. A summary of what is assumed is given in Expectations: Presumed Student Background, where you will find descriptions of what you are expected to know in the following areas:

• Your Mathematical Knowledge
• Your Problem Solving Knowledge and Skills
• Your Required Personal Algorithm Toolkit
• Your Required C++ Programming Language Knowledge (and see the following)
  • Our C++ Programming Style Conventions (that we will treat as rules)
  • Some C++ Code Examples (illustrating both style and substance)
• Your Program Development Skills

Potential Topics

The topics that appear under the headings in the Potential Topic List given below contain much more material than can be covered even in two complete single-semester courses. Thus many of the listed topics will not be covered, but most of the content of both CSCI 2341 and CSCI 2342 will be taken from the remaining material. The occasional topic may be added to the list later during either course. Just which topics are covered in each of the courses will evolve somewhat as each course proceeds, and will vary from year to year. It is reasonable to assume that pretty much anything covered in either CSCI 2341 or CSCI 2342 will fall under one or another of the eight general headings in this Topic List, but do not be intimidated by the amount of material since not all of it will be covered. One of the reasons for presenting this superset of topics to be covered is to give you a sense of some of the other material of interest in the areas you will be studying.

Potential Topic List

Miscellaneous Mathematical Tools

• Interval notation (middle value of an interval, number of values in an interval)
• Σ and Π notation; sums and products, and some basic rules for finding and manipulating them
• Elementary functions: polynomial, exponential and logarithmic
• Floor and ceiling functions and their uses
• Relative growth of functions and "order"
• Estimation of upper and lower bounds
• Methods of proof
  • direct methods
  • indirect methods
  • special techniques, such as mathematical induction
• Pseudorandom numbers and generators
• Recursion
• Recurrence relations
• Partial orders
• Units of measure
• Elementary probability

Algorithm Analysis

• Same problem solved by different algorithms should result in same solution
• The importance of developing efficient algorithms
• Factors affecting the time taken by a computer to solve a problem
• How we measure efficiency and compare algorithms
• Computational and asymptotic complexity
• Asymptotic notation, measures and rules of operation
• Best, worst and average case analysis
• Costs, benefits and tradeoffs
• Time complexity vs. space complexity: the time/space trade-off
• Input classes and the effect of data organization
• Computational complexity and intractability
• Amortized analysis

Algorithm Design and Classification

• Definition and properties of an algorithm
• Goals of algorithm design: correctness, readability, efficiency
• General (problem independent) guidelines for algorithm design
• Classification of problems (and some relevant algorithms)
  • Searching
    • linear search
    • binary search
    • searching in lists (possibly including self-organizing lists)
    • searching in trees (including tree balancing)
    • searching in hash tables
    • searching in sets
    • searching in maps
  • Sorting
    • quadratic sorts (selection, insertion, bubble)
    • faster sorts (quicksort, mergesort, heapsort, shellsort, treesort)
    • sorting by distribution: binsort and radix sort
    • indirect sorting using indexes to the elements
    • topological sorting
  • Graph and Tree Traversal
    • expression trees and their evaluation
    • depth-first
    • breadth-first
    • transitive closures (Warshall)
  • Optimizing
    • greedy methods
    • branch and bound
    • shortest path (Dijkstra, Floyd)
    • minimum spanning tree (Kruskal, Prim)
  • Indexing
    • linear indexing
    • tree indexing
  • Problems involving randomization
    • random data generation
    • simulation
    • Monte Carlo methods
    • optimization by simulated annealing
  • Algorithm profiling
  • Recreational algorithms (game-playing)
  • Numerical approximation and other numerical algorithms
  • Pattern matching and other string/text algorithms
  • Cryptographic algorithms (including steganography and digital signatures)
  • Data compression algorithms
  • Memory management algorithms
  • Geometric algorithms
  • Distributed algorithms
  • Parallel algorithms
  • Genetic algorithms
  • Many others (just in case you thought the above list was exhaustive)
• Another classification of algorithms
  (see Anany Levitin, A New Road Map of Algorithm Design Techniques,
  Dr. Dobbs Journal, April 2000, pp. 23-28)
  • Brute Force
    • Most general: exhaustive search
    • Less general: local search techniques such as
      greedy methods, or
      improvement methods
  • Divide-and-Conquer
    • Most general:
      divide before processing, or
      process before dividing
    • Less general: dynamic programming via a
      bottom-up approach, or
      top-down approach
  • Decrease-and-Conquer
    • Most general: decrease by
      a constant
      a constant factor
      a variable amount
    • Less general: state-space-tree techniques such as
      backtracking, or
      branch-and-bound (and other heuristics)
  • Transform-and-Conquer
    • Most general:
      instance simplification
      representation change
      preconditioning
      transformation to a different problem
  • Miscellaneous (just to emphasize that the above categories are not all-inclusive)
    • Some algorithms are based solely on insights specific to the problem they solve.
    • Some algorithms may be regarded as examples of more than one of the above categories.
    • Some algorithms may incorporate several of these different approaches.
• The STL and the library of algorithms in <algorithm>

Data Types, Abstract Data Types, and Data Structures

• Terminology: value or data item, type, data type, abstract data type, data structure
• Guidelines for choosing a data structure and its associated algorithms
• Containers
  • The stack
  • The queue and the deque
  • The priority queue
  • The tree
  • The graph and the digraph
• Searchable Containers
  • The vector
  • The list
  • The search tree
  • The hash table
  • The heap
  • The set and the multiset
  • The map and the multimap
• The STL Containers in C++

New C++ Features

• Command-line parameters
• Passing functions as parameters
• More on C-strings and the C++ string class
• More on pointers, dynamic data storage and linked structures
• More on text I/O: mainipulators and formatting flags, appending to a textfile
• Binary files (for unformatted I/O): opening, reading, writing, appending and random access
• More on const (re pointers in particular) and static
• More on operators and overloading
• More on template functions and template classes
• More on scope, namespaces, lifetime, storage classes, and linkage
• More on inheritance, composition and other class relationships
• More on virtual functions and polymorphism
• Abstract classes and pure virtual functions
• Multiple inheritance, virtual base classes, and virtual inheritance
• Up-casting and down-casting of class objects
• Exceptions and exception classes
• RTTI (Run Time Type Identification)
• Debugging and profiling techniques
• The STL

New Programming Environment Features

• Command-line compiling, linking and running
• Environment variables and placement of utility code
• More on the Visual C++ IDE (Integrated Development Environment)
• Introduction to GUI programming
• Use of Doxygen for source code documentation
• Use of CVS or Subversion for source code control and revision
• Use of Visual Studio macros for C++ programming
• Creating DLLs in Visual Studio
• Deploying programs from Visual Studio

More on Program Design and Development

• APIs (Application Programming Interfaces)
• Utility code:
  - the DisplayIDInfo free function
  - the DisplayTextfile free function
  - the Pause free function
  - the Read* free functions for getting values of various basic types from the user
  - the UserSaysYes free function
  - the Menu class
  - the OperationCounter class
  - the RandomGenerator class
  - the Stopwatch class
  - the TextItems class
  
• Scaffolding, assertions, and exceptions for error processing
• The object-oriented approach vs. the structured (procedural) approach
• Encapsulation and information hiding
• Inheritance vs. composition, and other class relationships
• Introduction to the UML (Unified Modeling Language)
• Design Patterns