Syllabus

Description: This course considers both theortical and practical aspects of algorithms and data structures. Students learn to implement data structures and algorithms and to analyze algorithms (both in terms of their worst-case complexity and in terms of their "practical efficiency").

Textbook: The primary textbook for this course is:

Childs, J.S. (2008) C++ Classes and Data Structures, Pearson/Prentice Hall , Upper Saddle River, NJ.
(Order from amazon , order from Barnes and Noble , compare at bigwords , compare at CampusBooks4Less , order from Chegg , or search eFollett )

If you are unfamiliar with C++ then you should also consider acquiring either a textbook or a language reference.

You are expected to complete all reading assignments before the first day they are discussed in class.

Outline: This course is organized as follows, though specific topics and dates may change. (Readings are listed in the right-most column.)

Part I: An Introduction to C++

8/30

About CS240 and A Brief History of C++

9/1

An Introduction to Classes and Objects in C++

Ch. 1

9/3

Developing in C++

9/6

Lab: Skills: C++ Development Tools

9/8

Arrays

9/10

Arguments

9/13

Assignment 1 Due

9/15-9/17

I/O in C and C++

9/20-9/22

Operator Overloading , Exceptions and Templates

Ch. 2

9/24

More on Classes and Objects in C++

Ch. 3, 6

9/27

Assignment 2 Due

9/29-10/6

Pointers and References and Memory Allocation

Ch. 4

10/8

Exam 1

Part II: An Introduction to ADTs

10/11

ADTs and An Introduction to Stacks

Ch. 7 and Ch. 8.1-8.2

10/13-10/15

Linked Stacks

Ch. 8.3

10/18

Assignment 3 Due

10/20

Introduction to Queues

10/22

Linked Queues and Examples of Stacks and Queues

Ch. 8.4-8.7

10/25

Lists

Ch. 10

10/27

Assignment 4 Due

10/29

Exam 2

Part III: An Introduction to Algorithms

11/1

Recursion

Ch. 13.1-13.3

11/3-11/5

Algorithmic Efficiency

Ch. 9

11/8

Searching Arrays

11/10

Assignment 5 Due

11/12-11/15

Sorting: Bubble Sort , Insertion Sort , Selection Sort and Merge Sort

Ch. 10, 14.2-14.5

11/17

Exam 3

11/19

Line Search

Part IV: Putting it All Together

11/29-12/1

Maps: Conformal and Hashed

Ch. 11

12/3

Graphs and Trees , Data Structures for Graphs , Data Structures for Trees , Tree Traversal and Binary Search Trees

Chap. 12.3,15

12/6

Heaps , Priority Queues and Heap Sort

Ch. 12, 14.1

12/8

Path Finding Algorithms and Data Structures for Path Finding

12/10

Assignment 6 Due

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: 3 in-class exams (20% each) , 1 final exam [during the exam period] (20% total) and several programming assignments (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 (C++ Basics)
Programming Assignment 2 (OOP in C++)
Programming Assignment 3 (Dynamic Memory Allocation, Linked Data Structures)
Programming Assignment 4 (Stacks, Queues, Lists, etc...)
Programming Assignment 5 (Recursion)
Programming Assignment 6 (Searching, Sorting and Hashmaps)

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

Office Hours: You may meet with Prof. Bernstein during his scheduled office hours or you may schedule an appointment with him.