CPSC 327 Course Information

On this page:

Course Description and Objectives
Prerequisites
Textbook
Software


Course Description and Objectives	At the heart of computer science is the development of efficient algorithms for solving problems. This course focuses on the design and analysis of algorithms, addressing common algorithmic approaches (iterative, recursive, divide-and-conquer, greedy, backtracking, branch-and-bound, dynamic programming) as well as topics such as correctness, efficiency, complexity, and NP-completeness. The choice of data structures used to implement an algorithm can have a significant impact on the simplicity and efficiency of a program, so data structures will also be considered. This course continues the study of data structures begun in CPSC 225, with a focus on hashtables, heaps, balanced binary trees, graphs, and building your own data structure for a particular application. The course has three main goals (and several subgoals): developing the skill of analyzing a problem and creating an efficient and provably correct solution to that problem, which includes: gaining a working knowledge of algorithmic efficiency, to inform the algorithm- and program-design process by providing a basis for comparing solutions and defining good solutions developing a toolbox of known data structures and algorithmic strategies which can be used to solve many common problems developing the knowledge of how to think about algorithms and data structures, for when a "canned" data structure or algorithm might not be sufficient fostering an appreciation for the practical value of studying algorithms and data structures developing other skills useful in computer science: abstract thinking, comfort with the idea of tradeoffs, and a habit of critical reflection By the end of the course, the successful student should be able to: describe and discuss different ways in which the efficiency of an algorithm can be determined define big-Oh notation discuss the pros and cons of asymptotic measures (big-Oh) and experimental measures of algorithm efficiency define the difference between best case, worst case, and average case running time/space determine the (best, worst, average) running time/space of an iterative or recursive algorithm arrange algorithms from fast to slow based on their asymptotic running times define: iterative algorithm, recursive algorithm, divide-and-conquer, greedy, recursive backtracking, branch-and-bound, dynamic programming give examples of algorithms utilizing each approach for each approach, identify the problem characteristics that make that approach suitable identify the steps for developing algorithms of each type develop algorithms for a new problem using suitable approach(es) convincingly justify the correctness of the resulting algorithm identify the key properties and typical operations of each ADT give examples of applications of each ADT match the needs of the problem to an appropriate ADT compare and contrast the time- and space-efficiency of different implementations of ADTs and discuss situations in which each implementation is most appropriate define and implement basic graph algorithms (e.g. depth-first search, breadth-first search, topological sort, shortest path), determine their running times, and discuss their applications define P, NP, NP-hard, and NP-complete and give examples of relevant problems describe several important NP-complete problems (e.g. 3SAT, vertex cover, clique, knapsack, TSP) discuss and apply algorithmic strategies (e.g. backtracking, branch-and-bound) for dealing with NP-complete problems

Prerequisites	CPSC 225 is required. Programming in this course will be done in Java, and students are expected to be able to write a program from pseudocode or a description of an algorithm. Also expected is familiarity with basic abstract data types (lists, stacks, queues, and binary trees), how those data types are implemented (using arrays, linked lists, and linked structures), and recursion. CPSC 229 is recommended. The most relevant topics from 229 are the idea of a formal mathematical proof, and specific proof techniques such as induction and proof by contradiction. Topics such as finite automata, context-free grammars, and some notions of computability may also make an appearance. All of these topics will be introduced as needed, but prior exposure is helpful.

Textbook	There is no textbook to purchase for the course. Readings will be posted on the course website. If you are looking for reference books, the classic resource is Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (also known just as "CLR" after the authors of the first edition). This book is very thorough, but can be a bit dense as a first introduction. It is available as a physical book in our library (but please don't check it out during this semester so that it remains available to everyone) or as an ebook to which you have free access through our library. Another reference is The Algorithm Design Manual by Skiena. It is both a good introduction for how to design algorithms and data structures and an extensive catalog of algorithmic problems that arise in practice. Many times the problem you are trying to solve turns out to be something well-known in disguise. This book is available as a physical book in our library (but please don't check it out during this semester so that it remains available to everyone).

Software	Projects will involve programming in Java with JavaFX used for GUIs. (You will not be expected to do any GUI programming, but may need to be able to run provided code that uses JavaFX.) The Eclipse development environment is recommended, but not required. Java 11, JavaFX, and Eclipse are available on the computers in two labs: Rosenberg 009 and the Math/CS lab (Lansing 310). If you want to set up your own computer you will need several things: Java 11 (JDK, not JRE) JavaFX Eclipse 2019-06 a file transfer program For Java 11 and JavaFX, see Getting JDK and JavaFX for information on obtaining and installing the right packages. The AdoptOpenJDK site is recommended for Java 11 if you aren't running Linux and installing through your distribution's package manager. Integrated development environments (IDEs) such as Eclipse make the development of larger programs easier. You can download Eclipse version 2019-06 here - select either the "Eclipse Installer" at the top of the page or the "Eclipse IDE for Java Developers" version partway down the page and choose the appropriate version for your computer (Mac, Windows, or Linux). It is recommended that you switch to this version of Eclipse even if you have an older version already installed. You will need to do some setup to be able to use JavaFX with Eclipse, as described in Using JavaFX in Eclipse. Finally, you will need a way to transfer files between your computer and the department filesystem. Using a file transfer program is more convenient than emailing files to yourself, and doesn't require you to remember to transfer the files before switching to another computer. Follow the directions here to download, install, and use the appropriate file transfer program for your computer. Note that Eclipse projects store some environment-specific configuration information and Eclipse does some management of the workspace directory on its own, so your best bet for transferring projects between the CS computers and your own is to copy the project folder somewhere other than into your workspace, create a new project within Eclipse on the current computer (if you don't already have one for the program you are working on), and then import the source files from the copied folder to the new project via Eclipse. It's a bit awkward but it does get the job done. Stop by office hours if you need help with this or any other aspect of getting your computer set up.