CMSC 330: Algorithms - Design & Practice

Bryn Mawr College
CMSC 330 Algorithms: Design & Practice
Spring 2016

Last modified: Thu May 5 11:18:34 EDT 2016 , Subject to change.

General Information

Instructor:	David G. Cooper
E-Mail:	dgc@cs.brynmawr.edu When you e-mail me, make sure you put "CS330" at the start of the subject line to ensure a quicker response.

Lecture Hours: Tuesdays & Thursdays, 2:25pm to 3:45pm
Room: Park 337

Required Texts

Please note: You may be able to find electronic versions of each of these as a PDF or ebook for a lower price. These can be great as a reference, in a pinch, but to really delve into the material, having a paper copy can be very useful.

Writing for Computer Science, 3rd Edition by Justin Zobel, Springer, 2014. Available at the Campus Bookstore. Also at Amazon.com for $37.39 click here.

Programming Pearls, 2nd Edition by Jon Bentley, Addison-Wesley, 1999 . Available at the Campus Bookstore ($39.99). Also at Amazon.com for $29.34 click here. Code from programming pearls available from wayback here.

Algorithms Unlocked by Thomas Cormen, MIT Press 2013. Available at the Campus Bookstore ($25.00). Also at Amazon.com for $21.65 click here.

Nine Algorithms That Changed The Future by John MacCormick, Princeton University Press, 2013. Available at the Campus Bookstore ($16.95). Also available at Amazon.com for $15.26 click here.

Syllabus

Course Description:This course examines the applications of algorithms to the accomplishments of various programming tasks. The focus will be on understanding of problem-solving methods, along with the construction of algorithms, rather than emphasizing formal proving methodologies. Topics include divide and conquer, approximations for NP-Complete problems, data mining and parallel algorithms. Prerequisites: Prerequisite: CS206 and CS231.

Important Dates

January 19 : First lecture
April 28: Last Lecture

Assignments

Unless explicitly specified, all assignments are due at the beginning of the class (BY 2:25pm sharp) on the date due. No credit will be awarded for any late work.

Assignment#1 (Due on 02/02): Write up algorithm from Algorithm Presentations. Click here for details.
Assignment#2 (Due on 02/11): Sorting large data files Click here for details.
Assignment#3 (Due on 02/18): Soundex Click here for details.
Assignment#4 (Due on 03/17): K-means.
Assignment#5 (Due on 04/05): Similar Names.
Assignment#6 (Due on 04/26): Tail Recursion.

Schedule (subject to change, check back for updates)

Week	Date	Topic	Reading Completed (by beginning of class)	Assignments _______________	Comments
1	01/19	Course introduction, logistics, overview. _________________________________________ Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity)	________________		slides worksheet
1	01/21	Discussion: Algorithm Design vs. Algorithm Practice vs. Algorithm Analysis Presentations of Worksheet 1 algorithms: Calla, Rachel, and Claire: Anagram search Kalina, Nora, and Neshka: Missing value search Jordan*, Hanna, and Clare: Missing value search	Cormen: Ch 1 MacCormick: Ch 1		blackboard notes
2	01/26	Discussion: Nine algorithms that changed the future. The first programming pearl (Bentley, sorting phone numbers).	Bentley: Ch 1	Start: HW 1	blackboard notes
2	01/28	Discussion: Describing and Evaluating Algorithms Presentation of Worksheet 1 algorithm B: Tu: Rotation recursive algorithm. Last rotation from Pearl 2.	Cormen: Ch 2		slides blackboard notes
3	02/02	Presentation: Search Engine Indexing, Sarah	MacCormick: Ch 2	Submit: HW 1 Start: HW 2
3	02/04	Presentation:PageRank, Ziting and Rachel Discussion: Aha! Algorithms, A look at C/C++ implementations. Compiling and running C/C++ programs.	Bentley: Ch. 2 MacCormick: Ch. 3
4	02/09	Presentation:Public Key Cryptography, Samantha and Xuan Discussion: Writing correct programs	Bentley: Ch. 3 & 4 MacCormick: Ch. 4
4	02/11	Presentation & Discussion: HW 2, Sorting Large Files, Tu		Submit: HW 2 Start: HW 3
5	02/16	Presentation: Pattern Recognition (Nearest Neighbor, Decision Trees, Neural Networks), Calla & Nora	MacCormick: Ch. 6
5	02/18	Discussion: Plots, Bongard Classes: design for first 9 classes.	Bentley: Ch. 5 & 6
6	02/23	Community Day of Learning (no class!)	MacCormick: Ch. 7
6	02/25	Presentation: Data Compression, Rebecca Discussion: Databases, Kalina & Neshka	MacCormick: Ch. 8	Submit: HW 3
7	03/01	Discussion: Writing, More Bongard Problems	Zobel: Ch. 5, pg. 51-62 Zobel: Ch. 12, pg. 179-190	Start: HW 4
7	03/03	Discussion: Writing, More Bongard Problems	Zobel: Ch. 13, pg. 191-196 Zobel: Ch. 14, pg. 197-215
	03/08	Spring Break
	03/10	Spring Break
