Syllabus

Description: This course provides an introduction to the design and implementation of software for personal navigation systems. Specifically, it considers how principals of object-oriented design can be applied in this particular domain and the algorithms and data structures that are used when implementing such systems.

It is organized along the way in which these systems were developed over time. It begins with systems that display a map. It then moves on to systems that add a destination to the map. Next, it considers systems that add a route/path to the map. After that, it considers systems that add a raw location and a map-matched location to the map. Finally, it considers systems that incorporate real-time routing.

Textbook: There is no textbook for this course. Readings are available on the Internet.

Outline: This course is organized as follows (though specific topics and dates may change).

Readings are listed in the right-most column.

Topics to Understand Completely Before the First Meeting

OOP Basics

Classes , Enumerated Types , Exceptions , Specialization , Abstract Classes and Interfaces

Polymorphism

Through Inheritance and Through Interfaces

Input/Output (I/O)

File System Basics and I/O Basics

Reference Types

Objects and Arrays

Other OOP Topics

Packages , Parameterized Classes/Interfaces and Collections

ADTs

Data Structures and Algorithms

Part I: Background

1/22

About this Course

1/24

The Observer Pattern , The Strategy Pattern and The Model-View-Controller Pattern

1/27-1/29

Windowing Basics , Layout Basics , Intermediate Layout , Using GUI Components and Worker and Timer Threads

GUI and W&T Threads

1/31-2/3

An Introduction to Vector Arithmetic and Software Design Issues

2/5-2/7

An Introduction to Analytic Geometry and Software Design Issues

Part II: Computer Cartography

2/10-2/12

2D Graphics

Java 2D API

2/14

Cartography , Remote Sensing and Digitizing

2/17-2/21

Coordinate Systems: For \(\mathbb{R}^{2}\) , For \(\mathbb{R}^{3}\) and Software Design Issues

2/24-2/28

Geographic Coordinate Systems and Map Projections for a Spherical Planet

Part III: Geocoding

3/3

Geocoding: Introduction and Text Matching

Part IV: Static Routing

3/5

An Introduction to Graphs and Modeling Road Networks

3/7

Routing Algorithms

3/10-3/24

Data Structures: Graphs , Routing , Trees and Heaps

3/26

Exam 1

Part V: Location/Position Determination

3/28

Introduction

3/31

Animation Basics

4/2

History: Measuring Latitude and Measuring Longitude

4/4-4/7

Data Acquisition: Checksums , Communications Ports and Software Design Issues

4/9

Sensors and Dead Reckoning

4/11-4/16

The Global Positioning System , An Introduction to Triangulation , Triangulation Using Optimization: Part I and Part II

4/18-4/21

Partitioning Spatial Data: Introduction and Software Design Issues

4/23

Computational Geometry: Metrics , Euclidean Calculations and Great Circle Distances

4/25-4/28

Map Matching

4/30

Exam 2

Part VI: Real-Time Routing

5/2

Route Recalculation

5/5-5/7

No Lecture - Work on the Final Project

5/12

Project Presentations

Attendance at lectures is not mandatory but is strongly encouraged. You are expected to come to class prepared to ask and answer questions. Hence, you should complete the readings on a topic before it is discussed in lecture.

Grading: Final grades will be based on your performance on: 2 in-class exams (25% each) , several programming assignments (30% total) and 1 final project (20% total).

Programming Assignments: 6 programming assignments will be assigned during the semester. Note that their due dates are subject to change.

Programming Assignment 1 ; Due: 2/5 11:00PM (GUIs)
Programming Assignment 2 ; Due: 2/19 11:00PM (Vector Graphics)
Programming Assignment 3 ; Due: 3/5 11:00PM (Cartography)
Programming Assignment 4 ; Due: 3/24 11:00PM (Geocoding and Cartography)
Programming Assignment 5 ; Due: 4/2 11:00PM (Static Routing)
Programming Assignment 6 ; Due: 4/16 11:00PM (Location/Position Determination)

Make sure you read and understand all of the policies related to programming assignments.

Individual/Group Project: Each student must complete a project. Make sure you read and understand all of the policies related to projects.

Office Hours: You may meet (either face-to-face or virtually, depending on the situation and schedule) with Prof. Bernstein during his scheduled office hours or you may schedule an appointment with him.

Contact Information: Prof. Bernstein's contact information is available on the contact page of his WWW site.