San Jose State University : Site Name


Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Spring Semester 2017

Office hours: Th: 2:30-4:30 PM
Office location: ENG 250
Mission Control, Jet Propulsion Laboratory (JPL)
NASA Mars Exploration Rover Mission

CMPE/SE 180-92: Data Structures and Algorithms in C++

Instructional Student Assistants
Weekly Tutoring Schedule

Saurabh Bhatkar
Monday 3:00-5:00 PM, room E405

Savio Fernandes
Tuesday 12:00-2:00 PM, room E206
Amit Chougule
Wednesday 2:00-4:00 PM, room E405

Th 6:00 - 8:45 PM, room ENG 189


# Assigned Due Assignment
1 Jan 26 Feb 2 Presidents
Input file:

Sample solution: presidents-draft.cpp    presidents.cpp
2 Feb 2 Sep 9 Rock Paper Scissors

Sample solution: rps.cpp
3.a Feb 9 Feb 16 Prime Numbers

Sample solution: primes.cpp
3.b Feb 9 Feb 16 Spirals

Sample solution: spirals.cpp
3.c Feb 9 Feb 16 Prime Spirals

Sample solution: PrimeSpirals.cpp
4 Feb 16 Feb 23 Big Pi

Sample solutions: BigPi.cpp    BigPiMillion.cpp
Sample output (one million digits with timings): You must compile with --std=c++11 to use the chrono timer package. BigPi-Debian.out
C++ library version: Run configure --enable-cxx to build the library extension for C++, and you must also #include <mpirxx.h>. Note that the arithmetic operators are now overloaded. BigPiCXX.cpp
5 Feb 23 Mar 2 Rational

Input file:
Sample solution: rational.cpp
6 Mar 2 Mar 9 Employee Records

Input file:
Sample solution: Employee.h    Employee.cpp    EmployeeApp.cpp
7 Mar 13 Mar 23 U.S. maps

Input files: boundary-data.csv   city-data.csv
Sample solution:
9 Mar 30 Apr 6 STL Vector and Linked List

Sample solution (extra credit):
10 Apr 8 Apr 13 Calculator

Sample solution (extra credit):
11 Apr 15 Apr 20 STL Vector and Map

Input file: USConstitution.txt
Sample solution:
Sample solution (extra credit):
12 Apr 22 Apr 27 Sorting algorithms

Sample output: output.txt
Sample solution:
13 Apr 28 May 4 BST and AVL trees

Expected output for Part 1: output.txt


Date Content
Jan 26 Slides: Course objectives; software to install; assignments; quizzes; exams; grading; what is C++; Hello World program; Pods and Peas program; identifier, variables, and keywords; assignment statements; input and output; #include and using namespace; formatting numbers; cin input; basic data types; string type; type compatibilities and conversions; arithmetic; operator shorthand; if statement; while loops; named constants; Boolean operators; precedence rules; enumeration types; nested if statements; switch statement; increment and decrement operators; for loops; break statement

Savitch slides: 01 02 03
Example programs: helloworld.cpp   Savitch_01-08.cpp   Savitch_03-06.cpp   Savitch_03-14.cpp
Feb 2 Slides: Predefined functions; random numbers; type casting; programmer-defined functions: declarations, definitions, calls; void functions; top-down design; number translator example; scope and local variables; block scope; global constants and variables; overloading function names; call-by-value; call-by-reference; procedural abstraction; testing and debugging functions; assert macro; Assignment #2 Rock Paper Scissors

Savitch slides: 04 05
Top-down design example:
int2words-1.cpp   int2words-2.cpp   int2words-3.cpp   int2words-4.cpp   int2words-5.cpp
Pass-by-value example: swap.cpp
Pass-by-reference example: exchange.cpp
Feb 9 Slides: Assignment #2 sample solution; streams; file I/O; stream name vs. file name; formatting output; output manipulators; passing streams to functions; character I/O; predefined character functions; eof function; arrays; array initialization; array function parameters; Assignment #3.a Prime Numbers; multidimensional arrays; Assignment #3.b. Spirals; C strings; the standard string class; vectors; Assignment #3.c. Prime Spirals

Savitch slides: 06 07 08
Feb 16 Slides: Assignment #3 solutions; sample solutions; pointers; int vs. pointer to int; declaring and assigning pointers; pointers are addresses; address-of and dereferencing operators; new and delete operators; pointer parameters; typedef; using pointers to pass-by-reference; pointers and arrays; pointer arithmetic; dynamic arrays; char* and char**; Assignment #4 Big Pi

Savitch slides: 09
Dynamic array example: DynamicArray.cpp
Feb 23 Slides: Assignment #4 sample solutions; structures; structures are types; scope of member names; structure variables; object-oriented programming (OOP); classes; member functions; public and private members; constructors; abstract data types (ADT); friend functions; operator overloading; overload <<; overload >>; Assignment #5 Rationals

Savitch slides: 10
Example class Birthday v1: Birthday1.cpp
Example class Birthday v2: Birthday2.cpp
Mar 2 Slides: Assignment #5 sample solution; array of objects; destructors; separate compilation; vector of objects; copy constructor; namespaces; search an array: linear search and binary search; Assignment #6 Employee Records

Savitch slides: 11 12
Example class Birthday v3: Birthday.h   Birthday3.cpp   BirthdayTester3.cpp
Example class Birthday v4: Birthday.h   Birthday4.cpp   BirthdayTester4.cpp
Example class Birthday v5: Birthday.h   Birthday5.cpp   BirthdayTester5.cpp
Mar 9 Slides: Assignment #6 sample solution; a "safe" array type; assignment operator; overload the subscript operator []; copy constructor; linked list insertion and deletion; queue; stack; Assignment #7; namespaces