8	03/15	Discussion: Error Correcting Codes, by Jordan	MacCormick: Ch. 5
8	03/17	Discussion: Expectation Maximization (EM)
9	03/22	Discussion: K-Means Assignment Presentation, Mary & Hanna	Submit: HW 4
	03/22
	03/24	Discussion: Digital Signatures, Aviva and Kara	MacCormick: Ch. 9	Start: HW 5
10	03/29	Discussion: Sorting algorithms: Selection Sort (Calla), Insertion Sort(Kalina), Merge Sort (Samantha), Quick Sort (Xuan).	Cormen: Ch. 3	Counting steps map (click for larger image):
10	03/31	Discussion: Counting Sort and Radix Sort (Rachel and Tu)	Cormen: Ch. 4
11	04/05	Discussion: HW 5 Finding Names (Sarah and Clare)		Submit: HW 5
11	04/07	Discussion: Directed Acyclic Graphs and Topological sort (Nora and Hanna)	Cormen: Ch. 5
12	04/12	Discussion: DAG and Naive Bayes Classification (Neshka and Kara)	Read:DAG and: Naive Bayes Classification
12	04/14	Discussion: Dijkstra's Shortest Paths (Jordan and Rebecca)	Cormen: Ch. 6	Start: Project 6
13	04/19	Discussion: Bellman-Ford algorithm (Ziting and Clare)	Cormen: Ch. 6
13	04/21	Discussion:	Book:
14	04/26	Discussion:Greedy Algorithms and Interval Scheduling, Aviva and Mary	Book:	Submit: Project 6 (NO LATE SUBMISSIONS WILL BE ACCEPTED!!!)
14	04/28
FINALS WEEK	05/03

Course Policies

Communication

Punctual Attendance and active participation are expected in every class. Anyone arriving later than the start time, 2:25pm, will be considered absent for that class. Participation includes asking questions, contributing answers, proposing ideas, and providing constructive comments. 30% of your course grade (see below) is based on attendance & participation.

As you will discover, I am a proponent of two-way communication and I welcome feedback during the semester about the course. I am available to answer student questions, listen to concerns, and talk about any course-related topic (or otherwise!). Come to office hours! This helps me get to know you. You are welcome to stop by and chat. There are many more exciting topics to talk about that I won't have time to cover in-class.

Please stay in touch with me, particularly if you feel stuck on a topic or project and can't figure out how to proceed. Often a quick e-mail, phone call or face-to-face conference can reveal solutions to problems and generate renewed creative and scholarly energy. It is essential that you begin assignments early.

Grading

At the end of the semester, final grades will be calculated as a weighted average of all grades according to the following weights:

Labs & Written Assignments:	50%
Presentations:	20%
Class Participation and Attendance:	30%
Total:	100%

Incomplete grades will be given only for verifiable medical illness or other such dire circumstances.

All graded work will receive a percentage grade between 0% and 100%. Here is how the percentage grades will map to final letter grades:

Rounded Percentage	Letter grade	Rounded Percentage	Letter grade
97% -100%	A+ (4.0)	77% - 79%	C+ (2.3)
93% - 96%	A (4.0)	73% - 76%	C (2.0)
90% - 92%	A- (3.7)	70% - 72%	C- (1.7)
87% - 89%	B+ (3.3)	67% - 69%	D+ (1.3)
83% - 86%	B (3.0)	60% - 66%	D (1.0)
80% - 82%	B- (2.7)	0% - 59%	F (0.0)

The instructor reserves the right to adjust the percentage ranges for each letter grade upward in your favor.

Incomplete grades will be given only for verifiable medical illness or other such dire circumstances. Please have any instances of medical illness or dire circumstances communicated to me thorugh your Dean.

Submission, Late Policy, and Making Up Past Work

All work must be turned in either in hard-copy or electronic submission, depending on the instructions given in the assignment. Extensions will be given only in the case of verifiable medical excuses or other such dire circumstances, if requested in advance and supported by your Academic Dean.

Late submissions will receive a penalty of 20% for every 0-24 hours it is past the due date and time (e.g., assignments turned in 25 hrs late will receive a penalty of 40%).

Study Groups

I encourage you to discuss the material and work together to understand it. Here are some thoughts on collaborating with other students:

The readings and lecture topics can be group work. Please discuss the readings and associated topics with each other. Work together to understand the material. I highly recommend forming a reading group to discuss the material -- I will explore many ideas and it helps to have multiple people working together to understand them.
It is fine to discuss the topics covered in the homeworks, to discuss approaches to problems, and to sketch out general solutions. However, you MUST write up the homework answers, solutions, and programs individually without sharing specific solutions, mathematical results, program code, etc. If you made any notes or worked out something on a white board with another person while you were discussing the homework, you shouldn't use those notes while writing up your answer.
Under ABSOLUTELY NO circumstances should you share computer code with another student, printed, electronic, or otherwise. Similarly, you are not permitted to use or consult code found on the internet for any of your assignments.

If you have any questions as to what types of collaborations are allowed, please feel free to ask.