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.
There will not be time to cover all of the topics listed here but
a student should expect to see a large subset of them.
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 will be the Java programming language (exclusively) in CSCI
2341, while in CSCI 2342 there may be continuation of Java, a switch
to C++, or some mixture of the two.
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 programming language used to implement problem solurions
in the course you are taking
- Your current programming language environment (the one used for
the course you are taking)
- The required programming style
You may need to adjust your own programming style as
necessary to conform to the conventions required for programming
in these courses, 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 in particular program development using the programming
language of choice, including this principle:
Use "off-the-shelf" software for what you need whenever 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 Programming Language Knowledge (and see the following)
- Our Programming Style Conventions (that we will treat as
rules)
- 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
- 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
Back to Topic List
- 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
Back to Topic List
- 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.
Back to Topic List
- Terminology: value or data item, type, data type, abstract data
type, data structure
- Guidelines for choosing a data structure and its associated
algorithms
-
Containers
- Stacks
- Queues
- Deques
- Priority Queues
- Heaps
- Trees
- Graphs
-
Searchable Containers
- Vectors
- Lists
- Search Trees
- Hash Tables
- Sets and Multisets
- Maps and Multimaps
- The STL Containers in C++ and Java's generic container classes,
with the associated algorithms
Back to Topic List
- Command-line parameters
- Parameter passing mechanisms for both data and functions
- Strings and string classes
- Dynamic data storage and linked structures
- I/O: standard, text and binary files
- Operators and overloading
- Generic programming
- Scope and lifetime
- Interfaces and abstract classes
- Casting, particularly of class objects
- Exceptions and exception classes
- RTTI (Run Time Type Identification)
- Debugging and profiling techniques
Back to Topic List
- Working at the command-line
- Using utility programs, configuration files and environment variables
- Editors vs. IDEs (Integrated Development Environments)
- Tools for source code documentation
- Tools for source code version control
- Deploying programs
- GUI programming
Back to Topic List
- APIs (Application Programming Interfaces)
- Scaffolding, assertions, and exceptions for error processing
- The object-oriented approach vs. the structured (procedural)
approach vs. the functional approach
- Encapsulation and information hiding
- Inheritance vs. composition, and other class relationships
- Introduction to the UML (Unified Modeling Language)
- Design Patterns
Back to Topic List