Introduction
Introduction to programming, data structures, and algorithm design, using one or more modern imperative language, as chosen by the instructor.
Students will learn: basic programming constructs, data types, advanced and balanced search trees; hashing; asymptotic complexity analysis; standard algorithm design techniques; graph algorithms; sort algorithms; and other “classic’ algorithms that serve as examples of design techniques.
Students will be given regular programming assignments.
Student Comment
Text Books
Required
No textbook. Extensive instructor-produced course notes.
Syllabus
The syllabus below describes a recent offering of the course, but it may not be completely up to date. For current details about this course, please contact the course coordinator. Course coordinators are listed on the course listing for undergraduate courses and graduate courses.
Week-by-Week Schedule
| Week | Topics Covered | Reading | Assignments |
|---|---|---|---|
| 1 | variables and assignments, input and output, data types and expressions, simple flow of control, use and definition of classes, use and definition of functions, creation of simple classes, using the debugger, scalar data types, and casting | Lecture notes topic 1 | Get the compiler operational, build a simple application that casts numbers between data types |
| 2 | Multi-way branching, loop statements, designing loops, definition of a stream, file I/O, the freestore and the stack, variable scoping, basic const | Lecture notes topic 2 | REPL lab |
| 3 | call-by-value vs call-by-reference, name overloading, function templates | Lecture notes topic 3 | Write several functions that work together |
| 4 | Template classes, the C++ string class, abstraction, use of vectors, iterators, STL algorithms, lambda functions, exception handling | Lecture notes topic 4 | Tic-tac-toe part 1 assignment – build a rudimentary tic-tac-toe game, due in one week |
| 5 | Use of linked list, stacks, queues | Lecture notes topic 5 | Tic-tac-toe part 2, extend part 1 to handle a variable size board, number of players, change board geometry, or other changes, due in one week |
| 6 | Smart pointers, custom classes, inheritance and polymorphism, copy and move constructors, operator overloading | Lecture notes topic 6 | Date and time class lab; create a series of related types that contain information about dates and times and can be added together and otherwise manipulated |
| 7 | Implementation of linked list, stacks, and queues | Lecture notes topic 7 | Build an RPN calculator based on a stack, due in one week. Early milestone for RPN calculator – one operator and two operands. |
| 8 | Implementation of trees and binary trees | Lecture notes topic 8 | |
| 9 | Raw pointers, C arrays, C strings, pointer math, advanced const, heaps | Lecture notes topic 9 | Array class lab – build a wrapper around an array. Implementation of a vector class, due in two weeks. |
| 10 | Search trees, sorted sets vs hash sets | Lecture notes topic 10 | |
| 11 | Definition of graph, terminology, use cases, shortest path | Lecture notes topic 11 | Calculate shortest path between two nodes via code. Read in a digraph from a file, determine attributes of the graph (such as cyclic). |
| 12 | Graph search techniques such as mark and sweep | Lecture notes topic 12 | Implement mark and sweep to create a virtual reference counted environment, due in two weeks |
| 13 | Applications of graphs | Lecture notes topic 13 | |
| 14 | Survey of remaining STL, formal introduction of recursion | Lecture notes topic 14 | Final assignment, due in 4-6 weeks depending on semester finals schedule, covering all materials |