Course: CS310, Section: 01Q, Class Number: 1726
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

WkChTopicHomework/Exam
5/252Introduction, Algorithm Analysis (big-Oh notation), Maps, HashTables (LinearProbeDemo)HW0 (due 5/28),
HW1 (due 6/2)
6/13,4Graphs and Trees, Greedy Algorithms (coin changing, interval scheduling, Interval partitioning, caching) (EarliestFinishTimeFirst Demo, EarliestStartTimeFirst Demo)Project 1 (due 6/15)
6/84Greedy Algorithms (Dijkstra's, Minimum spanning trees, single-link clustering) (Prim Demo, Kruskal Demo, Dijkstra Demo), UnionFind (QuickFind Demo, QuickUnion Demo, WeightedQuickUnion Demo)
6/155Greedy (Huffman coding) (Huffman Demo), Divide and Conquer (mergesort, counting inversions, closest pair of points)(Merge Demo, MergeInvert Demo)EXAM 0 (6/18),
HW2 (due 6/25)
6/226Dynamic Programming (Weighted interval scheduling, Knapsack problem)Project 2 (Due 7/7)
6/29Substring Search (Knuth-Morris-Pratt, Boyer-Moore) (Knuth-Morris-Pratt Demos), Dynamic Programming (Sequence alignment, string edit-distance, Needleman-Wunsch, Needleman-Wunsch Extra)HW3 (Due 7/9)
7/611ReviewEXAM 1 (7/9)
7/1313Dynamic Programming (Bellman Ford, Shortest Paths Dynamic Programming Extra, Bellman Ford Demo)HW4 (Due 7/21),
Project 3 (Due 7/27)
7/20Divide and Conquer (Fast Fourier Transform), Randomized and Approximation Algorithms (Linear Regression via Stochastic Gradient Decent)EXAM 2 (7/23)

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 kleinberg-tardos Algorithm Design by Jon Kleinberg and Éva Tardos.
Addison-Wesley 2005, ISBN 978-0321295354.
Recommended sedgewick-wayne This book will serve as a reference for the CS210 prerequisite.


Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne

ISBN: 978-0321573513
Recommended java-structures 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.