Bryn Mawr College
CMSC 330 Algorithms: Design & Practice
Prof. Deepak Kumar
Lecture Hours: Tuesdays & Thursdays, 11:25a to 12:45p
Room: Park 336
Lab: Fridays 10:00a to Noon in Room 231 (Attendance in ALL labs is required)
Office Hours: Tue 9:25a to 11:00a or by appointment.
- Computer Science Lab Room 231 (Science Building)
- You will also be able to use your own computer to do the labs
for this course.
Algorithms Unlocked by Thomas Cormen, MIT Press 2013. Available at the Campus Bookstore ($27.00 - new, $19.00 - used). Also at Amazon.com for $24.48 click here.
Nine Algorithms That Changed The Future by John MacCormick, Princeton University Press, 2013. Available at the Campus Bookstore ($15.00 - new, $10.75 - used). Also available at Amazon.com for $12.40 click here.
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: CS206 and CS231. This is a Writing Intensive (WI) course.
January 17: First lecture
April 27: Last Lecture
Unless explicitly specified, all assignments are due at the beginning of the class (BY 11:30a sharp) on the date due. No credit will be awarded for any late work.
- Lab#1 Write-up (Due in class on Thursday, January 26): Language Standards, Reference Compilers, Programming Pitfalls
- Lab#2 Write-up (Due in class on Thursday, February 2): Linear Search Algorithms: Performance Comparison.
- Lab#3 Write-up (Due in class on Thursday, February 9): How many FLOPS?
- Lab#4 Write-up (Due in class on Thursday, February 23): Quicksort versus Hybrid Quicksort versus Library sort() versus Dual Pivot Quicksort.
- Lab#5 Answers (Due in class on Tuesday, February 21): Special Hell Week (WTF) Edition.
- Lab#6 Write-up (Due in class on Thusrday, March 2): Anagram search.
- Lab#7 (Due at the end of Lab today):
- Lab#8 (Due in class on Tuesday, March 21): Graph Search: The W-O-M-A-N Puzzle.
- Lab#9-10 (Due in classon Thursday, April 6): Soundex, Metaphone, Phonetic Anagrams, and Homophones.
- Lab#11: (Due on Thursday, April 13): Dijkstra's Shortest Path Algorithm
- Lab#12: (Due on Thursday, April 20): Implementing LZW Algorithm
- Lab#13: (Due on Thursday, April 27): Cryptographic Hash Functions
- Week 1 (Week of January 16)
January 17: Course introduction, logistics, overview. Agorithms: Truth, Beauty, and Engineering. Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).
Read: Chapter 1 from Cormen, Chapter 1 from MacCormick.
Slides: Algorithms: Design & Practice (Introduction)
January 19: Contd. Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).
Read: Chapter 2 from Cormen.
January 20 Laboratory#1: Language standard, language reference, reference compilers, simple coding pitfalls.
Lab#1 Write-up (Due in class on Thursday, January 26): Language Standards, Reference Compilers, Programming Pitfalls
- Week 2 (Week of January 23)
January 24: What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity
Read: Chapter 3 from Cormen.
January 26: Algorithms for linear search. Doing performance analysis.
Read: Chapter 3 from Cormen.
January 26 Laboratory#2: Comparative Performance Evaluation of linear search algorithms.
Lab#2 Write-up (Due in class on Thursday, February 2): Linear Search Algorithms: Performance Comparison.
- Week 3 (Week of January 30)
January 31: Presentation: Sorting by Ilisha & Ziyan. More on sorting. Stable sorts. Sorting (linked)-lists: why it is a bad idea!
Read: Chapter 2 from MacCormack.
Watch: Three Beautiful Quicksorts by Jon Bentley.
February 2: Presentation: Results from Lab#2 by Ann & Sally. More on sorting. Stable sorts. Sorting (linked)-lists: why it is a bad idea! Chapter 3 (Cormen) Wrap-up.
Read: Chapter 2 from MacCormack.
February 3 Laboratory#3: No lab today due to Women in Data Science Day at SAP.
Lab#3 Write-up (Due in class on Thursday, February 9): How many FLOPS?
- Week 4 (Week of February 6)
February 7: Presentation: Web Search by Leqi & Xiaomeng (Chapter 2 from MacCormack)
Note: Today's Office Hours are cancelled de to a CS Department Meeting. Please send e-mail for appointments.
February 9: No class today due to snowstorm. Presentation scheduled for today will be next week (thursday).
Read: Chapter 3 from MacCormick.
February 10 Laboratory#4: Quicksort versus Hybrid Quicksort versus Library sort() versus Dual Pivot Quicksort. Note: This lab is due on Thursday, February 23.
- Week 5 (Week of February 13)
February 14: Indexing & Page Rank by Kewei & Xinyue (MacCormick, Chapter 3)
Read: Chapter 4 from MacCormick.
February 16: Presentation: Lab#3 - How many FLOPS by Lizzie & Jingling & Stepahnie. Some programming puzzles. Inlining functions. map(), filter(), and reduce() in Python.
February 17 Laboratory#5 (answeres due on Tuesday, Feb. 21): Special Hell Week (WTF) Edition.
- Week 6 (Week of February 20)
February 21: Public Key Cryptography by Keisna & Adriana
Read: Chapters 5 & 6 from MacCormick.
February 23: Presentation on Lab#4 by Ilisha & Ziyan. Comparing Quicksorts. Dual-Pivot Quicksort.
February 24 Lab#6: Write-up (Due in class on Thusrday, March 2): Anagram search.
- Week 7 (Week of February 27)
February 28: Nearest Neighbor & Decision Trees by Lizzie & Jingling & Stepahnie. Review of Hash Tables.
March 2: Error Correcting Codes by Ann & Sally
March 3 Laboratory#7 (Due at the end of Lab today): Hash Functions and hash tables. Lab is due at the end of the session today.
- Week 8 (Week of March 6)
No classes. Spring Break!
- Week 9 (Week of March 13)
March 14: No Class, snow day!
March 16: Review of Lab#6 & Lab#7. Graphs: Terminology. Graph Search algorithms.
Read: Chapters 5 & 6 from MacCormick.
March 17 Laboratory#8 (Due in class on Tuesday, March 21): Graph Search: The W-O-M-A-N Puzzle.
Link to dataset for Lab#8: http://cs.brynmawr.edu/Courses/cs330/spring2017/USStates.csv
- Week 10 (Week of March 20)
March 21: Lab#8 Presentation: Graph Search on the W-O-M-A-N Puzzle by Kewei & Xinyue.
March 23: Graph Algorithms: Topological Sort & Dijkstra's Algorithm by Adriana & Keisna.
Read: Chapter 6 from Cormen.
March 24 Laboratory#9 and #10 (Due in classon Thursday, April 6): Soundex, Metaphone, Phonetic Anagrams, and Homophones.
- Week 11 (Week of March 27) Deepak is out of town this week. There will be alternative activities.
March 28: No class today, Deepak is out of towm.
March 30: No class today, Deepak is out of town.
March 31 Laboratory#10: No lab meeting today, Deepak is out of town. Continue working on Lab#9 and #10 from last week.
- Week 12 (Week of April 3)
April 4: Graph Algorithms: Belman Ford Algorithm & Floyd Warshall Algorithm by Leqi & Xiameng.
April 6: Soundex, Metaphone, Phonetic Anagrams, and Homophones.Presentation by Ilisha & Ziyan.
April 7 Laboratory#11: (Due on Thursday, April 13) Dijkstra's Shortest Path Algorithm
- Week 13 (Week of April 10)
April 11: Data Compression (Chapter 7 from MacCormick): Presentation by Ann & Sally
April 13: Lab 11: Dijkstra's Shortest Path Algorithm: Presentation by Lizzie, Jingling, and Stephanie
April 14 Laboratory#12: Implementing LZW Algorithm (Due on Thursday, April 20)
- Week 14 (Week of April 17)
April 18: Digital Signatures (Chapter 9 from MacCormick): Presentation by Kewei & Xinyue
April 20: Lab 12: Implementing LZW Algorithm: Presentation by Keisna & Adriana
April 21 Laboratory#13: Cryptographic Hash Functions (Due on Thursday, April 27)
- Week 15 (Week of April 24)
April 25: Databases (Chapter 8 from MacCormick) Presentation by Leqi & Xiaomeng
April 27: Course Wrap up. Slides from today: Click here.
No Laboratory this week.
Punctual Attendance and active participation are
expected in every class. Anyone arriving later than 11:25a 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.
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, 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.
All graded work will receive a grade, 4.0, 3.7, 3.3, 3.0, 2.7, 2.3, 2.0, 1.7, 1.3, 1.0, or 0.0. 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 Work: 35%
Class Participation & Attendance: 30%
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. E-mail submissions, when permitted, should request
a "delivery receipt" to document time and date of submission.
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.
No assignment will be
accepted after it is past due.
No past work can be "made up" after it is due.
No regrade requests will be entertained one week after the graded work is returned in class.
I encourage you to discuss the material and work together to
understand it. Here are some thoughts on collaborating with other
If you have any questions as to what types of collaborations are
allowed, please feel free to ask.
- 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
- 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.
Created on January 11, 2017.