San Jose State University : Site Name

Navigation

Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Fall Semester 2017

Office hours: TuTh: 3:00-4:00 PM
Office location: ENG 250
E-mail: ron.mak@sjsu.edu
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


Zachary Zhong
Monday 3:00-5:00 PM, room E405
Venkat Raja Iyer
Tuesday 1:00-3:00 PM, room E405
Amit Chougule
Wednesday 3:00-5:00 PM, room E405

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





Assignments


# Assigned Due Assignment
1 Aug 24 Aug 31 Watering Plans
Input file: counts.txt

Sample solution: WateringPlans.cpp
2 Aug 31 Sep 7 Functional Decomposition
Input file: counts.txt

Sample solution: WateringPlans.cpp
3.a Sep 7 Sep 14 Prime Numbers

Sample solution: primes.cpp
3.b Sep 7 Sep 14 Spirals

Sample solution: spirals.cpp
3.c Sep 7 Sep 14 Prime Spirals

Sample solution: PrimeSpirals.cpp
4 Sep 14 Sep 21 Big Pi

Sample solution: BigPiNonic.cpp
Extra credit: BigPiNonicMillion.cpp
One million digits of pi: BigPiNonicMillion.txt
Compare to: https://www.exploratorium.edu/pi/numbers-of-pi
5 Sep 21 Sep 28 Roman Numerals

Sample solution: RomanNumeral.h    RomanNumeral.cpp    RomanNumeralTests.cpp
6 Sep 28 Oct 5 Book Catalog
Input file: commands.in
Expected output: output.txt

Sample solution: Book.h    Book.cpp    BookApp.cpp
7 Oct 7 Oct 19 Book Lists
Input files: categories.txt    childrens.txt    history.txt    mystery.txt    science.txt
Expected output: output.txt

Sample solution: BookNode.h    BookNode.cpp    Book.h    Book.cpp    BookList.h    BookList.cpp    BookListsApp.cpp
9 Oct 20 Oct 26 STL Vector and List
Expected output: output.txt
Expected extra credit output: outputx.txt

Sample solution: Node.h    Node.cpp    SortedVector.h    SortedVector.cpp    SortedList.h    SortedList.cpp    TestSuite.h    TestSuite.cpp    STLVectorList.cpp

Sample extra credit solution: Node.h    Node.cpp    SortedVector.h    SortedVector.cpp    SortedList.h    SortedList.cpp    TestSuite.h    TestSuite.cpp    STLVectorList.cpp
Can you find the three minor changes?
10 Oct 26 Nov 2 Calculator

Sample solution (includes extra credit): Calculator.h    Calculator.cpp    CalculatorTester.cpp
11 Nov 4 Nov 9 STL Vector and Map
Input file: USConstitution.txt

Sample solution: Asgn11Solution.zip
12 Nov 10 Nov 16 Sorting Algorithms

Sample solution: Asgn12Solution.zip
13 Nov 18 Nov 30 BST and AVL Trees
Expected output (Part 1): output-1.txt


Lectures


Date Content
Aug 24 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
Aug 31 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 Functional Decomposition

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
Sep 7 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
Sep 14 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
Sep 21 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
Sep 28 Slides: Assignment #5 sample solution; array of objects; destructors; vector of objects; copy constructor; "extra" constructor and destructor calls; namespaces; how a vector grows; search an array: linear search and binary search; Assignment #6 Book Catalog

Savitch slides: 11 12
Example class Birthday v3: Birthday3.h   Birthday3.cpp   BirthdayTester3.cpp
Example class Birthday v4: Birthday4.h   Birthday4.cpp   BirthdayTester4.cpp
Example class Birthday v5: Birthday5.h   Birthday5.cpp   BirthdayTester5.cpp
Oct 5 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 17
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
Oct 12 Slides: Midterm; template function; template class "safe array" version 6; object-oriented programming; inheritance; subclasses; polymorphism; virtual destructors

Savitch slides: 15
Oct 19 Slides: Midterm solutions; Assignment #7 sample solution; exception handling; exception classes; throwing exceptions in a function; random numbers; chrono; timing execution; Standard Template Library (STL), iterators; vector iterator; kinds of iterators; containers; list template class; linked list vs. vector; Assignment #9;

Savitch slides: 16 17 18

Exception handling examples: exception1.cpp   exception2.cpp   exception3.cpp
Vector iterator examples: IteratorVector1.cpp   IteratorVector2.cpp
Elapsed time example: TimeVector.cpp
Oct 26 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: Queen.zip
Nov 2 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
Nov 9 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
Nov 16 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


Goals


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.


Prerequisites


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


GNU C++ is usually pre-installed on the Mac and Linux platforms. For those platforms, install one of the following integrated development environments (IDE) for C++ development:

Do not use Apple's Xcode on the Mac, or you run the risk of writing programs that will not port to other platforms.

On Windows, do run use Microsoft Visual C++, or you run the risk of writing programs that will not port to other platforms. Windows users should install VirtualBox and run Linux as a virtual machine. Debian is a good Linux distribution. Download a .iso installation image and install it VirtualBox. Run Debian on the virtual machine and use its pre-installed GNU C++ compiler. Then you can install Eclipse or NetBeans for Linux.