CS 250 (001)          Algorithms & Data Structures        Fall 1997   

Room: Peck 2412

Time: 6:00 - 7:15 p.m.  

Text: Data Structures and Algorithm Analysis in C, Mark Allen Weiss

Supp. Texts: compared to what, Gregory Rawlins

      Data Structures and Algorithms, Aho, Hopcroft & Ullman

      Algorithmics, G. Brassard & P. Bratley

      Introduction to Algorithms, Cormen, Leiserson, & Rivest

Instructor: Bernard Waxman  -  BLDG II, rm 2323  -  692-2386

Electronic mail address: bwaxman@siue.edu or bmw@mpr.cis.siue.edu

Department WEB page: http://www.cs.siue.edu/

My WEB page: http://www.siue.edu/~bwaxman

Office hours: Tue & Thur 1:30 - 3:30 p.m. or Tue 7:30 - 8:30 p.m.

(Check with me or the CS secretary for other times)

Grading: Assignments, Programs & Lab reports 35%

Two exams 30%

Final Exam 25%

Other 10%

Policy:

Programming assignments must be written in C++ and run under UNIX. Your source code must be placed in a subdirectory called CS250 under your home directory on daisy.
 
Assignments are due at the beginning of class on the date specified. Points will be deducted on assignments that are turned in after the due date.
 
Regular Attendance is expected.

Topics:

CS 250 will cover Chapters 1 - 7 and 9, 10 from the book by Weiss. You will be expected to do the reading assignments before the topics are discussed in class, and to be prepared to ask questions if there are things you do not understand. Other reading material will be provided to supplement reading assigments from the Weiss book.

 

COURSE CONTENT

1. Analyzing algorithm performance
1. Compare algorithm in terms of time complexity, space complexity, understandability, and ease of implementation
2. Definition and us of Omega, O, and Theta.
3. Pseudocode and its use in analyzing performance
2. Review mathematical induction and compare to recursive algorithms
3. Searching, a comparison of binary and linear search
4. Review of basic data structures
1. Stacks, queues, lists
2. Array and dynamic memory implementations
5. Selecting and sorting
1. Selection sort, insertion sort, quick sort, heap sort, and bucket sort
2. Merge sort and sorting large data sets in secondary storage
3. Choosing the best sort
6. Binary trees
1. Acyclic connected graphs
2. Binary Search trees (revisit binary search
3. Using recursion with trees (height, counting, searching)
4. Priority queues (2-heaps)
5. AVL and Splay trees
7. Graphs
1. Nodes, edges, directed and undirected graphs
2. Paths, connected, cycles, node degree, acyclic graphs, and planar graphs
3. Graph isomorphism
4. Minimum spanning trees - Kruskal's and Prim's algorithms
5. Shortest path trees and Dijkstra's algorithm
6. Graph coloring
8. Complexity classes and computability
1. The Turing machine as a model of computation (the Church-Turing thesis)
2. Turing's halting problem and Godel's incompleteness theorem
3. The classes P, NP, and NP-hard