Data Structures Syllabus

• Course COSC-2320 Computer Science Department, University of Houston
• Instructor: Boanerges Aleman-Meza, bam AT nsm.uh.edu
• Office Hours Tuesday, Thursday, 1 - 1:30pm (127 Fleming), and 2:30-3:30pm (PGH 589), Wedneday 11am-1pm (Fleming 127), or by appointment.

The information contained in this class syllabus is subject to change without notice. Students are expected to be aware of any additional course policies presented by the instructor during the course.

Learning Objectives: Students will gain a good understanding of both theory and programming of fundamental data structures and algorithms. This course will provide a foundation for more advanced courses in computer science. Students will learn how data structures help in solving many problems in all areas in computer science, including compilers, database systems and operating systems. Students will understand how to derive a function that quantifies the efficiency of an algorithm, and will be able to understand how to analytically prove that a program works correctly. Finally, students will become experienced C++ programmers, understanding how to develop correct and robust code and how to test it.

Major Assignments/Exams:

This is a course that gives more weight to homeworks. Grading is as follows:

• 70%: 7 programming assignments.
• 30%: midterm.

Programming assignments are a fundamental component of learning for this course. All programming homeworks must be turned in to get B-. Programs will be developed in C++ and tested with the GNU C++ compiler. Programming assignments are individual. The TAs will post sample test cases, but the programs will be tested with similar test cases (not the same input files). The programs are thoroughly tested by the TAs, are graded on a 0-100 scale, and there is a severe penalty for each encountered error. A non-submitted program grade is ZERO. A non-working program (i.e., compiles, but does not run) grade is 10. A program with many errors typically reaches 50. Only fully functional programs can be expected to receive 80 or higher.

Required Reading: Malik, D.S. Data Structures Using C++. Course Technology, 2nd edition, 2010.

Recommended Reading: Any CS book on C++ and discrete mathematics are helpful for additional reference. A good reference for the theory part is the following book: Aho, J.E. Hopcroft, and J.D. Ullman. Data Structures and Algorithms. Addison/Wesley, Redwood City, California, 2nd edition, 1983.

List of discussion/lecture topics:

1. Basics of C++: pointers, arrays, parameter passing, class encapsulation, inheritance, methods, function overloading, Input/Output
2. Abstract Data Types, and Object Oriented Programming
3. Linked lists, queues
4. Stacks, recursion
5. Trees, balanced trees, multi-way search trees
6. Hashing functions and hash tables
7. Sorting and search algorithms: selection sort, heap sort, quick sort, shell sort, merge sort, linear and binary search, hash-based search.
8. Graphs, graph traversal, search, path problems, transitive closure

Theory covered in the course:

1. Time complexity analysis
2. Algorithm design techniques
3. Recursive functions
4. Proving algorithm correctness

Miscellaneous

• class google-group

• ICS Videos for the section of this class contains a video example of using GIT to copy yor files to the linux server (instead of doing so via FTP or scp).