Pre-requisites: CS210 and CS240 and Math140.
Start-End Dates: 5/26/2015 – 7/23/2015
Instructor: Joseph Paul Cohen ( joecohen -at- cs.umb.edu )
Teaching Assistant: Daniel Manning ( dmanning -at- cs.umb.edu )
Office Location: KDLab S-3-159 Map
Office Hours: Tuesday 4-5pm
Course Room: McCormack M01-0409
Meeting Time: MoTuTh 6:00PM – 7:30PM
Lab/Recitation Location: UNIX Lab
Lab/Recitation Hours: Monday 5pm-6pm
Piazza: https://piazza.com/configure-classes/summer2015/cs310
DESCRIPTION
A systematic study of the methods of structuring and manipulating data in computing. Abstract data types. The design and analysis of algorithms. Advanced techniques for program development and organization. The language of instruction is Java.
PREREQUISITES
- CS 210, fluency in Java, knowledge of stacks, queues, binary search trees, and sorting
- CS 240, knowledge of C, static and dynamic memory allocation
- Math 140, Calculus I, knowledge of limits and summations.
COURSE OUTCOMES
- Demonstrate a familiarity with major algorithms and data structures.
- Apply important algorithmic design paradigms and methods of analysis.
- Synthesize efficient algorithms in common engineering design situations.
- Understand the difference between tractable and intractable problems, and be familiar with strategies to deal with intractability.
- Analyze worst-case running times of algorithms using asymptotic analysis. Compare the asymptotic behaviors of functions obtained by elementary composition of polynomials, exponentials, and logarithmic functions. Describe the relative merits of worst-, average-, and best-case analysis.
- Explain the basic properties of randomized algorithms and methods for analyzing them. Recite algorithms that employ randomization. Explain the difference between a randomized algorithm and an algorithm with probabilistic inputs.
- Describe the greedy paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize greedy algorithms, and analyze them.
- Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
- Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic programming algorithms, and analyze them.
- Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate. Synthesize new graph algorithms and algorithms that employ graph computations as key components, and analyze them.
- Explain the concept and basic examples of basing cryptographic security on hard computational problems
TEXTBOOKS
| Required |  |
Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley 2005, ISBN 978-0321295354. |
| Recommended |  |
This book will serve as a reference for the CS210 prerequisite. Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne ISBN: 978-0321573513 |
| Recommended |  |
This book will serve as a reference for the CS210 prerequisite. Java Structures: Data Structures in Java for the Principled Programmer by Duane Bailey ISBN 978-0072399097 |
RESOURCES
Eclipse IDE
Download Eclipse Mars (Latest Milestone Release)
Download Eclipse Luna (Current Public Release)
Eclipse Java Demo Video
Eclipse GIT Demo Video
Linux
UNIX Tutorial for Beginners
Basic Linux and Package Management
Algorithm/Data Structure Visualizations
USFCA Algorithm Visualizations
Sorting At
Visual Go
GRADING POLICIES
| Exams (3 total, lowest grade is dropped): | 40% |
| Homeworks/Projects: | 50% |
| Class participation/attendance/contribution: | 10% |
TURNING IN WORK
Turn in work by ssh-ing into users.cs.umb.edu and entering your cs310 directory. You can scp your work as well. Any issues email operator -at- cs.umb.edu from your cs.umb.edu account. For an account go to the UNIX/Linux lab (S-3-159) and ask for the operator.
FILE FORMATS
I will only accept ASCII or UTF text (.txt,.java,.html,.tex …) files or pdf files.
LATE ASSIGNMENTS
I will only allow one late assignment. This assignment can be turned in anytime before the last class. You can change which assignment you turn in late if you would rather receive the points for a different assignment. For example you can use your late assignment on a homework and then if you are late on a project (worth more points) you can use the late assignment to turn in the project instead. Note: You will them receive no points for the homework.
COLLABORATION ON HOMEWORKS
You are encouraged to discuss homeworks with other students. Please only assist other students in finding the answer. Do not give answers to anyone. If you discussed a homework with someone document this on your homework.
ACADEMIC DISHONESTY
The penalty for cheating is extremely severe. It can result in an F in this course. Cheating consists of, but not limited to:
– Using or copying a person’s work (outside class or class member) on an exam or assignment in any fashion.
– Allowing your own work to be copied or used by another person.
– Submitting as your own work something that has been written by another person.
– Using any unauthorized reference on an exam or assignment.
– Not acknowledging in writing on an assignment any help you have received.