COMPUTER ALGORITHMS
&
DATA STRUCTURES
SPRING 2003
SYLLABUS
Instructor
Dr. Pervin; e-mail: pervin@utdallas.edu; URL: http://www.utdallas.edu/~pervin
Office Hours: TR 10:45am-11:15am and by appointment; Office: EC 4.626
Catalog Description
Basic data structures such as arrays, stacks, queues,
lists, trees. Algorithmic complexity. Sorting and
search techniques. Fundamental graph algorithms.
Prerequisites
CS 2315 and EE 3307 or their equivalents
Text
Mark Allen Weiss, "Data Structures & Algorithm Analysis
in C++", 2nd Ed., Addison-Wesley, 1999.
It is expected that the text material will be studied
outside of class before it is needed to follow the
discussion in class. In addition, you will be expected
to read, by yourself, some material from the text
not covered in class. Examinations are based on material
covered or described in class, even if not in the text.
Grading
There will be two examinations (worth 25% each)
during the semester and a comprehensive final (worth
40%). Homework will count in the final grade (10%).
All tests are graded subjectively, but fairly.
Tentative Schedule
Classes meet from 12:30pm to 1:45pm Tuesdays and Thursdays in EN 2.112
- 01. (1-14) [1&A] Introduction and C++
- 02. (1-16) [1&A] C++ classes
- 03. (1-21) [2] Algorithm Analysis
- 04. (1-23) [2] Order - "Big-O"
- 05. (1-28) [3] Lists, Stacks, Queues
- 06. (1-30) [3] (ADTs) Abstract DataTypes
- 07. (2-04) [4] Binary Trees
- 08. (2-06) [4] Search Trees
- 09. (2-11) [4] B-trees
- 10. (2-13) Examination I (25%)
- 11. (2-18) [5] Hashing
- 12. (2-20) [5] Random Numbers
- 13. (2-25) [6] Heaps
- 14. (2-27) [7] Sorting
- 15. (3-04) [7] Analysis of sorts
- 16. (3-06) [7] Heap, Merge, Quick Sorts
- SB. (3-11/13) Spring Break
- 17. (3-18) [9] Graphs
- 18. (3-20) [9] Topological Sort
- 19. (3-25) [9] Shortest Path
- 20. (3-27) Examination II (25%)
- 21. (4-01) [9] Dijkstra's Algorithm
- 22. (4-03) [9] Network Flow
- 23. (4-08) [9] Minimum Spanning Tree
- 24. (4-10) [9] NP-Completeness
- 25. (4-15) [10] Greedy Algorithms
- 26. (4-17) [10] Divide and Conquer
- 27. (4-22) [10] Dynamic Programming
- 28. (4-24) [10] Backtracking; Red-Black Trees
- FE. (5-01) Final Examination (40%)
This is a very ambitious schedule.
Students cannot afford to fall behind in their studies
since this will be a cumulative learning experience.
Students are expected to attend all classes.
Repeated absence from class or failure to turn in
homework regularly will be cause for dropping the
student from this class.
Examinations are based on material covered or
described in class.
Consult the class schedule and course catalog for
information on withdrawals, incompletes, and
academic dishonesty (see below).
Homework
Assignments will be made and must be turned in on time.
Programs should be written in C++ but other languages
(such as Java) may, with permission, be used.
Note that, although we are forced to use some one
language (C++) and cope with its details to some degree,
the study of algorithms should really be done in a way
that is as independent as possible
of the particular language used.
Students should keep a copy of their homework in case they
need it for reference before they can be graded and
returned. Not all problems will be marked and counted,
but students should do all the homework (and more)!
Honor Code
It is understood that your homework and examination
answers must be all your own work. There are clear
rules about "Scholastic Dishonesty" so please avoid
even the appearance of impropriety. Every paper you
submit has the following pledge assumed:
I have neither given nor received aid on this
homework/examination.