San Jose State University : Site Name

Navigation

Main Content

Working in Mars Mission Control, JPL

Ronald Mak

Department of Computer Engineering
Department of Computer Science
Department of Applied Data Science
Spring Semester 2020

Office hours: TuTh: 4:30-5:30 PM
Office location: ENG 250
E-mail: ron.mak@sjsu.edu
Mission Control, Jet Propulsion Laboratory (JPL)
NASA Mars Exploration Rover Mission

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


Section 2: Tu 6:00 - 8:45 PM, room ENG 337


Assignments


# Assigned Due Assignment
1 Jan 28 Feb 4 Watering Plans

Input file: counts.txt
Sample solution: WateringPlans.cpp
2 Feb 4 Feb 11 The Monty Hall Problem

Sample solution: MontyHall.cpp
3 Feb 11 Feb 18 War and Peace

Input file: WarAndPeace.txt

Test string::npos: NposTest.cpp
Test string trim: TrimTest.cpp
Sample solutions: WarAndPeace-NoNameSplits.cpp    WarAndPeace.cpp
See: online string reference
4 Feb 18 Feb 25 Student Scores

Input file: students.txt
Sample solution (two versions): students.cpp    students-typedef.cpp    output.txt
5 Feb 25 Mar 3 Roman Numerals

Input file: RomanNumeral.txt
Sample solution: RomanNumeral.h    RomanNumeral.cpp    RomanNumeralTests.cpp
6 Mar 1 Mar 8 Book Catalog

Input file: commands.in
Expected output: output.txt
Sample solution: Book.h    Book.cpp    BookApp.cpp
7 Mar 10 Mar 24 U.S. maps

Input files: boundary-data.csv   city-data.csv
Sample solution: Assignment7Solution.zip
9 Mar 24 Apr 7 Big Pi

Sample solution: Assignment9Solution.zip
10 Apr 7 Apr 14 STL Vector and List

Sample solution: Assignment10Solution.zip
11 Apr 14 Apr 21 U.S. Constitution

Input file: USConstitution.txt
Sample solution: Assignment11Solution.zip
12 Apr 21 Apr 26 Sorting Algorithms

Sample solution: Assignment12Solution.zip
13 Apr 27 May 3 BST and AVL trees

Expected output for Part 1: Part1-output.txt
Sample graphs for Part 2: Part2-graphs.pdf
Sample solutions: Assignment13-1Solution.zip    Assignment13-2Solution.zip


Lectures


Week Date Content
1 Jan 28 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   nestedloop.cpp   Savitch_01-08.cpp   Savitch_03-06.cpp   Savitch_03-14.cpp
2 Feb 4 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

Savitch slides: 04 05
Top-down design example:
translator1.cpp   translator2.cpp   translator3.cpp   translator4.cpp   translator5.cpp
Pass by value example: swap.cpp
Pass by reference example: exchange.cpp
Assert example: assert.cpp
3 Feb 11 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; multidimensional arrays; C strings; the standard string class; vectors; Assignment #3: War and Peace

Savitch slides: 06 07 08
4 Feb 18 Slides: Assignment #3 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; use typedef; using pointers to pass-by-reference; pointers and arrays; pointer arithmetic; dynamic arrays; 2-D dynamic array; use typedefs; char* and char**; Assignment #4: Student Scores

Savitch slides: 09
Dynamic array examples: DynamicArray1.cpp   DynamicArray2.cpp   DynamicArray3.cpp
5 Feb 25 Slides: Assignment #4 sample solution; 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 Roman Numerals

Savitch slides: 10 11
Example classes: Birthday1.cpp   Birthday2.cpp   Birthday3.zip
6 Mar 3 Slides: Assignment #5 sample solution; static class members; destructors; array of objects; vector of objects; copy constructor; "extra" constructor and destructor calls; how a vector grows; namespaces; search an array: linear search and binary search; Assignment #6 Book Catalog

