Syllabus

Description: This course provides an introduction to the design and implementation of software for personal navigation systems. Specifically, it considers how prinicpals 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.

Part I: Background

1/22

About this Course

1/24

Review of Data Structures and Algorithms

Algorithms

1/27-1/31

Graphical User Interfaces: The Observer Pattern , GUI Basics NEEDS WORK!!!! and Threads

2/3-2/5

Vector Arithmetic: Introduction and Software Design Issues

2/7-2/10

Analytic Geometry: Introduction and Software Design Issues

Part II: Computer Cartography

2/12

Cartography , Remote Sensing and Digitizing

2/14-2/19

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

2/21-2/26

Geographic Coordinate Systems and Map Projections for a Spherical Planet

2/28-3/3

USE THIS??? Vector Graphics and OR THIS THIS??? Vector Graphics

Part III: Geocoding

3/5

Geocoding: Introduction and Text Matching

Part IV: Static Routing

3/7

An Introduction to Graphs and Modeling Road Networks

3/10

Routing Algorithms

3/12-3/26

Data Structures: Graphs , Routing , Trees and Heaps

3/28

Exam 1

Part V: Location/Position Determination

3/31

Introduction

4/2

Animation Basics

4/4

History: Measuring Latitude and Measuring Longitude

4/7-4/9

Data Acquisition: Checksums , Communications Ports and Software Design Issues

4/11

Sensors and Dead Reckoning

4/14-4/18

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

4/21-4/23

Partitioning Spatial Data: Introduction and Software Design Issues

4/25

Computational Geometry: Metrics , Euclidean Calculations and Great Circle Distances

4/28-4/30

Map Matching

5/2

Exam 2

Part VI: Real-Time Routing

5/5

Route Recalculation

5/7

??????

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) , 1 final exam (25% total) and several programming assignments (25% total).

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

Programming Assignment 1 ; Due: 1/28 (Review)
Programming Assignment 2 ; Due: 2/16 (Maps)
Programming Assignment 3 ; Due: 3/16(Extended to 3/18) (Location/Position Determination)
Programming Assignment 4 ; Due: 4/6(Extended to 4/11) (Static Routing)
Programming Assignment 5 ; Due: 4/25(Extended to 4/29) (Real-Time Routing)

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

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.