CMP507 Data Structure and Algorithm Spring, 98
Meets: Monday 16:00 - 19:00 in TGP004
Instructor: Dr. Peter Wang
Office: CCN104F
Credit Hours: 3 Credit Hours
Telephone: (205) 851-5570
Fax: (205) 851-5570
Website: http://ching.aamu.edu, http://cis.aamu.edu
Office Hours: T,R:11-2, F:8-12
Email: phwang@asnaam.aamu.edu
Course Objective:
The objective of this course is to introduce the fundamental concepts of
structured programming and data structures needed to solve real
world problems and develop efficient programming skills. This
course would present the complex concepts in a concise, informal
way, and explain theory coupled with concrete examples. Upon
completion of this course, the students should be able to write
programs with the maximum amount of efficiency.
Prerequisites: CMP503 and CMP505
Textbook: Data Structures, Algorithms & Software Principles in C
Thomas A. Standish. Addison Wesley.
Programming assignments: There are 5 programming assignments.
All the programming assignments are due 2 weeks after
assigned. Each program is 4 point. You must implement all
assignments in C/C++. Your programs must run on one of
the machines of CIS department PC lab.
Due date: P1: 1/26/98
P2: 2/9/98
P3: 2/23/98
P4: 3/9/98
P5: 4/20/98
P1: To create a telephone directory system which allows
the user to build the telephone directory from a
data file, to modify each field of a record, to
insert an entire record, to delete an entire record,
to display the telephone directory in ascending
order of name, to inquire record(s) by name.
P2: All solutions of eight queen problem.
To place eight queens on an 8x8 chessboard so that
no queens "attack", that is so that no two of
them are on the same row, column, or diagonal.
P3: To sort a set of 20 integer numbers: 618, 10, 298, 98,
260, 313, 453, 133, 387, 228 by the following
sorting methods and print out the comparisons of
each sorting method.
1. Bubble sort.
2. Insertion sort.
3. Binary Sort.
4. Heap sort.
5. Quicksort.
P4: Using double link list to create a binary tree for
personnel system which allows the user to insert, list,
modify, delete a record and list all the personnel
records in ascending and decending order by name
Each employee record should contain the employee
name, address, telephone, sex, social security number,
and salary.
P5: Write a program which solves a 15 by 15 maze
problem. The starting point is maze(0,0), the exiting
point is maze(14,14). The original maze and the successful
path must be produced.
Bonus programs: There are 10 bonus programs. Each bonus program
earns 1.0 point. The daue date for bonus programs:
BP1, BP2: 2/2/98
BP3: 2/16/98
BP4, BP5 3/2/98
BP6: 4/ 6/98
BP7, BP8: 4/13/98
BP9, BP10: 4/20/98
BP1: Find the great common divisor of two nonnegative
integer numbers.
BP2: Generate the first 20 Fibonacci numbers by both of
iteration and recursive versions, display the
execution time each.
BP3: Generate the first 50 prime numbers.
BP4: Print out which day (Monday, Tuesday,..) is your birthday.
BP5: Design a dictionary lookup powerbook with at least 30
entries, each entry consists of the page number in one
of your dictionary, the word, and its definition &
examples. Your program should allow the user to
insert, delete, modify, and inquire individual entry
in the dictionary.
BP6: Implement a reverse polish desk calculator.
BP7: Coloring problem: to color the US states in no more than
4 colors such that no adjacent states with the
same color.
BP8: Write a program to convert an infix expression into
postfix expression.
BP9: Write a program to solve an 8x8 linear equations.
BP10: Write a program to find the first 5 perfect numbers.
Bonus: Submit an report of analysis of data structure and algorithm
related papers from ACM/IEEE with paper. Each earns 0.3 point.
Term Project:
The student will be expected to submit a project that will
be due on April 20, 1998. The project will be given in class.
Your project must be implemented in C/C++/VB,
the analysis, user manual, and project report.
Source Code and documentation : Your source code should be delivered
and documentewd as follows:
1. Hard copy of well documented source code
2. Code documentation: Your code should be well documented.
(a) Each function should be identified with a distinguishing
header and a short description of what it does.
(b) You should provide sufficient documentation in your
code that it will be clear to the instructor what a
given segment of code does with respect to youe
overall system.
Midterm: The midterm will be March 2, 1998. It will cover the
material presented in class through Feb. 23, 1998. The
midterm will be a close books, close notes exam.
Final: The final exam is scheduled for May 5, 1998. It will
be a comprehensive, close books, close notes exam covering
material from the entire course.
Course Policy: No test will be made up without prior approval
of the instructor. Late assignments and tests will be
penalized. (minus 30% late). No project,
assignments can be shared. Shared projects and assignments
will be panalized. (minus 50%).
Grading: Total 100 points
Class participation 10%
Programming assignments 20%
Homework 10%
Midterm 30%
Project 10%
Final test 20%
Grade Scale: 100-90 A 89-80 B 79-70 C
69-60 D 59-0 F