Course Notes for (C++ Versions of) CSCI 2341 and 2342

The first link below takes you to a subdirectory containing the PowerPoint slides from each chapter of the Carrano text. The other (annotated) links take you to notes on various topics discussed in class, and possibly other (ancillary) material as well. Items appear in chronological order, but there may be lectures with no corresponding notes here, and some notes here may have been discussed only briefly, or not at all, in the lectures. In short, although these notes should be regarded as a core part of the course, they must not in any way be regarded as a complete summary of what you should know in the course. The sample code, the text, and your work on the weekly submissions, all comprise essential parts of the course. Consult the Course Outline if you are in doubt as to what has been covered, or in what order. Most of the links here will be to standard HTML pages. Other possibilities include plain ASCII text files, which will be marked by an "ASCII" designation, and Microsoft Word files, which are indicated by "MSWord". Your browser will have to know how to deal with these files, or, alternatively, they can first be downloaded, and then subsequently viewed with an appropriate standalone application.

Empirical Algorithm Analysis Data (worksheet) This is a Microsoft Word document that provides a worksheet for recording data pertaining to the running of an algorithm on data sets of various sizes.

1. Instructor-Supplied Utilities Package The utilities available from this package are designed to save you time and energy during the development of your programs. You will be using these utilities throughout this course and the next. So, you should begin to familiarize yourself with the package immediately, and continue to explore it as the need for each the various features it offers arises.
2. From Java to C++ A list of "talking points" and external references for our discussion of the similarities and differences between C++ and Java.
3. Command-Line Parameters The use of command-line parameters provides a convenient mechanism for the programmer to let the user enter information from the "outside world" into a program as the program begins to run.
4. Namespaces The "namespace" concept was introduced to C++ to help alleviate the growing problem of "global namespace pollution" and to help deal with the increasing difficulties caused by different programmers placing things with the same name into the global namespace.
5. Scope The scope of an identifier is an important concept in any programming language, and deals with the region in a program where that identifier can be used. It takes on even greater importance when a program is split into multiple files.
6. Types, Data Types, ADTs, Data Structures, and APIs The notion of type is a key concept in computing science. In particular, the idea of an Abstract Data Type (ADT) forms the foundation for all programmer-defined types that are used to represent real-world entities. And Application Programming Interfaces (APIs) are the public operations provided so that "client programmers" can use implementations of Abstract Data Types in their programs.
7. Classes and Objects in C++ Some discussion of classes and objects in the context of C++.
8. Random Numbers and Generators [MSWord] Random values (or more accurately, pseudorandom values) are very important in computing for such purposes as generating random data input and simulating real-world activities.
9. Storage Classes and Linkage The storage class of a variable or object has to do with the "lifetime" of the variable or object, while the "linkage" of a variable or object has to do with the accessibility, from a given file, of a variable or object defined in another file.
10. Exceptions C++, like most modern programming languages, provides an exception-handling mechanism to recognize "exceptional" situations (errors) and deal with them more elegantly than the time-honored if..else approach.
11. Basic Pointer Concepts Every C++ programmer needs to know something about pointers. This page provides a summary of the basic pointer notions, but does not deal with linked structures.
12. Linked Nodes Data structures formed by the "linking" of "nodes" together in various configurations are very important in programming. This page discusses the general idea, and and in particular the idea of a sequence of nodes linked by a single link field (also called a "linked list" or a "chain").
13. Template Functions and Template Classes Template functions are functions that perform the same action(s) on different kinds of data. Template classes are classes that can store different kinds of data and permit the same actions on that data, no matter what kind of data it is.
14. The Standard Template Library (STL) This very new and very powerful part of C++ needs to be a part of every C++ programmer's repertoire of tools. This web site contains a growing, but still very incomplete, STL reference, which you will nevertheless find it helpful to consult as we continue. This link takes you to the index page for that part of the site.
15. The vector Abstract Data Type (ADTVector) The vector ADT is a very useful "container class" that emulates, in many ways, the behavior of an array, but is much more versatile and powerful. Once you've seen vectors, you'll find yourself using arrays less and less often.
16. The deque Abstract Data Type (ADTDeque) The deque ADT is one of the three "sequential" container classes in the STL. The other two are the vector and the list. The deque is a "double-ended queue", which means that it provides easy access for both insertion and deletion at both ends of the container (i.e., at the "front" as well as at the "back").
17. The list Abstract Data Type (ADTList) The list ADT is one of the three "sequential" container classes in the STL. The other two are the vector and the deque. The list emulates (and is meant to emulate) the kinds of lists humans use on a daily basis.
18. Algorithms, Design Goals, Pseudocode and Implementations An algorithm describes "how to do it" in any situation where something needs to be done, and implementing algorithms in a programming language are what computer programming is all about.
19. Mathematical Background for Algorithm Analysis You may need to be reminded of (or introduced to) a few mathematical concepts and some conventional notation before we begin to examine the basic ideas of algorithm analysis.
20. Algorithm Analysis: An Overview Algorithm analysis gives us a way to evaluate the potential performance of an algorithm we may wish to use, and also a way to compare it with other algorithms that might alternately be used to perform the same task. Being able to choose the "best" algorithm for a given situation on the basis of such evaluations is an important skill for any programmer to have.
21. The Linear Search Algorithm This is one of the simplest algorithms in the computer scientist's toolkit. And yet even it is subject to incorrect implementations by careless programmers. It requires no assumptions about the data values being searched.
22. The Binary Search Algorithm This is a very fast searching algorithm (compared to linear search) but can only be performed on data that satisfies the (rather severe) restriction of being sorted prior to the application of the binary search algorithm. Also, though simple in concept, it is a difficult algorithm to implement correctly.
23. Sorting: An Overview A few comments on sorting in general, and some common assumptions (or conventions) for sorting algorithms.
24. The Selection Sort Algorithm This is a quadratic-time sorting algorithm that works by maintaining a sorted subsequence and selecting, on each pass, from the remaining unsorted values, the largest or smallest remaining element, depending on how the algorithm is being implemented, and putting that element in its proper location.
25. The Insertion Sort Algorithm This is a quadratic-time sorting algorithm that works by maintaining a sorted list while taking, at each step, the next value (whatever it might be) from the remaining unsorted values, and inserting that value into its proper place in the sorted list.
26. The Bubble Sort Algorithm This is a quadratic-time sorting algorithm that works by continuing to make passes over the sequence of values, or a subset of the sequence, checking adjacent pairs of values and exchanging those pairs that are "out of order", until the list is sorted.
27. The Shell Sort Algorithm This is a sorting algorithm whose complexity still defies a precise analysis. It is nevertheless a fast sort, uses insertion sort in an "intimate" way, and is based on iteration, not recursion.
28. The stack Abstract Data Type (ADTStack) The stack ADT provides a LIFO (Last-In First-Out) structure.
29. The queue Abstract Data Type (ADTQueue) The queue ADT provides a FIFO (First-In First-Out) structure.
30. Recursive Sorts: An Overview One view of recursive sorting is as a specialization of general divide-and-conquer sorting. Applying a recursive approach to the problem of sorting a sequence leads to the development of several sorting algorithms whose performance is better than that of the quadratic sorts. The performance of these sorts turns out to be O(n*log n), which is also the "best" we can get for the kinds of comparison-and-exchange based sorts we are considering.
31. The Merge Sort Algorithm This is a O(n*log n) sorting algorithm that works by recursively splitting a sequence into two subsequences, sorting each subsequence, and merging the two sorted subsequences together to obtain the sorted form of the original sequence.
32. The Quick Sort Algorithm This is a O(n*log n) sorting algorithm that works by choosing one of the values of the sequence (called the pivot), then placing the values less than the pivot below the pivot and those values greater than or equal to the pivot above the pivot, and then repeating this action (recursively) on those two groups of values.
33. The map Abstract Data Type (ADTMap) The map ADT is one of the four "associative" container classes in the STL. The closely related multimap, and the set and multiset are the other three. Maps allow efficient storage of key/value pairs with unique keys, while multimaps permit duplicate keys.
34. The set Abstract Data Type (ADTSet) The set ADT is one of the four "associative" container classes in the STL. The closely related multiset, and the map and multimap are the other three. Sets allow efficient storage of ordered data in which the elements are unique, while multisets permit duplicate elements.
35. Trees The tree data structure turns out to be a very useful one in many different contexts, particularly the binary tree data structure. Unfortunately, however, the STL does not yet provide us with an off-the-shelf tree container. So, any trees we want we will have to implement ourselves.
36. Answers to Binary Tree Questions Answers to the questions on binary trees posed at the end of the "Trees" page above.
37. The Union Data Structure The union data structure may be useful when we wish to use the same storage space for different kinds of data (at different times), or to use different instances of the same data structure to store different kinds of data simultaneously.
38. String Streams String streams provide objects in memory to which data can be written, or from which data can be read, using the usual syntax for stream input/output. Such data is usually being examined or manipulated for some purpose on its way to another destination.
39. Regular Expressions Regular expressions are something with which every computing science student should eventually become familiar. They are available in many of the modern programming languages used for software development (now including C++11), and particularly in scripting languages used in web development.
40. Binary Expression Trees The binary expression tree (a special kind of binary tree) is very useful when programs (like compilers) have to deal with storing and evaluating arithmetic or other expressions.
41. The Binary Search Tree Abstract Data Type (ADTBinarySearchTree) The ADTBinarySearchTree is one that we will have to develop ourselves, since (unlike so many of the other standard containers) it is not available to us directly via the STL.
42. Building a Binary Search Tree Template Class The STL does not provide us with a binary search tree container, so we need to build one of our own.
43. Heaps The heap is another special kind of binary tree, with a "shape property" and an "order property".
44. STL Heap Algorithms The STL does not provide us with a heap container, but it provides us with some useful algorithms for working with heaps stored in vectors.
45. The priority queue Abstract Data Type (ADTPriorityQueue) The priority queue ADT provides a structure into which elements may be entered in any order but which come out of the structure in an order determined by some kind of "priority" which will depend upon the application.
46. Hashing Hashing is another approach to storage and retrieval of data. It can provide very fast lookup performance, but has its own peculiar disadvantages. These include the possibility of excessive unused storage and the inability to provide all of the data in convenient and commonly desired forms, such as sorted order.
47. Performance Summary of Various Storage and Retrieval Methods A table showing the performance of the insert, delete and find operations for each of several storage and retrieval methods.
48. Stable Sorting Algorithms A stable sort is one that does not interchange elements with duplicate keys, which can be important when the same data is sorted more than one way.
49. Notes on Graphs A graph may be regarded as a generalization of the notion of a tree, and graphs, like trees, are very useful as models in computing science and elsewhere.
50. The Graph Abstract Data Type A typical ADT for a graph, one of the very useful structures, both in computing science and in modeling in general.
51. The Three Pillars of OOP Discussion of the "three pillars" of object oriented programming: encapsulation, inheritance and polymorphism.
52. Multiple Inheritance Discussion of multiple inheritance in C++, including the "deadly diamond of death", virtual base classes and virtual inheritance.
53. RunTime Type Identification Sometimes it is very convenient for the programmer to have a program examine, at runtime, the data type of a variable or object, and react accordingly.