CS 2420 Course Outline: Data Structures and Algorithms Using C++:  Fall 2009

  • Instructor: Dr. Ron Peterson
  • Time & location: 9:30-11:20 a.m. Mon & Wed  in TE108
  • Office hours: Tue thru Thur 8:30-9:20 a.m., Mon & Wed 11:30 a.m.-12:20 p.m., or by appointment
  • Office location: TE 110E
  • Office phone: 801-626-6795
  • E-mail: rpeterson@weber.edu
  • Text: Data Structures Using C++, 2nd Edn, by D. S. Malik

 

Course objectives:  To be able to write C++ programs based on Data Structures including arrays, linked-lists, stacks, queues, trees, graphs, tables, and storage and retrieval structures.  To extend abilities in programming advanced Object-Oriented designs using the Visual Studio development environment.  To develop a repertoire of programming methods and tools to support rapid development of safe, efficient code.  To gain additional insight into algorithmic efficiency by studying searching, sorting, and hashing.  To become proficient at programming Abstract Data Types,  static and linked Data Structures, polymorphic user-interfaces, inheritance, exception handling, container classes, and templates.  Also to become familiar with advanced features of C/C++ and with the STL (C++ Standard Template Library).

 Course coverage by week:

Week of 

Topics 

Chapters 

Homework due

8/24

Introduction, objectives; the OO Paradigm; Pre-test; C++ basics

1

 

8/31

OOP; Review of C++:  classes; programming style; ADTs; Algorithmic efficiency;

2

 

9/7

{Labor Day}; Polymorphism: inheritance, operator overloading, templates; Quiz 1

-

 

9/14

Pointers; Exception handling; C-strings, string class; String Streams; 

 3, G

Prog. 1

9/21

Intro STL: containers, adapters, iterators; vector, list; Quiz 2;

4

 

9/28

Linked lists, header/sentinel, doubly- & circularly-linked;

5

 

10/5

Recursion

6

Prog. 2

10/12

Stacks: dense & linked implementations; STL Stack; Quiz 3;

7

 

10/19

Queues: dense & linked implementation, deques; STL Queue

8

 

10/26

Searching methods: linear, binary; storage/retrieval; hashing; Quiz 4

9

 

11/2

Sorting methods: simple, merge, Quicksort; Heapsort; STL sorting

10

Prog. 3

11/9

General and ordered trees, tree traversal; Binary trees, traversal

11

 

11/16

Tree search, balancing (AVL Tree, B-Tree, Red-Black Tree); Quiz 5

-

 

11/23

Graphs and graph applications 

12

Prog. 4

11/30

STL algorithms, functors; Quiz 6; review

13

 

 

 

 

 

12/7

9:30-11:20 a.m.      ***FINAL EXAM*** (comprehensive)

 

 

***Demo programs will be due in class each Monday (Wednesday for holidays) showing use of the current material
  - - (See homework pages for the list of required topics.  Late demo programs receive no credit.  Do at least 11 of 14 for maximum credit.)
***Quizzes will be on Wednesday during the first half of class.
***Major programs will be due by the end of class time on Wednesday of the week shown and will lose 20% per weekday for being late.

Grading:

4 programs @30 + 11 demos @5 + 6 quizzes @25 + final @225  = 550 points possible

 

the minimum score to get each grade is:

505 A 

460 B+ 

390 C+ 

320 D+

485 A- 

435 B 

365 C 

295 D

 

415 B- 

345 C- 

275 D-
  • No make-up quizzes will be given; if you have a conflict, contact Dr. Peterson as soon before the quiz as possible.
  • Grade of "I" will only be given in exceptional cases, and only when a total of at least 250 points has been accumulated.
  • Any cheating, including copying parts of other students programs, will result in an "E" grade for the course and other disciplinary action.
  • No cell phones or pagers will be allowed to interrupt class; first offense loses 10 points, additional offenses lose 30 points each.
  • Any student requiring accommodations or services due to a disability must contact Services for Students with Disabilities (SSD) in  the Student Services Center, room (SC)181.  SSD can also arrange for course materials in alternative formats if needed.