Bryn Mawr College
CMSC 330 Algorithms: Design & Practice
Prof. Deepak Kumar
Lecture Hours: Tuesdays & Thursdays, 9:55a to 11:15a
Room: Park 337
Lab: Thursdays 11:25a to 12:45p in Room 231 (Attendance in ALL labs is required)
Office Hours: Tuesdays, 1:30-2:30p & Wednesdays, 10a 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 9:55a sharp) on the date due. No credit will be awarded for any late work.
- Lab#1 (Write-up Due in class on Thursday, February 1): Language Standards, Reference Compilers, Programming Pitfalls
- Lab#2: (Write-up Due in class on Thursday, February 8): Performance analysis of Linear Search algorithms.
- Lab#3: (Write-up Due in class on Thursday, February 15): Performance Analyses of Quicksort algorithms (Bentley's, Hybrid, Library sort, Dual-Pivot).
- Lab#5: (Write-up Due in class on Tuesday, February 20): Special WTF (Hell Week Edition)-Programming puzzlers.
- Lab#4: (Write-up Due in class on Thursday, February 27): Finding anagrams.
- Lab#6: (Write-up due in class on Thursday, March 8): Hash Tables - use, collisions and load factor experiment.
- Lab#7/8: (Write-up due in class on Thursday, March 22): Soundex & metaphone Algorithms- finding homophones in English.
- Lab#9: (Write-up due in class on Thursday, March 29): Graph Search (Depth-First, Breadth-First): Solving the W-O-M-A-N Puzzle.
- Lab#10: (Write-up due in class on Thursday, April 5): Graphs : Dijkstra's Shortest Path Algorithm
- Lab#11: (Write-up due in class on Thursday, April 12): Computing Fibonacci Numbers - Many Ways in Python using: iterators, generators, memoizers, and decorators.
- Lab#12: (Write-up due in class on Thursday, April 17): Cryprographic Hash Functions - Hands on with MD5 and SHA families.
- Week 1 (January 23, 25)
January 23: 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:Introduction to Algorithms: Design & Practice.
January 25: Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).
Lab#1 Language Standards, Reference Compilers, Programming Pitfalls. Write-up is due in class on Tuesday, January 30
- Week 2 (January 30, February 1)
January 30: Algorithms for linear search. Doing performance analysis.
Read: Chapter 2 & 3 from Cormen.
February 1: Linear Search, contd. Doing presentations: some tips. Also, writing an essay vs a report.
- Week 3 (February 6, 8)
: Sorting algorithms (Chapter 3 - Cormen): Presentation by Chloe & Prakhya. Language coding style, alternat9ive implementations of Quick Sort.
Read: Chapters 2 & 3 from MacCormick.
February 8: Lab2: Performance analysis of Linear Search algorithms. Presentation by Abigail & Nanda
Lab#3: (Write-up Due in class on Thursday, February 15): Performance Analyses of Quicksort algorithms (Bentley's, Hybrid, Library sort, Dual-Pivot).
- Week 4 (February 13, 15)
February 13: Search Engine Indexing (Chapter 2-McCormick): Presentation by Edison & Leslie
February 15: Lab3: Performance Analyses of Quicksort algorithms (Bentley's, Hybrid, Library sort, Dual-Pivot).. Presentation by Nicole & Sarah Kay
Lab#5: (Write-up Due in class on Tuesday, February 20): Special WTF (Hell Week Edition)-Programming puzzlers. No presentation for this lab,
- Week 5 (February 20, 22)
February 20: PageRank (Chapter 3 - MacCormick): Presentation by Sarah Depew & Sarah Malia
Lab#4: (Write-up Due in class on Thursday, February 27): Finding anagrams.
February 22: No class, Deepak is out of town. There will be a Lab 4 (handout on Feb 20) for this week.
- Week 6 (February 27, March 1)
February 27: Public Key Cryptography (Chapter 4 - MacCormick): Presentation by MIkal & Kellie
: Lab4: Presentation by Ju-Han & Kennedy
Lab#6: (Write-up due in class on Thursday, March 8): Hash Tables - use, collisions and load factor experiment.
- Week 7 (March 6, 8)
March 6: Pattern Recognition: Nearest neighbor, Decision Trees (Chapter 6-MacCormick): Presentation by Julia & Xinyi
March 8: Lab 6: Presentation by Sujin & Leslie (PLUS Graphs (Chapter 5/6 Cormen) - Deepak)
Lab#7/8: (Write-up due in class on Thursday, March 22): Soundex & metaphone Algorithms- finding homophones in English.
- Week 8 (March 13, 14)
No classes. Spring Break!
- Week 9 (March 20, 22)
March 20: Community Learning Day - No Classes
March 22: Lab 7/8: Presentation by Abigail & Edison (Plus Deepak: Dijkstra's Shortest Path Algorithm)
Lab#9: (Write-up due in class on Thursday, March 29): Graph Search (Depth-First, Breadth-First): Solving the W-O-M-A-N Puzzle.
- Week 10 (March 27, 29)
March 27: Graph Algorithms - Belman Ford Algorithm - Presentation by Sara & Xinyi. Floyd Warshall Algorithm - Presentation by Chloe & Kellie. Both from Chapter 6 Cormen.
March 29: Lab 9: Prersentation by Julia and Ju-Han.
Lab#10: (Write-up due in class on Thursday, April 5): Graphs : Dijkstra's Shortest Path Algorithm
- Week 11 (April 3, 5)
April 3: Pattern Recognition - Neural Nets (Chapter 6 - MacCormick). Presentation by Nicole and Nanda. Deepak: Higher Order functions in Python: lambda(), map(), filter(), reduce.
April 5: Lab#10 - Presentation by Kennedy and Mikal: Computing Fibonacci Numbers in Python-recursive, iterative, iterators, generators, memoizing, decorators.
Lab#11: (Write-up due in class on Thursday, April 12): Computing Fibonacci Numbers - Many Ways in Python using: iterators, generators, memoizers, and decorators.
- Week 12 (April 10, 12)
April 10: Error Correcting Codes (Chapter 5 MacCormick). Presentation by Sujin and Leslie.
April 12: Lab#11 - Presentation by Chloe and Kellie.
Lab#12: (Write-up due in class on Thursday, April 17): Cryprographic Hash Functions - Hands on with MD5 and SHA families.
- Week 13 (April 17, 19)
NOTE:: Deepak's Office Hours for Tuesday, April 17 are moved to 12:00-1:00p due to a doctor's appointment.
April 17: Data Compression (Chapter 9 Cormen, Chapter 7 MacCormick). Presentation by Abigail and Edison.
April 19: Lab 12: Presentation by Sarah and Xinyi.
- Week 14 (April 24, 26)
April 24: Digital Signatures (Chapter 9 - MacCormick). Presentation by Julia and Ju-Han.
April 26: Lab 13 - Presentation by Nicole and Nanda.
- Week 15 (May 1, 3)
May 1: Databases (Chapter 8 - MacCormick). Presentation by Kennedy and Mikal.
May 3: Course Wrap up. Deepak.
Punctual Attendance and active participation are
expected in every class. Anyone arriving later than 9:55a 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 3, 2018.