Course Description: Representation and organization of digital information in the form of effective and efficient data structures, manipulation of data structures in a procedural fashion, and the analysis and evaluation of various algorithms. The following topics will be covered: ADT, arrays, tables, linked lists, stacks, queues, trees, sorting, searching, graphs, hashing, spanning trees, disjoint sets, and heaps.
Outcomes:
The instructor will:
1. Aid students to achieve an expert knowledge of how to represent and organize digital information by variety of data-structures applicable in most object-oriented languages.
2. Introduce students to the techniques of manipulating these structures by algorithms to perform common actions on the data structures such as finding, retrieving, adding, and deleting information.
3. Illustrate benefits and drawbacks of different algorithms by analytically and experimentally evaluating algorithmic efficiency.
4. Provide students with the background knowledge and skills needed to successfully design, implement, modify and evaluate digital information in subsequent upper-division computer science courses.
Students will be able to:
1. Design suitable information representations for a variety of problems.
2. Describe appropriate algorithms and data structures for a number of well-defined problems.
3. Design algorithms to solve given problems using techniques such as divide-and-conquer.
4. Implement algorithms and data structures in a computer programming language: C++ or Java.
5. Analyze the time and space efficiency of an algorithm, use the big-O notation.
6. Measure the time and space requirements of an algorithm.
Homework Assignments: There will be approximately six homework assignments that will consist of both analytical problems and programs to write. Late homework will be penalized by 5% per day late, up to the day that answers are provided. I will typically post answers the next week (but not always). Unless otherwise indicated, programming assignments and written assignments must represent your own work. It is permissible to discuss the assignments with other students, but do not disclose the solution.
Group Problems: On most weeks we will spend the end of a class period in randomly formed groups. You will be asked to work on a problem or set of problems within your group and discuss the solution with your group. There will also be some short presentations within your group and the class. You receive a grade of 0 or 1 based on participation for the group activity.
Questions: If you have any questions, feel free to come in to my office. In general, I have an open door policy -- if I am available in my office, you are welcome to come by. An even better way to reach me is through email. I check my email frequently and you should receive a response quickly. Email is preferred over telephone and you will probably receive a faster response since I don't check voicemail very frequently.
Exams: There are three exams, each worth an equal amount. Each exam will cover several chapters of the book while the final exam may include any material that was covered in the course, but will emphasize the new material. Unless prior arrangements are made no make-up exams will be given. Since you will be tested upon your critical thinking and problem solving skills and not your ability to memorize formula, exams will be open book/computer/notes. You are not allowed to search online or chat electronically during exams.
Grading:
Grading breakdown:
Homeworks: 30%
Group Problems: 10%
Exams: 60%
An incomplete grade will only be given for a valid excuse (e.g. medical, death in the family). An incomplete grade does not let you take the class over again, your final grade will be assigned based on work submitted in class and work that remains to be submitted.
Cheating: Students are expected to uphold the UAA standard of conduct relating to academic dishonesty outlined in the UAA catalog and student handbook. Cheating is not tolerated and constitutes grounds for dismissal. For this class, it is permissible and encouraged to assist classmates in general discussions of how to attack the homework problems. It is not permissible to copy another's work (or portions of it) and represent it as your own.