Savitch slides: 13
SafeArray example 1: SafeArray1.h   SafeArray2.cpp   SafeArrayTests1.cpp
SafeArray example 2 (operator =): SafeArray2.h   SafeArray2.cpp   SafeArrayTests2.cpp
SafeArray example 3 (fix operator =): SafeArray3.h   SafeArray3.cpp   SafeArrayTests3.cpp
SafeArray example 4 (overload []): SafeArray4.h   SafeArray4.cpp   SafeArrayTests4.cpp
SafeArray example 5 (copy constructor): SafeArray5.h   SafeArray5.cpp   SafeArrayTests5.cpp
Mar 16 Slides: Shorthand for pointer expressions; a sorted linked list: searching, inserting, removing; inheritance; subclasses; polymorphism; virtual destructors

Savitch slides: 15
Mar 23 Slides: Midterm solutions; Assignment #7 sample solution; exception handling; exception classes; throwing exceptions in a function; templates; Standard Template Library (STL), iterators; vector iterator; kinds of iterators; containers; list template class; linked list vs. vector; Assignment #8; chrono

Savitch slides: 16 17 18

Midterm solutions

Exception handling examples: exception1.cpp   exception2.cpp   exception3.cpp
Vector iterator examples: IteratorVector1.cpp   IteratorVector2.cpp
Elapsed time example: TimeVector.cpp
Apr 6 Slides: Review of iteration; recursion; think recursively; recursive examples: factorials, multiplication, Fibonacci (iterative and recursive), member of, unique, reverse, Towers of Hanoi; linear search; binary search (iterative and recursive); queens problem; backtracking

Savitch slides: 14
Malik slides: 06
Recursion examples: Factorial.cpp   Multiply.cpp   Fibonacci1.cpp   Fibonacci2.cpp   Fibonacci3.cpp   MemberOf.cpp   Unique.cpp   Reverse.cpp   Hanoi.cpp   BinarySearchIterative.cpp   BinarySearchRecursive.cpp
Backtracking example:
Apr 13 Slides: Introduction to algorithm analysis; how well an algorithm scales; Towers of Hanoi puzzle recurrence relation; proofs by induction; big-O notation and its cousins; rates of growth; rules for computing running time; scalability of different algorithms; hash tables; hash function; collisions; keys for successful hashing; collision resolution; separate chaining; open addressing: linear probing and quadratic probing; load factor

Malik slides: 09
Apr 20 Slides: Sorting algorithms; selection sort; insertion sort; Shellsort; insertion sort vs. Shellsort; suboptimal and optimal Shellsort; mergesort for linked lists; analysis of mergesort; partitioning a list; partition using a pivot; quicksort; pivot strategy; suboptimal and optimal quicksort; median-of-three pivot strategy; Assignment #12; sorting animations

Malik slides: 10
Apr 27 Slides: Trees; implementation; traversals: preorder and postorder; binary trees; infix ==> postfix; binary search trees; inorder tree traversal; min and max; contains; insert; remove; AVL trees; balancing: cases 1 - 4; AVL tree implementation; Assignment #13

Malik slides: 11
May 4 Slides: Graphs: terms, examples, and representation; topological sort; unweighted shortest path algorithms; weighted least cost path; Dijkstra's algorithm; minimum spanning tree (MST); Prim's algorithm for MST; depth-first and breadth-first searches

Malik slides: 12
May 11 Slides: Assignment #13 solution; auto keyword; decltype pseudo-function; function definitions in header files; inline keyword; "The Big Three"; project phases; waterfall model; agile software development; requirements elicitation; bridging the gap; functional and nonfunctional requirements; what requirements must have; strong statements; how to get requirements; where to get classes; categories of classes; class responsibilities; class relationships: dependency, aggregation, inheritance; UML class diagram; UML sequence diagram; class diagram examples

"Big Three" examples: Array1.cpp   Array2.cpp   Array3.cpp


First goal: You will learn to design and write well-crafted programs in a useful subset of the C++ language.

Second goal: You will learn how to use C++ to implement some fundamental algorithms and data structures reliably and efficiently.

Learning to program well in a language like C++ requires much practice! You should expect to write one or more programs each week. The programming assignments will become increasing more challenging during the semester.


Admission into the CMPE or SE masters program.

Required books

Problem Solving with C++, 9th edition
Walter Savitch
Pearson, 2015
ISBN: 978-0133591743
Data Structures Using C++, 2nd edition
D.S. Malik
Cengage Learning, 2010
ISBN: 978-0324782011

Software to install

For the Mac, Linux, or Windows platform, install one of the following integrated development environments (IDE) for C++ development:

GNU C++ is usually pre-installed on the Mac and Linux platforms. On Windows, you must first download and install the GNU C++ compiler via Cygwin.

You can also use Apple's Xcode on the Mac, or Microsoft Visual C++ on Windows. But then you run the risk of writing programs that will not port to other platforms.

On Windows, you must first download and install GNU C++ via Cygwin. See:

Despite what the second video shows, do not use Notepad to edit your programs on Windows! Download and install Eclipse or NetBeans and use the IDE to edit, compile, and run your programs.

Do not install MinGW instead of Cygwin. MinGW in a minimum C++ installation that lacks many of the POSIX libraries required by some of the assignments.