Savitch slides: 12
Example classes: Birthday4.zip   Birthday5.zip   BirthdayArray.zip   BirthdayVector.zip   BirthdayCopyCtor.zip   BinarySearchIterative.cpp
7 Mar 10 Video recording
Slides: Assignment #6 sample solution; a "safe" array type; assignment operator; overload the subscript operator []; copy constructor; the "big three"; linked list insertion and deletion; queue; stack; Assignment #7

Savitch slides: 13
SafeArray example 1: (crashes) 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 (another fix operator =): SafeArray4.h   SafeArray4.cpp   SafeArrayTests4.cpp
SafeArray example 5 (overload []): SafeArray5.h   SafeArray5.cpp   SafeArrayTests5.cpp
SafeArray example 6 (copy constructor): SafeArray6.h   SafeArray6.cpp   SafeArrayTests6.cpp
8 Mar 17 Video recording
Slides: Midterm; template function; template class "safe array" version 7; object-oriented programming; inheritance; subclasses; polymorphism; virtual destructors

Savitch slides: 15
Template function example: TemplateExchange.cpp
Template class example: Pair.h   PairTests.cpp
SafeArray example 7 (template): SafeArray7.zip
Virtual destructors: VirtualDestructor1.zip   VirtualDestructor2.zip
9 Mar 24 Video recording
Slides: Midterm solutions; Assignment #7 sample solution; calculation puzzle; chrono; auto; decltype; Assignment #9; exception handling; exception classes; throwing exceptions in a function; review of iteration; recursion; think recursively; recursive examples: factorials, multiplication, Fibonacci (iterative and recursive), member of, unique, reverse, Towers of Hanoi; recursive binary search; mergesort

Savitch slides: 14 16
Malik slides: 06
Calculation puzzle: roundoff.cpp
Exception handling examples: exception1.cpp   exception2.cpp   exception3.cpp
Timed vector examples: TimeVector1.cpp   TimeVector2.cpp
Recursion examples: Factorial.cpp   Multiply.cpp   Fibonacci1.cpp   Fibonacci2.cpp   Fibonacci3.cpp   MemberOf.cpp   Unique.cpp   Reverse.cpp   Permutations.cpp   Hanoi.cpp   BinarySearchRecursive.cpp
10 Apr 7 Video recording
Slides: Pointer to a function; Assignment #9 suggested solution; binary search: iterative and recursive; Towers of Hanoi; mergesort; the Standard Template Library (STL); iterators; containers; STL list template class; Assignment #10

Sample programs: FunctionParm1.cpp   FunctionParm2.cpp
11 Apr 14 Video recording Password M9.N#3G^
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; Assignment #11

Malik slides: 09
12 Apr 21 Video recording Password 3N@UEb82
Slides: Nasty C++ puzzle; 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; sorting animations; Assignment #12

Malik slides: 10
Nasty C++ puzzle: Thing.h   Thing.cpp   IteratorEndTest.cpp
13 Apr 28 Video recording Password 2u%42+C4
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
14 May 5 Video recording Password 8P^+YH95
Slides: Assignment #13 solution; 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; function definitions in header files; inline keyword; more modern C++ features

Savitch slides: 17 18
Malik slides: 12
Inline examples: Inline1.h   InlineTest1.cpp   Inline2.h   InlineTest2.cpp   InlineTest3.cpp

Goals


CMPE 180A is an introduction to data structures and algorithm design with C++. The course emphasizes important data structures, such as linked lists, stacks, queues, hash tables, trees, and graphs. It also introduces recursive algorithm design and algorithm analysis techniques. 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


Department policy is to enforce
all course prerequisites strictly

Admission into the CMPE or SE masters program.


Required books


Problem Solving with C++, 10th edition
Walter Savitch
Pearson, 2017
ISBN: 978-0134710747
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 an integrated development environments (IDE) such as Eclipse 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 not use Microsoft Visual C++, or you run the risk of writing programs that will not port to other platforms. Windows users should install Ubuntu.