| 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 data structures and
algorithms, continuing the study of data structures begun in CPSC
225 with a focus on more advanced structures (hashtables, heaps,
balanced binary trees, graphs, and building your own data structure
for a particular application), common algorithmic approaches
(iterative, recursive, divide-and-conquer, greedy, backtracking,
branch-and-bound, dynamic programming), and covering topics such as
correctness, efficiency, complexity, and NP-completeness.
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 (or not 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.
This course builds
directly on the material in CPSC 225 (and 124): programming in
Java, fundamental program constructs such as loops and
conditionals, basic abstract data types (lists, stacks, queues,
and binary trees), how those data types are implemented (using
arrays, linked lists, and other linked structures), and
recursion.
CPSC 229 is helpful, but not essential.
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. While prior exposure to this material is helpful, no
knowledge is assumed and all of these topics will be introduced
as needed.
|
| Textbook |
The Algorithm Design Manual (3rd ed)
Steven S Skiena
Springer, 2020
ISBN 978-3030542559 (hardcover), 978-3030542566 (ebook)
This is both a textbook for learning how to design algorithms and
data structures, and a useful reference with an extensive
catalog of algorithmic problems that arise in practice. I hope that
you will enjoy reading the book during the course and that you will
want to hang on to the book afterwards to use in your future
algorithmic endeavors.
If you are buying the book on Amazon or elsewhere, note
that the third edition has a very similar-looking cover to the
second edition. Look for "Third Edition" on the cover and/or check
the ISBN to make sure you are getting the right version.
Additional material will be handed out or posted on the
course webpage.
|
| Software |
Some homeworks will involve programming in Java.
The tools that you need (Java 17, JavaFX, Eclipse 2021-12) are
available on the lab computers in Rosenberg 009 (reboot them to
Linux) and Lansing 310, or you can install them on your own
computer.
If you want to set up your own computer for programming in this
course, you will need several things:
- Eclipse 2021-12
- Java 17 (JDK, not JRE)
- JavaFX
- a file transfer program
You can download Eclipse
2021-12 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; choose the x86_64 version unless you
have a very new Apple device). It is recommended that you switch
to this version of Eclipse even if you have an older version
already installed. Run the installer or unpack the compressed
archive file you downloaded (see below).
Eclipse 2021-12 includes Java 17, so you no longer need to
download that separately.
You can download JavaFX
from https://gluonhq.com/products/javafx/.
In the "Downloads" section, choose the right JavaFX version
(17.0.2), operating system, and type (SDK) from the dropdown menus
to narrow the list of download links. You'll also need to choose
the right system architecture - most likely x64 unless
you have a very new (within the last year) Apple device
(aarch64). Unpack the compressed archive file you
downloaded (see below).
To unpack the JavaFX (and possibly Eclipse) archives downloaded,
double-clicking on the file should either extract the contents or
start a program that will let you extract the contents. The
extracted files can go anywhere, but make a note of where they end
up.
You will also 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
leaving the lab. See
the SSH, SFTP,
SCP section
of Using Linux at
HWS for information about commandline options (scp, sftp)
which may already be available on your computer. If you prefer a
GUI tool and don't already have
one, FileZilla is
free and runs on all platforms. (You only need to download the
client, not the server.) Be sure to check out
the documentation
(especially the usage instructions). Enter "sftp://math.hws.edu"
for the host and leave the port blank when establishing a
connection.
Finally, you'll need to configure Eclipse to use the JavaFX
libraries and to set certain formatting and coding conventions:
-
Use the file transfer program to copy the
formatter and code templates files
from /classes/cs327/eclipse on the department filesystem
to your own computer.
-
Create a new workspace directory to use for this course
and start Eclipse.
-
From the "Window" menu, choose "Preferences". On the left side,
expand "Java".
-
Specify how code should be formatted:
-
Expand the "Code
Style" item under "Java", then click "Formatter".
-
On the right
side of the window, click "Import..." and then navigate your way
to /classes/cs225/eclipse (start with "File System" and
then double-click on each directory in turn).
-
Highlight cs225-formatter.xml and click "OK".
-
Make sure
that cs225 is shown as the "Active profile".
-
Specify options for code generation:
-
Expand the "Code
Style" item under "Java", then click "Code Templates".
-
On the right side of the
window, click "Import..." and then again navigate your way
to /classes/cs225/eclipse.
-
Highlight cs225-codetemplates.xml and click "OK".
-
At the bottom of the right side of the window, click the
"Automatically add comments for new methods, types, modules,
packages and files" box. (It should be checked.)
-
Tell Eclipse about the convention of naming instance
variables ending with _:
-
Choose the main "Code Style"
entry under "Java".
-
On the right side of the window, click on
"Fields" in the box under "Conventions for variable names:" to
highlight it, then click the "Edit..." button. In the box that
pops up, enter _ (an underscore) in the "Suffix list" box
and click OK.
-
Tell Eclipse to enforce Java 17 syntax rules:
-
Tell Eclipse to store compiled classes separately from source files:
-
Choose the main "Build Path" entry
under "Java".
-
Make sure that the "Folders" option is selected under "Source
and output folder", and that the source folder name is src and the
output folder name is bin.
-
Configure the Java 17 JRE with the VM options needed for
JavaFX: (in the following, substitute the path where you unpacked the
JavaFX download for javafx-lib)
-
Choose the main "Installed JREs" entry
under "Java".
-
Select the openjdk 17 JRE in the list and click "Edit...". (Ask if there's more than one choice and/or you aren't sure which to pick.)
-
Fill in the "Default VM Arguments" box with --module-path=javafx-lib --add-modules=ALL-MODULE-PATH (Make sure you include the -- at the very beginning!)
-
Click "Add External JARs...", navigate to javafx-lib, and select all of the files there.
-
Click "Finish".
-
Configure the default Java 17 environment to be the one you
just set up for JavaFX:
-
Expand the "Installed JREs" item under "Java", then click "Execution Environments".
-
Click "JavaSE-17" in the list of execution environments to
select it, then click the only item in the list of compatible JREs to toggle the checkbox on. (Ask if there's more than one.)
-
Finally, click "Apply and Close" at the bottom of the
Preferences window to apply the new settings and close the
window.
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 any aspect of getting
your computer set up or sorting out the workflow of how you'd
actually use all these pieces once they are installed and
configured. (Bring your laptop.)
|