|CPSC 327||Data Strutures and Algorithms||Spring 2006|
At the heart of computer science is the development of efficient algorithms for solving problems, and the choice of data structure to implement that algorithm can have a significant impact on the simplicity and efficiency of a program.
This course continues the study of data structures, their applications, and the algorithms associated with them. Topics include abstract data types, dictionaries, graphs, searching, and sorting. The design and analysis of algorithms is also covered, with topics such as efficiency and complexity, NP-completeness, dynamic programming, and amortized analysis.
M 1-2pm, W 4-5:30pm, Th 9:30-11am, F 1:30-2:30pm
|Class Hours and Meeting Place||
|Course Web Page||
Algorithm Design: Foundations, Analysis, and Internet
Additional material will be handed out or posted on the course webpage.
CPSC 225 and CPSC 229
|Rationale & Aims||
This course explores a topic at the very core of computer science: designing efficient solutions to problems, and implementing those solutions in efficient and organized ways. The course has three main goals:
These skills will build on the programming skills introduced and refined in CPSC 124/225, with the ultimate goal of producing stronger problem-solvers and programmers.
|Course Content Overview||
The course material falls into five main units:
Algorithm Analysis: You've thought of several algorithms for solving a particular problem - which is the best? Time- and space-efficiency will be discussed, and big-Oh notation will be introduced - concepts which will be the fundamental tools used in the rest of the course. There will also be a quick review of several basic data structures (including stacks, queues, vectors, and lists) with an emphasis on applying the new algorithm analysis tools to compare possible implementations of these data structures.
Searching, Sorting, and Selection: Searching, sorting, and selection (picking the kth smallest or largest item) problems are extremely common, so it is worth considering how to solve these problems efficiently. This section will expand the toolbox of known data structures and algorithms with a number of new data structures (including balanced search trees and hashtables) and algorithms (including sorting and selection algorithms). These three problems will also serve as a case study of how different data structures and algorithms can greatly affect a program's efficiency, and will provide a motivation for introducing some additional tools for algorithm analysis.
Algorithm Design: The next unit will examine three fundamental techniques of algorithm design (greedy algorithms, divide-and-conquer, and dynamic programming), along with examples of applications of each technique. This continues to build the toolbox of known solutions, but more importantly begins to build a repertoire of strategies for solving new problems.
Graphs: The graph is a data structure with a wide variety of applications. We'll define a graph ADT, consider how that ADT might be implemented, and introduce a number of common graph algorithms (including traversal, shortest path, and minimum spanning tree) and their applications.
Complexity and NP-Completeness: After a semester-long focus on the efficiency of algorithms, some questions might come to mind: Are some problems fundamentally harder to solve than others? Are there problems that can't be solved? We'll delve briefly back into more theoretical topics to examine these questions (and what "hard" actually means), and to look at some of the hardest problems in computer science.
If time permits, some additional data structures (such as sets and heaps) and algorithms for different domains (such as text processing, computational geometry, and network security) will be considered.
|Assignments and Evaluation||
This course is a problem-solving course. Many of the assignments will be written, but some will involve programming or use of the computer for experimental studies.
Homework: To encourage discussion and keeping up with the course material (and to enable rapid feedback), homework problems will be assigned frequently and will generally be due at the beginning of the next class period after they are assigned (rather than having large weekly problem sets). Of the problems assigned each day, only a few will be designated as problems to hand in for grading. (The rest should be worked for additional practice and review.)
Late homeworks will not be accepted, but the three lowest individual problem scores will be dropped when computing the homework component of the final grade.
Programming Exercises: Some exercises will involve implementation and/or experimental comparison of different data structures and algorithms. Programming assignments will generally have a longer deadline than homework problems (e.g. due a week or so after being assigned).
Exams: There will be two midterm exams and a final exam. All will be take-home exams, and will emphasize applying concepts rather than simple recall. More information about the exams will be provided closer to the exam dates.
Late Policy and Collaboration: See the course policies for the late policy and collaboration policy.
Final Grades: Final grades in this course will be computed as follows:
On-time attendance and class participation (see the course policies) are expected, though they are not formally factored into your final grade. However, missing class - for any reason - often results in lower grades because important material was missed. Similarly, not participating in class even if you are physically present may mean that you aren't actively following the material and thus may be missing more sophisticated or subtle points. Whether or not your grade is impacted for these reasons is up to you - it is your responsibility to get notes from another student or otherwise catch up on missed material. Also note that class participation and the number of unexecused absences are considered when deciding whether or not to round up a final grade which is just below a grade-level cutoff. See the course policies for the definition of unexcused and excused absences.
Extra Credit: There will be opportunities for extra credit at various points during the semester.